在实现分离链接哈希映射时，更倾向于将节点插入链表的头部还是尾部？

Question

PS: 由于许多SO用户不喜欢讨论JDK实现细节的动机/权衡，他们认为JDK工程师有权在不告诉任何人的情况下进行操作(有关JDK动机的先前帖子已关闭)，因此本问题纯粹是关于HashMap算法和数据结构以及两个不同分离链接实现之间的权衡分析/工程师考虑的问题。

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

两种方法的最坏时间复杂度相同（因为在两种情况下，我们都必须扫描整个链表以检查是否有相同的键，如果没有，则需要插入它。当我们扫描整个链表时，我们已经有了头和尾）。然而，在我学习算法课程时，我的老师告诉我们，我们更喜欢插入到头部，因为通常情况下，最近插入的元素更有可能被查找。因此，我看到所有带有伪代码或任何编程语言中的具体实现的算法或数据结构教材都选择插入到头部。（例如，《算法》，Sedgewick code，《算法导论》，CLRS（第258页）等）

然而，几天前我看到了JDK8中HashMap的源代码。 JDK8选择在尾部插入，这超出了我的预期（在JDK 8源代码的line 611, 641和putVal()方法中）。 然后我检查了JDK7并发现JDK7选择在头部插入，这通常是我们所学的方法。 （在JDK 7源代码的line 402、line 766和addEntry()方法中）

我的问题：

通常，在实现分离链接哈希映射时，将元素插入头部和尾部之间存在什么权衡？是否有任何实际的工程考虑（例如多线程）？（我看到了几个 博客 讨论说，如果没有正确同步，将元素插入头部可能会导致死循环。）

- maplemaple

---

你有没有读过你分享的博客摘要！！原因在那里清楚地说明了！ - Papai from BEKOAIL

链接中没有原子操作，因此无论插入点在哪里，它都会失败。如果需要多线程访问，建议使用ConcurrentHashMap。 - Surt

@PapaifromBEKOAIL 这是错误使用 HashMap 的情况，而不是尾插入修改的原因。改为尾插入后，HashMap 仍然不是线程安全的。 - Poison

Answer 1

总的来说，越近期插入的元素有更大的机会被查找到。

但是这需要附加假设。例如，如果存在一个大的、长寿的结构，可能存储在磁盘上，那么旧元素可能会过时，不再被查找。

在这里，我们谈论的是存储在内存中的结构，通常是短寿命的，用于进行一些计算，并在之后被删除。如果没有关于插入顺序和访问频率之间的假设，就没有理由认为较新的元素更经常被访问。

另外，值插入的位置与并发性无关。在这种情况下，应使用同步的、线程安全的结构，如ConcurrentHashMap，两种方法都可以使用。

话虽如此，JDK 可以任选实现方式。我认为选择更方便、结果更清晰的方式已经被选择了。我猜 JDK 7 会插入到头部，因为这样可以通过避免在表中检查给定哈希是否已经有任何值来减少复杂性。JDK 8 已经显著改变了实现方式。在这里，插入新节点时，我们刚刚到达列表中的最后一个节点，并且对于作者来说这可能看起来更自然。

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

than

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

但两种方法都可以很好地工作。

- Prectron