V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Leexiaobu
V2EX  ›  Java

HashMap 在 jdk 1.7 中为什么选的头插法,而不是尾插法

  •  
  •   Leexiaobu · 2021-01-12 18:18:29 +08:00 · 2506 次点击
    这是一个创建于 493 天前的主题,其中的信息可能已经有所发展或是发生改变。

    在我看来,头插法和尾插法都要遍历一遍链表啊,应该不是效率问题吧.

    12 条回复    2021-01-15 14:53:19 +08:00
    VincentWang
        1
    VincentWang  
       2021-01-12 18:32:25 +08:00
    有一种说法是:缓存的时间局部性原则 (新插入的数据可能会更早用到)
    Leexiaobu
        2
    Leexiaobu  
    OP
       2021-01-12 19:37:50 +08:00   ❤️ 1
    我刚看了遍源码,得出一个结论,感觉还挺像的
    插入时需要判断是否重复,此时要遍历一遍链表,
    如果采用尾插法,需要将尾节点保存起来,传入后面的 addEntry 的方法中
    addEntry 会判断是否需要扩容,如果扩容的话,待插入节点的下标就需要重新计算,
    这样之前保存的尾节点就不一定正确,需要在重新计算一次尾节点,
    所以说使用头插法效率会高一些
    Leexiaobu
        3
    Leexiaobu  
    OP
       2021-01-12 19:38:34 +08:00
    @VincentWang 刚刚不知道如何回复。
    qwerthhusn
        4
    qwerthhusn  
       2021-01-12 20:41:26 +08:00
    插头插尾都无所谓,因为链表长度达到 8 (好像是 6,忘记了)的时候,就变成红黑树了,
    长度个位数的链表,咋遍历都不会影响性能
    ssynhtn
        5
    ssynhtn  
       2021-01-12 21:04:53 +08:00 via Android
    因为简单啊,怎么简单怎么来呗
    emSaVya
        6
    emSaVya  
       2021-01-12 21:40:07 +08:00
    头插有概率形成死循环 1.8 以后改成尾插
    cco
        7
    cco  
       2021-01-13 09:31:28 +08:00
    @qwerthhusn 这不是 1.8 后才有的么?
    Leexiaobu
        8
    Leexiaobu  
    OP
       2021-01-13 09:34:00 +08:00
    @qwerthhusn,在 1.8 之后确实不用考虑这个问题了,但是我当时奇怪的是 1.7 为什么用的头插法。
    @emSaVya 对,就是因为头插法会形成环形链表,所以我才好奇为什么不用尾插法,当时我以为效率一样,后面发现其实是不一样的。
    ffhigh
        9
    ffhigh  
       2021-01-13 10:42:53 +08:00
    如果 1.7 只改尾插, 不改扩容机制。 也不会形成环么?
    751327
        10
    751327  
       2021-01-15 14:49:41 +08:00
    可能是在扩容迁移元素的过程中,用头插法更快
    751327
        11
    751327  
       2021-01-15 14:50:57 +08:00
    1.7 是一个元素一个元素迁移的,用尾插法就要遍历到链表尾部再插入
    751327
        12
    751327  
       2021-01-15 14:53:19 +08:00
    扩容转移元素不需要遍历一遍链表哦
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2701 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 14:19 · PVG 22:19 · LAX 07:19 · JFK 10:19
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.