關於Java HashMap的實現

爲什麼容量必須是2或2？爲什麼在indexFor函數中使用「&」？爲什麼重新計算散列函數中的散列而不是直接使用鍵的散列碼？關於Java HashMap的實現

我認爲這個實現和「算法介紹」的描述之間有一些重要的區別。

「>>>」是什麼意思？

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); 
}

任何人都可以給我一些指導？我很感激如果有人能解釋哈希算法。非常感謝！

來源

2012-04-03 lingguang1997

我知道使用「＆」，密鑰可以映射到有限的插槽。對哈希映射中碰撞的影響如何？ – lingguang1997 2012-04-03 21:30:07

'>>>'是無符號右移。 Java中的常規'>>'將保留並傳播符號位，並保留負數。發生移位時，>>>將填充符號位。 – 2012-04-04 16:10:48

這是一個性能優化。將散列碼映射到表索引的常用方法是

table_index = hash_code % table_length;

%運算符很貴。如果table_length是2的冪，則計算：

table_index = hash_code & (table_length - 1);

等效於（多）更昂貴的模運算。

來源

2012-04-03 21:34:28

這就是爲什麼學習在舊處理器上進行彙編代碼是一個好主意。 – biziclop 2012-04-03 21:53:56

危險威爾羅賓遜！ 50％的散列碼是負數，所以'hash_code％table_length'可能是負數，導致出現'ArrayOutOfBoundsException'。你需要使用'Math.abs（hash_code％table_length）'得到一個可用的（即安全的）索引 – Bohemian 2012-04-03 23:20:15

@Bohemian - 是的，負數是一個額外的複雜因素。這是第二種方法的另一個優點，對於負面的哈希碼值，它可以很好地工作。 – 2012-04-04 00:18:22

不理睬幕後的男人。實際的算法無疑是開發人員「感覺良好」的一種組合，修復了一些奇怪的退化情況，以及簡單的傳統（用戶經常開發不明確的依賴關係）的組合。

並注意這一點：

* Applies a supplemental hash function to a given hashCode, which 
* defends against poor quality hash functions. This is critical 
* because HashMap uses power-of-two length hash tables, that 
* otherwise encounter collisions for hashCodes that do not differ 
* in lower bits. Note: Null keys always map to hash 0, thus index 0.

網：只要它的工作原理和性能還是不錯的，你不在乎。

來源

2012-04-03 21:46:02

感謝大家的回答。他們回答了我的問題。 – lingguang1997 2012-04-04 16:03:33

關於Java HashMap的實現

回答

相關問題