关于java:hashMap源码算法问题

40次阅读

共计 710 个字符,预计需要花费 2 分钟才能阅读完成。

在读 HashMap 源码的时候,有些位运算的目标和原理不是很分明,顺便记下来以便日后温习应用。
1 为什么 hashMap 内 hash 办法会对原对象 hash 值右移 16 位?
`static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);// 这里对 key,hash 值右移了 16 位
}`
hash 值位 int 类型,长度位 32bit,右移 16 位后再与本身的 hash 值进行与操作,会进步 hash 值计算方法的复杂度,进步 hashMap 中 hash 值的散列水平,使其更平均的散布。
2 扩容拆分链表时为什么是 hash 值与原有数组的大小进行并操作(寄存下标是等于对象 hash 值与现有数组长度减一进行取余的操作)?
`if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else loTail.next = e;
loTail = e;
}`
此操作是为了确定链表的节点元素在新数组中的下标地位,若等于 0 则地位不变,如果不为 0,则地位位当初所处的地位下标 + 原有数组长度,上面来剖析一下原理。
首先来明确一个概念,hashmap 中元素的寄存地位与数组下标的关系是:

数组下标 = 元素的 hash 值 &(数组长度 -1)而且 hashmap 的长度肯定是 2 的 n 次方。那么原有数组长度的二进制数能够这样示意 1 0 0 0 0
扩容后数组长度为                   1 0 0 0 0 0
原有数组长度减一后为                 0 1 1 1 1
现有数组长度减一后为               0 1 1 1 1 1
那么原有数组中元素寄存地位下标只与后四位无关,扩容后只与后五位无关,那么,如果只与第五位进行与操作的话,就能够判断出该元素寄存地位是否须要扭转了。

正文完
 0