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

Why Hashmap internally uses LinkedList instead of Arraylist,when two objects having same hashcode are placed into the same bucket?

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

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