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()
方法中)
我的问题:
通常,在实现分离链接哈希映射时,将元素插入头部和尾部之间存在什么权衡?是否有任何实际的工程考虑(例如多线程)?(我看到了几个 博客 讨论说,如果没有正确同步,将元素插入头部可能会导致死循环。)