爪哇HashMap中執行哈希碼問題

通過Java HashMap中這裏的實施尋找：http://www.docjar.com/html/api/java/util/HashMap.java.html我注意到以下：爪哇HashMap中執行哈希碼問題

使用的內部數據結構是數組，其在每個索引存儲參照鏈接的第一個條目名單。數組索引基於密鑰的哈希碼，鏈表則表示該特定哈希碼的存儲桶。我發現有趣的是方法indexFor（int h，int length），對於給定的鍵，它決定了數組中要查找的桶。但是實現返回h &（長度爲1）在某種意義上看起來很奇怪對於與給定數組索引不一致的不確定數量的哈希碼，該方法將返回0.因此，無論您爲對象實現何種唯一的哈希碼，數組中的0存儲桶最有可能充滿對象，因此你不會從獨特的哈希碼應該爲你提供什麼，這是更快的數據訪問。

我錯過了什麼嗎？

克里斯蒂安

來源

2012-10-05 cristian.petroaca

你缺少從HashMap的源代碼下面的Javadoc：

/** 
* The table, resized as necessary. Length MUST Always be a power of two. 
*/ 
transient Entry<K,V>[] table;

這意味着table.length-1永遠是1的序列。

來源

2012-10-05 14:30:04 ddimitrov

是的，就是這樣。謝謝 –

這次我有另一個與哈希表類有關的問題。在這個實現中http://www.docjar.com/html/api/java/util/Hashtable.java.html中，數組中的存儲區索引使用key.hashcode％array.length進行計算。這裏array.length不是兩個冪。假設我們有一個長度爲11的初始數組，我們首先插入一個hashcode = 1的密鑰，那麼數組索引就是1，然後我們插入另一個hashcode = 12的密鑰，這樣數組索引也就是1。這是否意味着具有不同散列碼的2個鍵的對象將被存儲在同一個桶中？ –

正確，但如果你指定了一個好的初始值（即15），調整大小公式'oldCapacity * 2 + 1'將保持良好。在這些情況下，素數是一個典型的推薦值，並且它會工作得很好。如果你指定了蹩腳的初始大小，調整大小會更好。最後，它不是完美的 - 沒有數據結構。如果你關心效率 - 我建議你檢查一下：http：//labs.carrotsearch.com/hppc.html - 它給你足夠的繩索去做你想做的事情:-) – ddimitrov

我不明白你相信問題是什麼。

該h & (length - 1)是一種簡單的方法來計算h % n其中n是兩個冪。在我的理解中，沒有任何理由爲什麼h % n應該給出不自然的大量零。

來源

2012-10-05 14:29:55 parsifal

爪哇HashMap中執行哈希碼問題

回答

相關問題