爲什麼HashMap要求初始容量是2的冪次？

我正想通過Java的HashMap的源代碼，當我看到下面爲什麼HashMap要求初始容量是2的冪次？

//The default initial capacity - MUST be a power of two. 
static final int DEFAULT_INITIAL_CAPACITY = 16;

我的問題是，爲什麼擺在首位不存在這個要求？我也看到，它允許使用自定義能力創建一個HashMap構造函數將其轉換成二的冪：

int capacity = 1; 
while (capacity < initialCapacity) 
    capacity <<= 1;

爲什麼總是有能力爲二的冪？

此外，當執行自動重新刷新時，到底發生了什麼？哈希函數是否也改變了？

2011-12-02 Sushant

該映射必須計算出哪個內部表索引可用於任何給定鍵，將任何int值（可能爲負）映射到[0, table.length)範圍內的值。當table.length是兩個電源，可以做真的便宜 - 並且是在indexFor：

static int indexFor(int h, int length) { 
    return h & (length-1); 
}

具有不同表的長度，你需要計算餘數，並確保它的非負面的。這絕對是一個微型優化，但可能是一個有效的:)

此外，什麼時候執行自動刷新，究竟發生了什麼？哈希函數是否也改變了？

這對我來說不太清楚你的意思。使用相同的哈希碼（因爲它們只是通過在每個鍵上調用hashCode來計算），但是由於表長度的改變，它們將在表內以不同的方式分佈。例如，當表長度爲16時，5和21的散列碼最終都會存儲在表項5中。當表長度增加到32時，它們將處於不同的條目中。

2011-12-02 06:10:38

正是我在找什麼，謝謝。還有一個疑問，爲什麼Entry表暫時存在，即使它保留了所有數據？ – Sushant

@Sushant：表中的數據*在writeObject中顯式*序列化（這樣所有的空條目都不會被寫出）。使字段瞬態停止來自*也*的正常序列化代碼，將其寫入'defaultWriteObject'的調用中。 –

@JonSkeet h＆（長度-1）如何處理底片？可以說長度= 16和h = -7 – Geek

理想情況實際上是使用素數大小作爲HashMap的支持陣列。這樣你的密鑰將更自然地分佈在陣列中。然而，這與mod分區協同工作，並且隨着每個Java版本的發佈，操作變得越來越慢。從某種意義上說，2種方法的威力是您可以想象的最差的表格大小，因爲糟糕的哈希碼實現更有可能在陣列中產生關鍵的爆炸。

爲此，你會發現在Java的HashMap實現，這是hash(int)，用於補償差哈希碼另一種非常重要的方法。

2011-12-02 07:55:30

是的，這有很大的意義，但作爲一個額外的好處，你可以詳細討論hash（int）函數如何改善原始哈希碼。我看到它採取了幾個比特，但我還沒有完全理解它。 – Sushant

基本上，使用兩種方法的冪使得hashCode的低位是重要的。在糟糕的hashCode實現中，這個差別不會太大（例如：10110111和00000111）。所以隨着所有位的轉移，更高的位變得更加重要。 –

嗯，我明白了......感謝 – Sushant

回答