Java中的HashMap实现.桶指数计算如何工作？

Question

我正在研究HashMapJava 中的实现,并且一度陷入困境.功能
是如何indexFor计算的？

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

谢谢

Answer 1

散列本身是通过hashCode()您尝试存储的对象的方法计算的.

你在这里看到的是计算"桶"来存储基于哈希的对象h.理想情况下,为了避免碰撞,你h可以获得与最大可实现值相同数量的桶- 但这可能对内存要求太高.因此,您通常会有较少数量的铲斗,存在碰撞危险.

如果h是1000,但在底层数组中只有512个桶,则需要知道放置对象的位置.通常,mod操作就h足够了,但这太慢了.鉴于HashMap底层数组总是有多个桶的内部属性2^n,Sun的工程师可以使用它的想法h & (length-1),它用一个由所有数字组成的数字进行按位AND1,实际上只读取n散列的最低位(这是一样的做h mod 2^n,只是多快).

例:

     hash h: 11 1110 1000  -- (1000 in decimal)
   length l: 10 0000 0000  -- ( 512 in decimal)
      (l-1): 01 1111 1111  -- ( 511 in decimal - it will always be all ONEs)
h AND (l-1): 01 1110 1000  -- ( 488 in decimal which is a result of 1000 mod 512)

Answer 2

它不是计算哈希值,而是计算桶.

该表达式在使用时h & (length-1)略微有点,它就像一个位掩码,只返回低位,从而形成一个超快的变量.ANDhlength-1hh % length