当我们实现单独的链式HashMap时，更喜欢将节点插入到链表的头部或尾部？

Question

PS： 鉴于关于 JDK 实现细节的动机或权衡的讨论经常在 StackOverflow 上遇到阻力，普遍认为 JDK 工程师有权独立做出决策（之前关于 JDK 动机的帖子的结束证明了这一点） ，我想澄清的是，这个问题严格集中在 HashMap 的算法和结构方面，特别是在两个单独的链接实现（头部插入和尾部插入）之间进行选择时涉及的分析和工程考虑。

在 separate-chaining HashMap 中，冲突是通过链接列表中的链接条目来管理的。当发生冲突时，新元素可以插入到链表的头部或尾部。 两种方法具有相同的最坏时间复杂度，因为需要对列表进行全面扫描才能识别重复项或插入点。但是，传统智慧和算法教育（例如，Sedgewick 算法源、算法简介、CLRS p.258）建议最好在头部插入，因为较新的元素更有可能很快被访问。

奇怪的是，虽然 JDK7 的

HashMap

（

JDK 7 源代码

中的第 402、766 行和 addEntry() 方法）通过在头部插入来遵循此约定，但 JDK8 切换到尾部插入（第 611、641 和

putVal()

JDK 8 源代码中的方法）。

我的问题是： 在分离链式 HashMap 中，头部插入和尾部插入之间的权衡是什么？是否存在可能影响此选择的实际工程考虑因素（例如多线程问题）？我遇到过一些讨论（例如，这个博客），表明如果同步不正确，在头部插入可能会导致死循环。任何人都可以提供有关此主题的见解或更多资源吗？

注意：我正在寻求深入的技术分析以及任何相关的经验或资源。感谢您的贡献！

Answer 1

一般来说，最近插入的元素有更多的机会被查找

如果有额外的假设，这可能是正确的。例如，如果有一个大型、长期存在的结构，可能存储在磁盘上，则较旧的元素可能“过时”并且不再查找。

这里我们讨论的是存储在内存中的结构，通常是短暂的，用于进行一些计算并在之后删除。如果没有关于插入顺序和访问频率之间的关系的假设，则没有理由假设最近的元素被更频繁地访问。

此外，在哪里插入值与并发性无关。在这种情况下，应该使用像

ConcurrentHashMap

这样的同步、线程安全的结构，并且这两种方法都可以工作。

话虽如此，JDK 可以以任何一种方式实现它。我认为已经做出了更方便且代码更清晰的选择。我猜想 JDK 7 会插入到头部，因为它避免了检查表中给定哈希值是否已经存在的必要性，从而降低了复杂性。 JDK 8 显着改变了实现。这里当插入一个新节点时，我们刚刚到达列表中的最后一个节点，对于作者来说这样写可能看起来更自然

if ((e = p.next) == null) {
    p.next = newNode(hash, key, value, null);

比

if ((e = p.next) == null) {
    tab[i] = newNode(hash, key, value, tab[i]);

但这两种方法都可以。