我经常听到很多地方和教程中说，每当重写equals()方法，我需要重写hashCode（）方法。但是，原因是什么？

equals()是定义在Object的一个方。在Java中，有两种类型的比较。一种方法是使用 “==” 操作符，
另一种就是“equals()” 。这两者之间的差异相信大家都知道， “equals()”是指等价关系。
在广义上说两个对象是相等的，他们满足的是“equals()”条件。

hashCode()是定义在Object的一个native方法，默认实现基本上是对象提供来自内存地址映射到一个整数的值。

源代码如下(截自jdk1.7 Object):

1
2
3
4
5
6
7
8
public class Object {
	// 省略
	public boolean equals(Object obj) {
        return (this == obj);
    }
    public native int hashCode();
    // 省略
}

when and why override equals() ro hashCode()?

equals()与hashCode()具体关系是什么？什么时候应该重写equals() 和 hashCode()方法呢？有一个经验法则，
如果你要复写方法 equals() 和 hashCode() 之一，你就必须复写equals() 和 hashCode()，否则就是一种违反合同的行为。
(参考 Java doc)。

下面代码展示了 equals() 和 hashCode() 的使用:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class Person {
    private String name;
    private int age;
	... 省略了构造函数、get和set。
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        Person p = (Person)o;
        // 根据name判断是否相等
        if(name!=null?!name.equals(p.name):p.name!=null) return false;
        return true;
    }
    @Override
    public int hashCode() {
        // 直接使用age做为hash值
        return age;
    }
    public static void main(String[] args) {
        // 创建了2个逻辑上是相等的对象
        Person person1 = new Person("faith",32);
        Person person2 = new Person("faith",31);
        // HashSet 是基于HashMap实现的
        Set<Person> personSet = new HashSet<Person>();
        personSet.add(person1);
        personSet.add(person2);
        System.out.println(personSet.size());//结果是2 
    }
}

结果是2，完全不满足set的特性，为什么呢？如果你了解hash的存储方式，你就会知道，在存储时候，先计算hash值
来索引的。

hashCode()主要是和采用hash存储的集合(HashMap、HashSet、HashTable)有关系了，我们看一下以下代码(截自jdk1.7 HashMap)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public V put(K key, V value) {
        if (key == null) // key	值为null 采用putForNullKey()方法
            return putForNullKey(value);
        int hash = hash(key); // 根据 key 的 keyCode 计算 Hash 值  
        int i = indexFor(hash, table.length);//搜索指定 hash 值在对应 table 中的索引
        //如果 i 索引处的 Entry 不为 null，表明此处有 Entry，通过循环不断遍历得到元素  
        for (Entry<K,V> e = table[i]; e != null; e = e.next) {
            Object k;
            // 找到指定 key 与需要放入的 key 相等  
     		// 通过hash 和 equals 判断
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
		// 如果 i 索引处的 Entry 为 null，表明此处还没有 Entry,直接将 key、value 添加到 i 索引处
        modCount++;
        addEntry(hash, key, value, i);
        return null;
    }

根据代码发现 HashMap 采用 Hash 算法决定集合元素的存储位置，首先判断的就是 Hash 值，然后才是 equals 判断。
所以当 hash 值不同的时候，存储的时候就会判断那hash值的链中值是否相等。由于即使有相同对象采用 equals 判断的，
也会存储进去，以至于产生了不统一情况。所以当我们重写 equals 时候，紧接着就应该重写 hashCode。

在 HashMap 中 hash 值是怎么计算的呢？看下面代码(截自jdk1.7 HashMap):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
final int hash(Object k) {
        int h = 0;
        // 根据useAltHashing判断采哪种生成方式
        if (useAltHashing) {
            if (k instanceof String) {
                return sun.misc.Hashing.stringHash32((String) k);
            }
            h = hashSeed;
        }
		// 各种运算啊！主要是无符号右移和异或运算
        h ^= k.hashCode();
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }

如果类具有自己特有的“逻辑相等”概念，而且超类中没有覆盖equals以实现期望的行为，这时我们就需要覆盖equals方法。这通常适合于“值类(value class)”，比如Integer和Date。这样做了之后实例就可以满足映射表(map)的key或者set元素的预期行为(enum类型不用改写equals)。

复写equals通用约定：

  • 自反性：对于非null的引用值x，x.equals(x)返回true，x.equals(null)返回false。
  • 对称性：对于任何的引用值x和y，如果y.equals(x)为true，那么x.equals(y)也为true。
  • 传递性：对于任何的引用值x、y和z，如果x.equals(y)为true，并且y.equals(z)为true，那么x.equals(z)也为true。
  • 一致性：对于任何的引用值x和y，如果equals比较的对象信息没有修改，无论x.equals(y)多少次都应该返回一致。

如果源码你看过并且知道相关的hash知识，那不难理解这些约定。

计算hash值

为什么要研究证明计算hash值？因为一个好的hash通常是没有相同的hash值的。相同的hash值额外的冲突处理，这样会浪费
性能。

一个简单方式:

1.把某个非零常数值，例如17，保存在int变量result中；
2.对于对象中每一个关键域f（指equals方法中考虑的每一个域）：
3.boolean型，计算(f? 0 : 1);
4.byte,char,short型，计算(int);
5.long型，计算(int)(f ^ (f>>>32));
6.float型，计算Float.floatToIntBits(afloat);
7.double型，计算Double.doubleToLongBits(adouble)得到一个long，再执行[2,3];
8.对象引用，递归调用它的hashCode方法;
9.数组域，对其中每个元素调用它的hashCode方法。
10.将上面计算得到的散列码保存到int变量c, 然后执行result=37*result+c;
11.返回result。

还可以后续看是否有相同hash值，有的话找出原因，再改进。

在java中String 用31来做hash计算,推荐使用：

公式：s[0]*31^(n-1) + s[1]*31^(n-2) + … + s[n-1]

为什么使用31？

31是个神奇的数字，因为任何数n * 31就可以被JVM优化为 (n << 5) -n,移位和减法的操作效率要比乘法的操作效率高的多，对左移现在很多虚拟机里面都有做相关优化，并且31只占用5bits！

参考文档