Java中的HashMap实现。 水桶指数计算如何工作?

我正在看Java中的HashMap的实现,并坚持一点。
如何计算indexFor函数?

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

谢谢

3 Solutions collect form web for “Java中的HashMap实现。 水桶指数计算如何工作?”

这不是计算散列 ,而是计算

expression式h & (length-1)h使用length-1 AND来执行,这就像一个位掩码,只返回h的低位位,从而形成一个超快的变体h % length

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

你在这里看到的是计算基于哈希h存储对象的“桶”。 理想情况下,为了避免碰撞,你可以得到与h的最大可达值相同的桶数 – 但这可能太过内存要求。 因此,你通常有一个桶的数量较less,有碰撞的危险。

如果h是1000,但在底层数组中只有512个存储桶,则需要知道将对象放在哪里。 通常情况下,对hmod操作就足够了,但这太慢了。 考虑到HashMap的内部属性,底层数组总是具有等于2^n的桶2^n ,Sun的工程师可以使用h & (length-1) ,它将按位进行AND运算, s,实际上只读取散列的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) 

它正在计算存储条目(键值对)的哈希映射的桶。 bucket id是hashvalue/buckets length

哈希映射由桶组成; 对象将被放置在基于桶标识的这些桶中。

任何数量的对象实际上都可以基于它们的hash code / buckets length值落入同一个桶中。 这被称为“碰撞”。

如果许多对象落入同一个桶中,searchequals()方法将被调用以消除歧义。

碰撞的次数与桶的长度间接成正比。

  • 实现一个HashMap
  • 如何使用Gson将JSON转换为HashMap?
  • 如何在Java中通过键sortingMap值
  • HashSet和HashMap的区别?
  • 哈希映射和空值?
  • 数组哈希ruby
  • 根据键对hashmap进行sorting
  • 如何使用JavaScript / JQuery创build一个简单的地图