LinkedHashMap的内部实现与HashMap实现有何不同？

Question

我读到HashMap具有以下实现:

main array 
   ?
[Entry] ? Entry ? Entry      ? linked-list implementation
[Entry]
[Entry] ? Entry
[Entry]
[null ]

因此,它有一个Entry对象数组.

问题:

1. 我想知道如果相同的hashCode但不同的对象,这个数组的索引如何存储多个Entry对象.

2. 这与LinkedHashMap实施有何不同？它是map的双链表实现,但它是否像上面那样维护一个数组,它如何存储指向下一个和前一个元素的指针？

Answer 1

HashMap不维护插入顺序,因此不维护任何双向链表.

LinkedHashMap最突出的特点是它维护键值对的插入顺序.LinkedHashMap使用双重链接列表来执行此操作.

LinkedHashMap的输入看起来像这样 -

  static class Entry<K, V> {
     K key;
     V value;
     Entry<K,V> next;
     Entry<K,V> before, after;        //For maintaining insertion order    
     public Entry(K key, V value, Entry<K,V> next){
         this.key = key;
         this.value = value;
         this.next = next;
     }
  }

通过使用之前和之后 - 我们在LinkedHashMap中跟踪新添加的条目,这有助于我们维护插入顺序.

在引用之前的条目之前和之后引用LinkedHashMap中的下一个条目.

有关图表和分步说明,请参阅http://www.javamadesoeasy.com/2015/02/linkedhashmap-custom-implementation.html

谢谢..!!

Answer 2

所以,它有一个Entry对象数组.

不完全是.它有一系列Entry对象链.一个HashMap.Entry对象有一个next字段,允许Entry对象被链接的链接列表.

我想知道Entry如果相同的hashCode但不同的对象,这个数组的索引如何存储多个对象.

因为(如问题中的图片所示)Entry对象被链接.

这与LinkedHashMap实施有何不同？它是map的双链表实现,但它是否像上面那样维护一个数组,它如何存储指向下一个和前一个元素的指针？

在LinkedHashMap实现中,LinkedHashMap.Entry类HashMap.Entry通过添加before和after字段来扩展类.这些字段用于将LinkedHashMap.Entry对象组装到记录插入顺序的独立双向链表中.因此,在LinkedHashMap类中,条目对象位于两个不同的链中:

• 通过主哈希数组访问的单链接哈希链,和

• 在条目插入顺序中保留的所有条目的单独双向链接列表.

Answer 3

快来看看自己.为了将来参考,你可以谷歌:

java LinkedHashMap源码

HashMap使用LinkedList来处理collissions,但之间的差HashMap并且LinkedHashMap是LinkedHashMap具有可预测迭代顺序,这是通过一个额外的双链表,这通常保持键的插入顺序来实现的.例外情况是重新插入密钥时,在这种情况下它会返回到列表中的原始位置.

作为参考,迭代a LinkedHashMap比迭代a 更有效HashMap,但LinkedHashMap内存效率更低.

如果从我上面的解释中不清楚,散列过程是相同的,那么你可以获得普通散列的好处,但是你也可以获得上面所述的迭代优势,因为你使用了一个双向链表来保持Entry对象的顺序,这与在冲突的哈希过程中使用的链表无关,如果不明确的话.

编辑:(响应OP的评论):
A HashMap由数组支持,其中一些插槽包含Entry处理冲突的对象链.要遍历所有(键,值)对,您需要遍历数组中的所有插槽然后通过LinkedLists; 因此,您的总时间将与容量成比例.

使用a时LinkedHashMap,您需要做的只是遍历双向链表,因此总时间与大小成正比.