为什么 HashMap.put 既比较哈希值又测试相等性?

2022-01-08 00:00:00 hashmap java

我分析Java中的HashMap源代码，得到一个关于put方法的问题.

I analyse the HashMap source code in Java and get a question about the put method.

下面是JDK1.6中的put方法:

Below is the put method in JDK1.6:

public V put(K key, V value) {
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key.hashCode());
    int i = indexFor(hash, table.length);
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }

    modCount++;
    addEntry(hash, key, value, i);
    return null;
}

我对 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) 感到困惑

为什么会这样?

因为在Java超类Object中，有一个contract of hashCode and equals:

Because in Java super class Object, there is a contract of hashCode and equals:

如果两个对象根据equals(Object)方法相等，那么对两个对象中的每一个调用hashCode方法必须产生相同的整数结果.

If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.

所以 key.equals(k) 意味着 key.hashCode() == k.hashCode().

hash()如下:

 static int hash(int h) {
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

因此 key.hashCode() == k.hashCode() 意味着 e.hash == hash.

那么为什么不是if ((k = e.key) == key || key.equals(k))这样的条件?

推荐答案

这只是一个优化:比较两个整数比调用 equals() 更快.

It's just an optimization: comparing two integers is faster than calling equals().

如果两个hashcode不同，那么根据equals和hashCode的约定，map知道现有的key不等于给定的key，并且可以更快地进入下一个.

If the two hashcodes differ, then, based on the contract of equals and hashCode, the map knows that the existing key isn't equal to the given key, and can go faster to the next one.

相关文章