爲什麼哈希錶店在Java中的表中的鍵的哈希值

Question

我正想通過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存儲密鑰的哈希值並檢查它？

Answer 1

由於% tab.length操作，同一個存儲桶（tab）可以存放具有不同散列的項目。如果哈希值不同，則首先檢查哈希可能會進行一些性能優化，以避免調用equals()。

舉一個例子：假設你有兩個複雜的對象，其代價是equals()。一個對象的散列值等於1，而另一個對象的散列值爲32.如果將這兩個對象放在一個具有31個存儲桶的散列表中，它們將最終在同一個存儲桶中（tab）。添加第二個（不同的對象）時，您必須確保它尚未在表格中。您可以立即使用equals()，但這可能會變慢。相反，你首先比較散列，避免代價高昂的equals()，如果不是必要的話。在這個例子中哈希是不同的（儘管在同一個桶中），所以equals()是沒有必要的。

Answer 2

它使訪問速度更快，因爲散列值不需要爲每次訪問重新計算。這不僅對於顯式搜索（在執行equals之前檢查哈希）而且對於重新哈希來說也很重要。