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

Question

PS:因为很多人不喜欢讨论JDK实现细节的动机/交换，他们认为JDK工程师有权不告诉任何人就这么做。(关于JDK动机的前一篇文章已经结束)，这个问题纯粹是关于HashMap算法&数据结构和两个不同的链接实现之间的权衡分析/工程师考虑。

众所周知，在实现分离链式法 (每个链都是不同的链接列表)时，我们可以使用散列碰撞来处理HashMap。原则上，当插入带有散列冲突的新元素时，我们可以将其插入链接列表的头或尾。

两种方法都可以使用相同的最差时间复杂度(因为在这两种情况下，我们都必须扫描整个链接列表以检查是否存在相同的密钥，如果没有，则需要插入它。当我们扫描整个链接列表时，我们已经有了头尾。)然而，当我学习算法课程时，我的老师告诉我们，我们更喜欢插入到头部，因为，一般来说，最近插入的元素有更多的机会被查找到。由于这个原因，我已经看到所有带有伪代码或具体实现的算法或数据结构教科书在任何编程语言中都会选择插入到头中。(例如，Alogirhtms，Sedgewick 代码，算法导论，CLRS(第258页)等)

然而，几天前，我在JDK8中看到了源代码JDK8。JDK8选择在尾部中插入，根据我的知识(JDK 8源代码中的line 611, 641, and putVal()方法)，这超出了我的预期。然后，我检查了JDK7，发现JDK7选择插入到头部中，这是我们通常了解到的。(line 402, line 766 and addEntry()方法在JDK 7源代码中)

我的问题：

通常，在实现分离链接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]);

但这两种方式都会很好。