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

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

实际上，它不使用任何一个（！）。

它实际上使用通过链接哈希表条目实现的单链表。（相比之下，a 是双重链接的，它需要为列表中的每个元素使用单独的对象。LinkedListNode

那么，我为什么要在这里挑剔呢？因为它实际上很重要...因为这意味着 和 之间的正常权衡不适用。LinkedListArrayList

正常的权衡是：

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

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

但是，在通过将条目节点链接在一起形成的私有单链表的情况下，空间开销为一个引用（与相同），插入节点的成本为（与相同），并且删除所选节点的成本也是（与相同）。HashMapArrayListO(1)LinkedListO(1)LinkedList

仅依靠“大O”进行此分析是值得怀疑的，但是当您查看实际代码时，很明显，在删除和插入的性能方面，什么与查找相当。（这忽略了内存局部性影响。而且它使用更少的内存进行链接，而不是使用或曾经使用过的内存......考虑到已经存在内部输入对象来保存键/值对。HashMapArrayListArrayListLinkedList

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

^{1 - 即插入/删除是O（1），如果你已经找到了插入/删除点。例如，如果您正在使用 LinkedList 对象的 ListIterator 上的插入和删除方法。}

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

删除在LinkedList中为O（n），遍历和调整指针。数组列表中的删除可以是 O（n^2），遍历到元素并移位元素或调整数组列表的大小。

在任一情况下，包含数都将是 O（n）。

当使用HashMap时，我们将期望O（1）操作进行添加，删除和包含。使用ArrayList，我们将在存储桶中产生更高的添加，删除操作的成本