为什么HashTable在java中存储表中键的哈希值

Question

我正在通过Java的hash方法实现put方法,并且遇到了这个:

// Makes sure the key is not already in the hashtable.
    Entry tab[] = table;
    int hash = key.hashCode();
    int index = (hash & 0x7FFFFFFF) % tab.length;
    for (Entry<K,V> e = tab[index] ; e != null ; e = e.next) {
        if ((e.hash == hash) && e.key.equals(key)) {
            V old = e.value;
            e.value = value;
            return old;
        }
    }

虽然我知道需要一个密钥来检查冲突,但为什么Java存储密钥的哈希值并检查它？

Answer 1

因为相同的桶(tab)可以保持由于% tab.length操作而具有不同散列的物品.首先检查哈希可能是一些性能优化,以避免equals()在哈希不同时调用.

举一个这样的例子:假设你有两个复杂的对象和昂贵的equals()方法.一个对象具有等于1的散列,而另一个对象具有32的散列.如果将两个对象放在具有31个桶的散列表中,它们将最终在同一个桶中(tab).添加第二个(不同的对象)时,必须确保它还没有在表中.您可以equals()立即使用,但这可能会更慢.相反,你首先比较哈希,equals()如果没有必要,避免代价高昂.在这个例子中,哈希是不同的(尽管在同一个桶中)所以equals()没有必要.