6

我正在通过 Java 对哈希表的 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 会存储键的哈希值并检查它?

4

2 回答 2

8

因为同一个桶(tab)可以存放因% tab.length操作而具有不同哈希值的项目。首先检查哈希可能是一些性能优化,以避免equals()在哈希不同时调用。

举个例子:假设你有两个复杂的对象,equals()方法很昂贵。一个对象的哈希值等于 1,而另一个对象的哈希值是 32。如果将两个对象都放在一个有 31 个桶的哈希表中,它们最终会在同一个桶中 ( tab)。添加第二个(不同的对象)时,您必须确保它尚未在表中。您可以equals()立即使用,但这可能会更慢。取而代之的是,您首先比较哈希,避免equals()不必要的开销。在这个例子中,哈希是不同的(尽管在同一个桶中),所以equals()没有必要。

于 2012-10-18T19:26:04.717 回答
1

它使访问更快,因为不需要为每次访问重新计算哈希值。这不仅对于显式搜索(在执行之前检查哈希)很重要,而且对于重新哈希也很重要equals

于 2012-10-18T19:34:21.580 回答