LinkedHashMap vs HashMap!= LinkedList vs ArrayList

Question

我已经读过LinkedHashMap比HashMap具有更快的迭代速度,因为它的元素彼此双重链接.此外,因此,插入或删除元素时LinkedHashMap较慢.大概是因为这些链接也需要更新.

虽然我可以看到LinkedList与ArrayList的类比,因为LinkedList的元素也是双向链接的,我读到它迭代的速度比ArrayList 慢,并且插入和删除时间更快.

为什么是这样？也许我在某个地方犯了错误？

干杯!

Answer 1

这个比喻不起作用.LinkedList和ArrayList是List的两个不相关的实现.然而,LinkedHashMap与HashMap的数据结构相同,但是将LinkedList编织到其中以使迭代更快更一致.

LinkedHashMap迭代比HashMap迭代更快的原因是HashMap迭代必须遍历所有桶,甚至是空桶.LinkedHashMap有一个指向数据的列表这一事实意味着它可以跳过空桶.LinkedHashMap中的列表是一个链表,因为删除时间保持不变(而不是O(n),如果它是一些arrray支持的列表).

Answer 2

链接列表迭代运行时(访问每个元素)在理论上与数组列表相同.两者都需要O(n)(Big-O表示法)运行时.但是,因为数组的内存分配是在连续的内存块上(链接列表元素是单独分配的,并且可能在内存中的任何位置),所以缓存生效.