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

Question

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

Answer 1

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

实际上,它也没有使用(!).

它实际上使用通过链接哈希表条目实现的单链表.(相比之下,a 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内部数据结构进行了全面改进.在当前实现中,一旦哈希链超过特定长度阈值,实现就切换到使用按键值排序的数组,以及用于链内查找的二进制搜索.那时,哈希链真的更好地被视为集合而不是列表.基于如何添加条目的哈希链的任何残留排序都将丢失.(没关系.无论如何,它没有意义或稳定.)

Answer 2

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

LinkedList中移除是O(n)，遍历并调整指针。arraylist 中的删除可能是 O(n^2) 、遍历元素并移动元素或调整 Arraylist 的大小。

无论哪种情况，包含的复杂度都是 O(n)。

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