为什么Hashmap内部使用LinkedList而不是Arraylist

Question

当两个对象放置在哈希表的同一存储桶中时，Hashmap内部为什么使用LinkedList而不是Arraylist？

Answer 1

为什么当两个对象放入哈希表中的同一存储桶中时，HashMap内部使用 s LinkedList 而不是 Arraylist？

实际上，它也不使用(！

它实际上使用通过链接哈希表条目来实现的单向链表。 (相比之下，LinkedList是双重链接的，并且它需要列表中每个元素的单独Node对象。

那我为什么要在这里吹毛求疵呢？ 因为它实际上很重要...因为这意味着LinkedList和ArrayList之间的正常权衡不适用。

正常的权衡是：

• ArrayList使用较少的空间，但在最坏的情况下O(N)插入和删除所选元素。

• LinkedList 使用更多空间，但插入和删除选定的元素¹ O(1) 。

但是，对于HashMap入口节点链接形成的私有单链表，空间开销为一个引用(与ArrayList相同(，插入节点的成本O(1)(与LinkedList相同(，删除选定节点的成本也是O(1)(与LinkedList相同(。

仅仅依靠"大O"进行这种分析是可疑的，但是当您查看实际代码时，很明显，HashMap所做的在删除和插入的性能上击败了ArrayList，并且在查找方面具有可比性。 (这将忽略内存局部性影响。 而且它还使用比ArrayList或LinkedList更少的内存用于链接......考虑到已经有内部入口对象来保存键/值对。

但它变得更加复杂。 在Java 8中，他们彻底修改了HashMap内部数据结构。 在当前实现中，一旦哈希链超过某个长度阈值，如果键类型实现Comparable，则实现将切换到使用二叉树表示形式。

<小时 />

^{1 - 即如果您找到了插入/移除点，则插入/删除O(1)。 例如，如果在LinkedList对象的ListIterator上使用插入和删除方法。}

Answer 2

这基本上可以归结为ArrayList和LinkedList的复杂性。在 LinkedList 中的插入(当顺序不重要时(是 O(1(，只需追加到开始。在 ArrayList 中的插入(当顺序不重要时(是 O(N(，遍历到结束，并且还有调整大小开销。

删除在链接列表中是 O(n(，遍历和调整指针。数组列表中的删除可以是 O(n^2( ，遍历元素并移动元素或调整数组列表的大小。

在这两种情况下，包含都将是 O(n(。

当使用 HashMap 时，我们期望 O(1( 操作用于添加、删除和包含。使用 ArrayList，我们将在存储桶中添加、删除操作的成本更高

Answer 3

简短回答：Java使用LinkedList或ArrayList(无论它认为适合数据哪个(。

长答案

虽然排序的ArrayList看起来像是显而易见的方法，但使用LinkedList有一些实际的好处。我们需要记住，LinkedList 链仅在密钥发生冲突时使用。但作为哈希函数的定义：碰撞应该是罕见的

在

极少数冲突的情况下，我们必须在排序数组列表或链接列表之间进行选择。如果我们比较排序的 ArrayList 和 LinkedList，有一些明显的权衡

1. 插入和删除：排序数组列表取 O(n(，但链接列表取常量 O(1(
2. 检索：排序数组列表取 O(logn(，链接列表取 0(n(。

现在，很明显，在插入和删除过程中，LinkedList 比排序后的 ArrayList 更好，但它们在检索时很糟糕。

在冲突较少的情况下，排序后的 ArrayList 带来的价值更少(但开销更大(。但是当冲突更频繁并且冲突的元素列表变得很大(超过某个阈值(时，Java 会将冲突数据结构从 LinkedList 更改为 ArrayList。