Java hashCode() 方法深入理解

String类的hasCode()

Java代码

public int hashCode() {
    int h = hash;
    if (h == 0) {
        int off = offset;
        char val[] = value;
        int len = count;

            for (int i = 0; i < len; i++) {
                h = 31*h + val[off++];
            }
            hash = h;
        }
        return h;
    }

这段代码最有意思的还是hash的实现方法了。最终计算的hash值为:

s[0]31n-1 + s[1]31n-2 + … + s[n-1]

s[i]是string的第i个字符,n是String的长度。那为什么这里用31,而不是其它数呢?

31是个奇素数,如果乘数是偶数,并且乘法溢出的话,信息就会丢失,因为与2相乘等价于移位运算。使用素数的好处并不是很明显,但是习惯上都使用素数来计算散列结果。31有个很好的特性,就是用移位和减法来代替乘法,可以得到更好的性能:31*i==(i<<5)-i。现在的VM可以自动完成这种优化。(From
Effective Java)


WHY hashCode()?

集合Set中的元素是无序不可重复的,那判断两个元素是否重复的依据是什么呢?
“比较对象是否相等当然用Object.equal()了”,某猿如是说。但是,Set中存在大量对象,后添加到集合Set中的对象元素比较次数会逐渐增多,大大降低了程序运行效率。
Java中采用哈希算法(也叫散列算法)来解决这个问题,将对象(或数据)依特定算法直接映射到一个地址上,对象的存取效率大大提高。这样一来,当含有海量元素的集合Set需要添加某元素(对象)时,先调用这个元素的hashCode(),就能一下子定位到此元素实际存储位置,如果这个位置没有元素,说明此对象时第一次存储到集合Set,
直接将此对象存储在此位置上;若此位置有对象存在,调用equal()看看这两个对象是否相等,相等就舍弃此元素不存,不等则散列到其他地址。

Java.lang.Object
有一个hashCode()和一个equals()方法,这两个方法在软件设计中扮演着举足轻重的角色。在一些类中覆写这两个方法以完成某些重要功能。本文描述了为什么要用hashCode(),
如何使用,以及其他的一些扩展。阅读本文需要有基本的hash算法知识以及基本的Java集合知识,本文属于菜鸟入门级讲解,大神读至此请点击右上角的X,以免浪费您的时间^_^。

  1. 如果a.equals(b)返回“true”,那么a和b的hashCode()一定相等。
  2. 如果a.equals(b)返回“false”,那么a和b的hashCode()有可能相等,也有可能不等。
    下面是一个例子。在实际的软件开发中,最好重写这两个方法。

HOW use hashCode()?

Java语言对猿设计equal()有五个必须遵循的要求。

  1. 对称性。若 a.equal(b) 返回”true”, 则 b.equal(a) 也必须返回 “true”.
  2. 反射性。a.equal(a) 必须返回”true”.
  3. 传递性。若a.equal(b) 返回 “true”, 且 b.equal(c)返回 “true”,
    则c.equal(a)必返回”true”.
  4. 一致性。若a.equal(b) 返回”true”, 只要a,
    b内容不变,不管重复多少次a.equal(b)必须返回”true”.
  5. 任何情况下,a.equals(null),永远返回是“false”;a.equals(和a不同类型的对象)永远返回是“false”.

hashCode()的返回值和equals()的关系.

  1. 如果a.equals(b)返回“true”,那么a和b的hashCode()必须相等。
  2. 如果a.equals(b)返回“false”,那么a和b的hashCode()有可能相等,也有可能不等。

下面是一个例子。在实际的软件开发中,最好重写这两个方法。

public class Employee {
    int        employeeId;
    String     name;

    // other methods would be in here 

    @Override
    public boolean equals(Object obj)
    {
        if(obj==this)
            return true;
        Employee emp=(Employee)obj;
        if(employeeId.equals(emp.getEmployeeId()) && name==emp.getName())
            return true;
        return false;
    }

    @Override
    public int hashCode() {
        int hash = 1;
        hash = hash * 17 + employeeId;
        hash = hash * 31 + name.hashCode();
        return hash;
    }
}

下面着重介绍一下常用类的hashCode()实现方法。

Java.lang.Object
有一个hashCode()和一个equals()方法,这两个方法在软件设计中扮演着举足轻重的角色。在一些类中重写这两个方法以完成某些重要功能。

Object类的hasCode()

Object类中hashCode()是一个Native方法。Native方法如何调用?

public native int hashCode();

Object类的Native方法类可在这里找到。
深入分析请看另外一篇博客

static JNINativeMethod methods[] = {
    {"hashCode",    "()I",                    (void *)&JVM_IHashCode},
    {"wait",        "(J)V",                   (void *)&JVM_MonitorWait},
    {"notify",      "()V",                    (void *)&JVM_MonitorNotify},
    {"notifyAll",   "()V",                    (void *)&JVM_MonitorNotifyAll},
    {"clone",       "()Ljava/lang/Object;",   (void *)&JVM_Clone},
};

源代码包括getClass()(See line58)等, hashCode()(See
line43)被定义为一个指向JVM_IHashCode指针。

jvm.cpp中定义了JVM_IHashCode(line
504)函数,
此函数里调用ObjectSynchronizer::FastHashCode,其定在 synchronizer.cpp,
可参考576行的FastHashCode 和 530行的 get_next_hash 的实现。

equals()和hashCode()方法是用来在同一类中做比较用的,尤其是在容器里如set存放同一类对象时用来判断放入的对象是否重复。

List<String> list = Arrays.asList("a", "b", "c");
boolean contains = list.contains("b");


在object类中,hashcode()方法是本地方法,返回的是对象的地址值,而object类中的equals()方法比较的也是两个对象的地址值,如果equals()相等,说明两个对象地址值也相等,当然hashcode()
也就相等了。

既然equals比较元素相等更准确,那么为什么还要用hashCode( )方法呢?
因为hash算法对于查找元素提供了很高的效率,如果想查找一个集合中是否包含有某个对象,大概的程序代码怎样写呢?
你通常是逐一取出每个元素与要查找的对象进行比较,当发现某个元素与要查找的对象进行equals方法比较的结果相等时,则停止继续查找并返回肯定的信息,否则,返回否定的信息,如果一个集合中有很多个元素,比如有一万个元素,并且没有包含要查找的对象时,则意味着你的程序需要从集合中取出一万个元素进行逐一比较才能得到结论。

这里我们首先要明白一个问题:
equals()相等的两个对象,hashcode()一定相等,equals()不相等的两个对象,却并不能证明他们的hashcode()不相等。换句话说,equals()方法不相等的两个对象,hashCode()有可能相等。
在这里hashCode就好比字典里每个字的索引,equals()好比比较的是字典里同一个字下的不同词语。就好像在字典里查“自”这个字下的两个词语“自己”、“自发”,如果用equals()判断查询的词语相等那么就是同一个词语,比如equals()比较的两个词语都是“自己”,那么此时hashCode()方法得到的值也肯定相等;如果用equals()方法比较的是“自己”和“自发”这两个词语,那么得到结果是不想等,但是这两个词都属于“自”这个字下的词语所以在查索引时相同,即:hashCode()相同。如果用equals()比较的是“自己”和“他们”这两个词语的话那么得到的结果也是不同的,此时hashCode()
得到也是不同的。
反过来:hashcode()不等,一定能推出equals()也不等;hashcode()相等,equals()可能相等,也可能不等。

换句话说:当我们重写一个对象的equals方法,就必须重写他的hashCode方法,不重写他的hashCode方法的话,Object对象中的hashCode方法始终返回的是一个对象的hash地址,而这个地址是永远不相等的。所以这时候即使是重写了equals方法,也不会有特定的效果的,因为hashCode方法如果都不想等的话,就不会调用equals方法进行比较了,所以没有意义了。


  • 选择字段
    但哪些字段是相关的呢?需求将会帮助我们回答这个问题:
    如果相等的对象必须具有相同的哈希码,那么计算哈希码就不应包括任何不用于相等检查的字段。(否则两个对象只是这些字段不同但是仍然有可能会相等,此时他们这两个对象哈希码却会不相同。)所以用于哈希组字段应该相等时使用的字段的子集。默认情况下都使用相同的字段,但有一些细节需要考虑。
  • 澳门新葡亰网站注册,总结
    我们了解到计算哈希码就是压缩相等的一个整数值:相等的对象必须有相同的哈希码,而出于对性能的考虑:最好是尽可能少的不相等的对象共享相同的哈希码。
    这就意味着如果重写了equals方法,那么就必须重写hashCode方法
    当实现hashCode使用与equals中使用的相同的字段(或者equals中使用字段的子集)
    最好不要包含可变的字段。对集合不要考虑调用hashCode,如果没有特殊的输入特定的模式,尽量采用通用的哈希算法