容量和indexFor在Java中的Hashmap

雖然要通過Java HashMap的源代碼，我們可以看到一個鍵的第一桶，採用如下方法確定：容量和indexFor在Java中的Hashmap

static int indexFor(int h, int length) { //h = hash of key 
    return h & (length-1);    //length = capacity of array at 
}          //   current time

按我的理解，如果初始大小是16（length-1 = 15 = 1111），並且如果密鑰的生成散列是108378（1 10100111 01011010），則 indexFor()方法將返回10（1010）。

現在，說一些額外的後容量已經改變爲32。現在，如果我要搜索密鑰（使用散列108378），它將再次使用相同的indexFor()方法檢查存儲區。現在h & (length-1)代碼片段將返回26。（108378 & 31）。

我的問題是，如果表得到調整大小，這個get方法將如何找到正確的桶？

來源

2017-08-02 Anirban B

在調整表格大小時，桶會重新構造。 – shmosel

當調整表的大小時，將重新計算和移動鍵的所有散列值。 – 4castle

當達到負載因數的最大閾值時，會發生稱爲重新刷新的過程，並將所有元素移動到新表中。

當在散列表中的條目的數量超過了負載率和電流容量的產品，哈希表是 重新散列（即，內部數據結構被重建），從而使哈希表大約有兩倍的桶數。

設置其初始容量時應考慮地圖中的條目數及其加載因子，因此應儘可能減少重新散列操作的次數。

來源

2017-08-02 23:21:00

謝謝。延伸你的答案，我有另一個問題。如果已經應用了鏈接，則在重新哈希時，是否還要爲鏈接節點重新計算bucket＃？或者只是鏈接節點的起始節點？ –

對於所有值重新進行計算，因爲之前保存相同水桶位置的節點現在可以分佈在不同的水桶位置。 –

如果表格被調整大小，那麼長度參數將改變，並且indexFor方法將返回不同的值。在調整表格大小時，表格中當前的值必須移動到新表格中，因此將爲每個值計算新索引。

來源

2017-08-02 23:16:18

好的...我明白了。謝謝。但令人驚訝的是，當它調整大小時，時空複雜。在手術過程中，我不相信O（n）的複雜性。 –

@AnirbanB在rehash期間，時間複雜度爲O（n），因爲舊哈希表中的所有元素都必須計算一個新的哈希代碼，然後計算一個索引，然後將其放在新表中。它不如添加單個元素那麼有效，但它仍然是O（n）。 –

是的......只是意識到它實際上是O（n）。但平均情況是O（1）。然而空間複雜度比O（n）大得多。 –

您看到的length不是map.size()報告的值。它是一個表示哈希表大小的內部長度。在密集填充的哈希映射中，該長度可以小於size()，或者在稀疏填充的哈希映射中可能大於size()。它越小，對於h & (length-1)就會發現具有相同評估的密鑰越多，這意味着更多的密鑰將被分組到桶中。

在一定的時間映射決定length太小，造成了太多的衝突，（在每個桶太多的按鍵，），所以它重組地圖，重新分配散點（希望儘可能少見）表更大，重新計算所有散列值，並重新分配桶中的密鑰，以便h & (length-1)對所有散列值仍然正確。

來源

2017-08-02 23:26:17

容量和indexFor在Java中的Hashmap

回答

相關問題