2017-07-29 36 views
0

我知道這個問題已經被問到stackover流的時間數。但我無法找到我懷疑的答案。在HashMap中如何獲取桶號

當我們將鍵值對存儲在散列表中時,HaspMap將查找鍵的散列碼並將其存儲在標識符爲鍵的散列碼的存儲區中。

一個存儲桶可以有多個鍵值對。如果一個存儲桶可以保存多對鍵值,那麼這些鍵之間的關係是不相似的,但仍然共享相同的散列碼。

同一個桶的不同密鑰如何具有相同的哈希碼?我可以知道它的工作原理嗎?

+0

因爲這就是散列碼的用途。 – EJP

回答

1

同一個存儲桶的不同密鑰如何具有相同的散列碼...?

hashCode()合同並未說明兩個不相等的對象可能沒有相同的哈希碼。

如果兩個對象具有相同的哈希碼,這些都是在同一個桶,但HashMap不僅在hashCode()靠,這也依賴於equals()方法來評估,如果兩個鍵是平等的。
這意味着地圖會在桶的每個元素中查找使用輸入鍵在equals()方面元素是否等於。
如果輸入密鑰是equals()與元素,這些是等於。
這就是爲什麼建議減少散列碼衝突的原因,因爲它有利於通過散列查找進行迭代查找。

這裏是HashMap(Java 8)中定義的私有getNode()方法檢索從地圖的關鍵:

final Node<K,V> getNode(int hash, Object key) { 
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k; 
    if ((tab = table) != null && (n = tab.length) > 0 && 
     (first = tab[(n - 1) & hash]) != null) { 
     if (first.hash == hash && // always check first node 
      ((k = first.key) == key || (key != null && key.equals(k)))) 
      return first; 
     if ((e = first.next) != null) { 
      if (first instanceof TreeNode) 
       return ((TreeNode<K,V>)first).getTreeNode(hash, key); 
      do { 
       if (e.hash == hash && 
        ((k = e.key) == key || (key != null && key.equals(k)))) 
        return e; 
      } while ((e = e.next) != null); 
     } 
    } 
    return null; 
} 

你可以看到地圖的關鍵的輸入鍵只有在符合其hashcode()值是相同的,這些是「equals()」。

+0

有道理.. !!你能否解釋一下你的陳述「它支持迭代查找哈希」?我沒有得到它。其次,是什麼讓不同的密鑰產生相同的哈希碼..?第三,我們如何獲得HashMap中現有的哈希碼列表,而不是鍵?感謝:) – LearnJava

+0

「什麼使不同的密鑰產生相同的哈希碼」這是一個簡單的計數問題。只有2^32個不同的哈希碼,但是可以哈希多個不同的對象。所以很明顯,一些碰撞必須發生。 – Henry

+1

1.如果在同一個桶中有很多元素,映射必須遍歷所有元素,以確定輸入鍵是否與桶中的一個元素相等(我添加了虛幻的代碼)。 2.實現'hashCode()'和'int'範圍的方式。即使它設計得很好,可以在物體之間提供良好的分佈,但它可能並不完美。它往往是速度和分配之間的折衷。有幾次碰撞通常不是問題。頻繁發生足夠的碰撞是。當然。檢索密鑰('keySet()')並在每個密鑰上調用'hashCode()'。 – davidxxx