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

Question

我读到 HashMap 具有以下实现：

 main array
   ↓
[Entry] → Entry → Entry      ← linked-list implementation
[Entry]
[Entry] → Entry
[Entry]
[null ]

因此，它有一个 Entry 对象数组。

问题：

1. 我想知道在 hashCode 相同但对象不同的情况下，该数组的索引如何存储多个 Entry 对象。

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

原文由 Mercenary 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

因此，它有一个 Entry 对象数组。

不完全是。它有一个数组 Entry 对象 _链_。 HashMap.Entry 对象有一个 next 字段允许 Entry 对象被链接为链表。

我想知道这个数组的索引如何存储多个 Entry 对象，以防 hashCode 相同但对象不同。

因为（如您问题中的图片所示） Entry 对象是链接的。

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

In the LinkedHashMap implementation, the LinkedHashMap.Entry class extends the HashMap.Entry class, by adding before and after fields.这些字段用于将 LinkedHashMap.Entry 对象组装成一个独立的双向链表，记录插入顺序。因此，在 LinkedHashMap 类中，每个条目对象位于两个不同的链中：

• 有许多通过主哈希数组访问的单链接哈希链。这用于（常规）哈希图查找。

• 有一个单独的双向链表，其中包含所有条目对象。它按条目插入顺序保存，并在您迭代哈希图中的条目、键或值时使用。

原文由 Stephen C 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

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;
     }
  }

通过使用 before 和 after - 我们跟踪 LinkedHashMap 中新添加的条目，这有助于我们维护插入顺序。

Before 指的是上一个条目，after 指的是 LinkedHashMap 中的下一个条目。

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

谢谢..！！

原文由 Ankit Mittal 发布，翻译遵循 CC BY-SA 4.0 许可协议