关于 equals 和 hashCode 方法

为何重写 equals 就必须重写 hashCode

有这样一条定则——如果重写了 equals 方法，就一定要重写 hashCode 方法。

这是因为，对象的 hashCode 是同对象的值相关联的，如果两个对象相等，则两个对象的 hashCode 也应当相等。可是，Object 类的 hashCode 方法其返回值只与对象的地址相关联，因此，如果只重写 equals 方法，就会导致这样一种情况——两个 equal 的对象，其 hashCode 却是不相等的。这会导致在 HashSet，HashMap 之类的利用哈希表进行映射的数据结构出现问题。

HashSet，HashMap 的哈希函数遵循这样的逻辑——如果两个对象拥有不同的哈希值，则它们是必定不同的，如果拥有相同的哈希值（这是哈希碰撞的情况，两个对象不相等，但其哈希值经过再次混淆后相同），则调用 equals 方法再判断是否确实为相等的对象。

我们编写 hashCode，没有必要强求一个对象必然要得到独一无二的 hashCode，这是不可能的，尽量减少碰撞即可。

注：==运算符比较的是两个变量的值，对于基本类型，则比较的是它们的值，对于引用类型，则比较的是它们存储的地址，因此，只有两个引用类型的变量（即使其类型不同也可以，比如一个子类的对象引用和一个父类的对象引用指向一个子类的对象）指向同一个地址（或者说，堆里的同一个对象实例）的时候==才返回真。

从 HashSet 的源码入手

当我们调用 HashSet 的 add 实例方法的时候，会发生什么？看看源码吧。

@Override
 public boolean add(E e) {
     // 这里的 map 是个 HashMap<E, Object>类的实例，说明 HashSet 是通过 HashMap 实现的
     // PRESENT 是一个 final static 的 Object 对象，这里显然只是用来置位的，没有实际作用
     return map.put(e, PRESENT)==null; 
 }

再看看 HashMap 的 put 方法。HashMap 使用的是数组——链表结构，如果某个链表长度大于阀值（8）且数组长度大于 64，则该链表将被转换为红黑树结构，否则会将数组的长度乘 2。不过判断的流程还是一致的——首先将元素的 hashCode 使用杂凑函数进行处理，确定其插入位置，如果插入位置为空，则直接插入，（对于数组——链表）否则遍历该位置的所有元素，对每一个元素进行判断；首先比较哈希值是否相等，如果相等，则判断其是否是同一对象，判断其是否 equal，如果是则说明是重复的 key，对该 key 进行处理，如果到最后都未找到，则将其插入尾端。

public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}
// HashMap 中使用的哈希方法，它对对象的 hashCode 进行杂凑
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); 
}

// 这代码写出来是不是不想给人看的？？？
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i; // 这里的 Node 是一个实现了 Entry 的类，其有链表结构
    // table 是整个哈希表。它是数组——链表结构或是数组——红黑树结构
    if ((tab = table) == null || (n = tab.length) == 0) 
        n = (tab = resize()).length;
    
    // 这个 if-else 是重点！
    // 如果要插入的位置没有元素，则直接插入
    // 这里需要注意的是，这个位置是对象的哈希对 n 取余的结果，所以存在这个位置的元素的哈希值并不一定是相等的
    if ((p = tab[i = (n - 1) & hash]) == null)   // 在 n 等于 2 的幂次方的时候，(n-1)&hash==hash&n，并且前者效率更高，这也是为什么 HashMap 的容积使用 2 的幂次方
        tab[i] = newNode(hash, key, value, null);
    // 如果有元素，则需要遍历该位置的所有元素
    else {
        Node<K,V> e; K k;
        // 需要注意的是，||的优先级是更高的。
        // 这里的 p 是碰撞位置的链表的第一个元素……至少最初是
        // 它先看该元素的 hash 和链表中该位置的 hash 是否相等 （这里就能看到，如果没有重写 hashCode 方法，对于任意非重复插入的对象实例，这个 p.hash == hash 将始终为假，equals 方法将不被调用）
        // 然后看 (k = p.key) == key，即这两个 key 是否指向同一个对象，如果不是，则调用 equals 方法比较
        // 如果这个 if 检查成功，说明这两个对象真的是相同的，因此将 e 的值设为 p，等待下一步对其值进行更新并返回
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            e = p; 
        // 如果这个位置是一个 TreeNode，则说明使用的是红黑树结构
        else if (p instanceof TreeNode)
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        // 遍历 p 位置所在链表，找到第一个与其哈希相同，且指向同一个对象或 equal 的节点，如果到最后还没有找到，则插入到尾端。无论如何，e 保存了最终的位置，无论是插入还是更新`。
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) { 
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        
        // put 也要承担更改元素的作用
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        resize();
    afterNodeInsertion(evict);
    return null;
}

PS：HashSet 和 HashMap，IdentityHashMap 允许插入 null 或以 null 为 key。它的哈希将为 0。

PS：看看 IdentityHashMap

IdentityHashMap 则是另一个极端。与 HashMap 不同，它只比较元素的内存地址（即 Object 的 hashCode 方法，或者说可以理解成==运算符）来判断其是否是同一个 key，而不关心是否 equal。

private static int hash(Object x, int length) {
    int h = System.identityHashCode(x); // 这个 hashCode 调用其父类，即 Object 类的 hashCode 方法，而无论它是否重写 hashCode
    // Multiply by -127, and left-shift to use least bit as part of hash
    return ((h << 1) - (h << 8)) & (length - 1);
}
// 代码有点晦涩，只需要看到其中没有调用 equals 方法就够了……
public V put(K key, V value) {
    final Object k = maskNull(key);

    retryAfterResize: for (;;) {
        final Object[] tab = table;
        final int len = tab.length;
        int i = hash(k, len);

        for (Object item; (item = tab[i]) != null;
             i = nextKeyIndex(i, len)) {
            if (item == k) {
                @SuppressWarnings("unchecked")
                V oldValue = (V) tab[i + 1];
                tab[i + 1] = value;
                return oldValue;
            }
        }

        final int s = size + 1;
        // Use optimized form of 3 * s.
        // Next capacity is len, 2 * current capacity.
        if (s + (s << 1) > len && resize(len))
            continue retryAfterResize;

        modCount++;
        tab[i] = k;
        tab[i + 1] = value;
        size = s;
        return null;
    }
}