为什么在HashMap中计算哈希码的索引(Why index of hashcode is calculated in HashMap)

为什么在HashMap中计算哈希码的索引(Why index of hashcode is calculated in HashMap)

我正在检查HashMap实现，并在其中看到了计算后的哈希值，计算了哈希值的索引，如下所示： int i = indexFor(hash, table.length); ，并将其用作底层地图的索引。

/** * Returns index for hash code h. */ static int indexFor(int h, int length) { return h & (length-1); }

我搜索没有找到任何解释我的问题，为什么再次计算哈希索引，用作底层数据结构的最终索引。 与使用哈希作为索引相比，它有什么优势。

我知道它只是按位而已，但我想知道它为什么这样做。

I was checking implementation of HashMap and in its put I see the after calculating the hash, index of the hash is calculated, like this int i = indexFor(hash, table.length);, and it is used as index of the underlying map.

/** * Returns index for hash code h. */ static int indexFor(int h, int length) { return h & (length-1); }

I searched didn't find any explanation to my question that why again index of the hash is calculated which is used as final index of the underlying data structure. What is the advantage of it over using the hash as index.

I know it is nothing but bitwise AND but I want to know why it is done like this.

最满意答案

对象的哈希码可以是-2 ^ 31和2 ^ 31-1之间的任何int值。 哈希表使用的基础数组不会具有相同的范围（没有负数，对于一个，可能不是那么大），因此必须有一些操作将哈希代码从其原始范围转换为0和0之间的一个数组的长度。

由于HashMap总是使用大小为2的幂数组（例如16,32,64等），因此使用&是将散列代码映射到指示符的有效方法，因为它只是简单地去除其他位。 其他哈希表实现可能会使用模相似的效果，如果它们不将数组大小限制为2的幂。

另见https://en.wikipedia.org/wiki/Hash_table#Collision_resolution

An object's hash code can be any int value, between -2^31 and 2^31-1. The underlying array used by a hash table is not going to have the same range (no negatives, for one, and likely not that large), therefore there must be some operation transforming the hash code from its original range to one between 0 and the array's length.

Because HashMap always uses arrays sized to a power of 2 (e.g. 16, 32, 64, etc.) using & is an efficient way to map hash codes to indicies, as it simply strips the other bits. Other hash table implementations might use modulo to similar effect, if they don't limit their array sizes to powers of two.

See also https://en.wikipedia.org/wiki/Hash_table#Collision_resolution