indexFor在散列表？

Question

只是試圖通過查看代碼讓我的頭在Java HashMap的運作。當添加的元素，則發生以下情況：

1. 用於密鑰的哈希碼是得了
2. 一個散列函數對結果
3. 施加indexFor上的2的結果應用該方法這使在適當的桶中首次輸入。然後迭代桶中的鏈接列表 - 找到結尾並添加元素。

的implementation of indexO f是：

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

我無法理解的伎倆在IndexOf方法回事。任何人都可以解釋嗎？

謝謝。

Answer 1

這是可行的，因爲Java HashMaps總是有一個容量，即桶的數量，爲2的乘方。讓我們使用256的容量，它是0x100，但它可以與2的任何冪一起工作。 2的冪產生按位所需的精確位掩碼，並用散列獲得適當的存儲區索引，範圍爲0至length - 1。

256 - 1 = 255 
0x100 - 0x1 = 0xFF 

例如， 257（0x101）的散列值按0xFF逐位遞增以產生1的桶號。