LinkedHashMap与HashMap!=LinkedList与ArrayList

这种类比是行不通的。LinkedList和ArrayList是列表的两个不相关的实现。然而,LinkedHashMap与HashMap是相同的数据结构,但是它包含一个LinkedList以使迭代更快、一致。

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

链表迭代运行时间(访问每个元素)“理论上”与数组列表相同。两者都需要O(n)( Big-O Notation )运行时。但是,由于数组的内存分配是在一个连续的内存块上进行的(链表元素是单独分配的,并且可能在内存中的任何位置),所以缓存开始生效。

一些细节:

LinkedHashMap的迭代器顺序与映射中的插入顺序相同。因此LinkedList部分只需要在末尾“insert”(对于跟踪尾部的链表是O(1)),Map部分只需要执行一个映射insert,即O(1)。一般的链表插入是O(N),而ArrayList插入必须通过数组将内容复制到1个槽上,然后才能进行插入。

数组在内存中是连续的,下一个元素只是当前元素的内存位置随元素大小的增加而增加。

对于双链表,在数组中的任何位置插入都非常快,因为只需要更改前面和后面元素的引用。另一方面,数组速度较慢,因为在任何点插入都会导致复制整个数组,以便为新元素腾出空间。当没有足够的连续内存分配给数组和新添加的元素时,即使附加一个元素也会导致复制整个数组。

arraycopy() 也许,双链表的插入速度总是更快。因为HashMaps很少迭代,并且依赖于插入和顺序,所以双链表可能会提高它的性能。