sy3345036
非攻喵
采纳率100%
2018-12-19 16:13 阅读 791
已采纳

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条回答 默认 最新

  • 已采纳
    weixin_37139197 阿进的写字台 2018-12-19 11:36

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

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

    index = (table.length - 1) & hash
    

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

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

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

    点赞 评论 复制链接分享
  • D939030515 飘落的秋风 2018-12-19 11:34

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

    点赞 3 评论 复制链接分享
  • lixiaozhen007 lixiaozhen007 2018-12-19 09:03

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

    点赞 评论 复制链接分享

相关推荐