jdk1.8中HashMap源码有一些疑问.

在Node链表长度超过7的时候会执行treeifyBin方法进行树的转换.
但是在treeifyBin方法里又判断了tab(也就是放Node链表的数组)的长度不超过64时, 仅执行resize

我想问的是, 链表的长度和tab的length有毛关系?
为什么链表超长了,需要resize tab?


以下为部分源码

// bincount 就是链表的长度.  TREEIFY_THRESHOLD默认为8
if (binCount >= TREEIFY_THRESHOLD - 1)
    treeifyBin(tab, hash);

// MIN_TREEIFY_CAPACITY 默认为64
if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
    resize();

3个回答

仅仅是因为设计的人觉得长度小于64时没必要进行树的转换。。先进行resize(), resize() 之后,可能就达不到转化为树的要求啦。。。

要理解这个, 你需要知道他是怎么计算tab中位置的,

index = (table.length - 1) & hash

以上会涉及到tab长度需要是2的次幂。。 不过在此你可以认为是取模, 虽然不太一样。

所以, table的长度增加之后, index是有可能会变化的:比如hash值是1和9的两个值, 在长度为8的table上都是在第一个索引中的, 但是,如果长度扩为16, 则他们就不在一个索引中了。

如不理解, 可以看我的文章

你应该很了解HashMap的数据结构是数组加链表,数组也可以称为桶的概念,引入红黑树的目的是为了解决hash冲突的问题,能够提高检索落在同一个桶中key的效率,但是这种提高相对于直接从数组中取值还是比较低的,代码的意思是如果数组长度低于64,就进行resize,这样会重新分布不同的数据,使得数据更加离散。假如数组长度本来只有2,直接在其中一个里面用红黑树,还不如直接扩大数组的size,这样索引效率会更高。当然具体为什么选择64当做数组的长度边界就不太理解了,希望能帮到你,谢谢。

我记得,这个是hashMap,中新增一个特性,主要是为了解决类似hashCode冲突,还有hashMap,加锁,效率提升的相关的问题。因为之前
的版本,加锁,相当于全部锁的那种,现在不是分段,加锁的,那种,你懂的。好像是这个样子

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐