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

How is the internal implementation of LinkedHashMap different from HashMap implementation?

提问by Mercenary

I read that HashMap has the following implementation:

我读到 HashMap 有以下实现：

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

So, it has an array of Entry objects.

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

Questions:

问题：

1. I was wondering how can an index of this array store multiple Entry objects in case of same hashCode but different objects.

2. How is this different from LinkedHashMapimplementation? Its doubly linked list implementation of map but does it maintain an array like the above and how does it store pointers to the next and previous element?

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

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

采纳答案by Stephen C

So, it has an array of Entryobjects.

所以，它有一个Entry对象数组。

Not exactly. It has an array of Entryobject chains. A HashMap.Entryobject has a nextfield allowing the Entryobjects to be chained as a linked list.

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

I was wondering how can an index of this array store multiple Entryobjects in case of same hashCode but different objects.

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

Because (as the picture in your question shows) the Entryobjects are chained.

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

How is this different from LinkedHashMapimplementation? Its doubly linked list implementation of map but does it maintain an array like the above and how does it store pointers to the next and previous element?

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

In the LinkedHashMapimplementation, the LinkedHashMap.Entryclass extends the HashMap.Entryclass, by adding beforeand afterfields. These fields are used to assemble the LinkedHashMap.Entryobjects into an independent doubly-linked list that records the insertion order. So, in the LinkedHashMapclass, the entry objects are in two distinct chains:

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

• a singly linked hash chain that is accessed via the main hash array, and

• a separate doubly linked list of all entries that is kept in entry insertion order.

• 通过主散列数组访问的单链接散列链，以及

• 按条目插入顺序保存的所有条目的单独双向链表。

回答by Trying

hashCodewill be mapped to any bucket by the hash function. If there is a collision in hashCodethan HashMapresolve this collision by chaining i.e. it will add the value to the linked list. Below is the code which does this:

hashCode将被哈希函数映射到任何桶。如果在碰撞hashCode比HashMap解决此冲突通过链接即它将值添加到链接列表。下面是执行此操作的代码：

for (Entry<K,V> e = table[i]; e != null; e = e.next) {
392             Object k;
393             if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
394         `enter code here`        V oldValue = e.value;
395                 e.value = value;
396                 e.recordAccess(this);
397                 return oldValue;
398             }
399         }

You can clearly see that it traverse the linked list and if it finds the key than it replaces the old value with new else append to the linked list.

您可以清楚地看到它遍历链表，如果找到键，则将旧值替换为新的 else 附加到链表。

But the difference between LinkedHashMapand HashMapis LinkedHashMapmaintains the insertion order. From docs:

但之间的差异LinkedHashMap，并HashMap为LinkedHashMap维护插入顺序。从文档：

This linked list defines the iteration ordering, which is normally the order in which keys were inserted into the map (insertion-order). Note that insertion order is not affected if a key is re-inserted into the map. (A key k is reinserted into a map m if m.put(k, v) is invoked when m.containsKey(k) would return true immediately prior to the invocation).

这个链表定义了迭代顺序，这通常是键被插入到映射中的顺序（插入顺序）。请注意，如果将键重新插入映射中，则插入顺序不会受到影响。（如果当 m.containsKey(k) 在调用之前立即返回 true 时调用了 m.put(k, v)，则键 k 被重新插入到映射 m 中）。

回答by Steve P.

Take a lookfor yourself. For future reference, you can just google:

快来看看自己。为了将来参考，你可以谷歌：

java LinkedHashMap source

java LinkedHashMap 源码

HashMapuses a LinkedListto handle collissions, but the difference between HashMapand LinkedHashMapis that LinkedHashMaphas a predicable iteration order, which is achieved through an additional doubly-linked list, which usually maintains the insertion order of the keys. The exception is when a key is reinserted, in which case it goes back to the original position in the list.

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

For reference, iterating through a LinkedHashMapis more efficient than iterating through a HashMap, but LinkedHashMapis less memory efficient.

作为参考，迭代 aLinkedHashMap比迭代a更有效HashMap，但LinkedHashMap内存效率较低。

In case it wasn't clear from my above explanation, the hashing process is the same, so you get the benefits of a normal hash, but you also get the iteration benefits as stated above, since you're using a doubly linked list to maintain the ordering of your Entryobjects, which is independent of the linked-list used during hashing for collisions, in case that was ambiguous..

如果我上面的解释不清楚，散列过程是一样的，所以你得到了普通散列的好处，但你也得到了如上所述的迭代好处，因为你使用的是双向链表维护Entry对象的顺序，它独立于在冲突散列期间使用的链表，以防出现歧义..

EDIT:(in response to OP's comment):
A HashMapis backed by an array, in which some slots contain chains of Entryobjects to handle the collisions. To iterate through all of the (key,value) pairs, you would need to go through all of the slots in the array and then go through the LinkedLists; hence, your overall time would be proportional to the capacity.

编辑：（响应 OP 的评论）：
AHashMap由一个数组支持，其中一些插槽包含Entry用于处理碰撞的对象链。要遍历所有 (key,value) 对，您需要遍历数组中的所有插槽，然后遍历LinkedLists; 因此，您的总时间将与容量成正比。

When using a LinkedHashMap, all you need to do is traverse through the doubly-linked list, so the overall time is proportional to the size.

使用 a 时LinkedHashMap，只需遍历双向链表，因此总时间与大小成正比。

回答by aaronman

Since none of the other answers actually explain how something like this could be implemented I'll give it a shot.

由于其他答案都没有真正解释如何实现这样的事情，我会试一试。

One way would be to have some extra information in the value (of the key->value pair) not visible to the user, that had a reference to the previous and next element inserted into the hash map. The benefits are that you can still delete elements in constant time removing from a hashmap is constant time and removing from a linked list is in this case because you have a reference to the entry. You can still insert in constant time because hash map insert is constant, linked list isn't normally but in this case you have constant time access to a spot in the linked list so you can insert in constant time, and lastly retrieval is constant time because you only have to deal with the hash map part of the structure for it.

一种方法是在用户不可见的值（键->值对）中有一些额外的信息，这些信息具有对插入到哈希映射中的前一个和下一个元素的引用。好处是您仍然可以在恒定时间内删除元素，从哈希图中删除是恒定时间，在这种情况下从链表中删除是因为您有对条目的引用。您仍然可以在恒定时间内插入，因为哈希映射插入是恒定的，链表通常不是，但在这种情况下，您可以恒定时间访问链表中的某个位置，因此您可以在恒定时间内插入，最后检索是恒定时间因为你只需要为它处理结构的哈希映射部分。

---

---

Keep in mind that a data structure like this does not come without costs. The size of the hash map will rise significantly because of all the extra references. Each of the main methods will be slightly slower (could matter if they are called repeatedly). And the indirection of the data structure (not sure if that's a real term :P) is increased, though this might not be as big a deal because the references are guaranteed to be pointing to stuff inside the hash map.

请记住，像这样的数据结构并非没有成本。由于所有额外的引用，哈希映射的大小将显着增加。每个主要方法都会稍微慢一些（如果它们被重复调用可能很重要）。并且数据结构的间接性（不确定这是否是一个真正的术语：P）增加了，尽管这可能不是什么大问题，因为引用保证指向哈希映射中的内容。

---

---

Since the only advantage of this type of structure is that it preserves order be careful when you use it. Also when reading the answer keep in mind I don't know that this is the way it's implemented but it is how I would do it if given the task.

由于这种类型的结构的唯一优点是它保留了顺序，因此在使用时要小心。另外在阅读答案时请记住，我不知道这是它的实施方式，但如果给定任务，我将如何做到这一点。

---

---

On the oracle docsthere is a quote confirming some of my guesses.

在oracle 文档上有一段引用证实了我的一些猜测。

This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries.

此实现与 HashMap 的不同之处在于它维护一个双向链表，贯穿其所有条目。

Another relevant quote from the same website.

来自同一网站的另一个相关引用。

This class provides all of the optional Map operations, and permits null elements. Like HashMap, it provides constant-time performance for the basic operations (add, contains and remove), assuming the hash function disperses elements properly among the buckets. Performance is likely to be just slightly below that of HashMap, due to the added expense of maintaining the linked list, with one exception: Iteration over the collection-views of a LinkedHashMap requires time proportional to the size of the map, regardless of its capacity. Iteration over a HashMap is likely to be more expensive, requiring time proportional to its capacity.

此类提供所有可选的 Map 操作，并允许空元素。与 HashMap 一样，它为基本操作（添加、包含和删除）提供恒定时间性能，假设哈希函数在桶中正确分散元素。由于维护链表的额外费用，性能可能略低于 HashMap，但有一个例外：对 LinkedHashMap 的集合视图进行迭代所需的时间与映射的大小成正比，无论其容量如何. 对 HashMap 的迭代可能更昂贵，需要与其容量成正比的时间。

回答by Ankit Mittal

HashMap does not maintain insertion order, hence it does not maintain any doubly linked list.

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

Most salient feature of LinkedHashMap is that it maintains insertion order of key-value pairs. LinkedHashMap uses doubly Linked List for doing so.

LinkedHashMap 最显着的特点是它维护了键值对的插入顺序。LinkedHashMap 为此使用双向链表。

Entry of LinkedHashMap looks like this-

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

By using before and after - we keep track of newly added entry in LinkedHashMap, which helps us in maintaining insertion order.

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

Before refers to previous entry and after refers to next entry in LinkedHashMap.

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

For diagrams and step by step explanation please refer http://www.javamadesoeasy.com/2015/02/linkedhashmap-custom-implementation.html

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

Thanks..!!

谢谢..！！