A Guide to LinkedHashMap in Java – Java中的LinkedHashMap指南

最后修改: 2017年 1月 20日

中文/混合/英文(键盘快捷键：t)

1. Overview

1.概述

In this article, we are going to explore the internal implementation of LinkedHashMap class. LinkedHashMap is a common implementation of Map interface.

在这篇文章中，我们将探讨LinkedHashMap类的内部实现。LinkedHashMap是Map接口的一个普通实现。

This particular implementation is a subclass of HashMap and therefore shares the core building blocks of the HashMap implementation. As a result, it’s highly recommended to brush up on that before proceeding with this article.

这个特定的实现是HashMap的子类，因此共享HashMap实现的核心构建块。因此，强烈建议在继续阅读本文之前先了解一下。

2. LinkedHashMap vs HashMap

2.LinkedHashMap与HashMap

The LinkedHashMap class is very similar to HashMap in most aspects. However, the linked hash map is based on both hash table and linked list to enhance the functionality of hash map.

LinkedHashMap类在大多数方面与HashMap非常相似。然而，链接哈希图同时基于哈希表和链接列表来增强哈希图的功能。

It maintains a doubly-linked list running through all its entries in addition to an underlying array of default size 16.

它除了维护一个默认大小为16的底层数组外，还维护一个贯穿其所有条目的双链接列表。

To maintain the order of elements, the linked hashmap modifies the Map.Entry class of HashMap by adding pointers to the next and previous entries:

为了保持元素的顺序，链接的哈希图修改了Map.Entry的HashMap类，增加了指向下一个和上一个条目的指针。

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

Notice that the Entry class simply adds two pointers; before and after which enable it to hook itself to the linked list. Aside from that, it uses the Entry class implementation of a the HashMap.

请注意，Entry类只是添加了两个指针；before和after，这使得它能够将自己挂到链表上。除此之外，它还使用了HashMap的Entry类的实现。

Finally, remember that this linked list defines the order of iteration, which by default is the order of insertion of elements (insertion-order).

最后，请记住，这个链接列表定义了迭代的顺序，默认情况下是插入元素的顺序（insertion-order）。

3. Insertion-Order LinkedHashMap

3.插入顺序LinkedHashMap

Let’s have a look at a linked hash map instance which orders its entries according to how they’re inserted into the map. It also guarantees that this order will be maintained throughout the life cycle of the map:

让我们来看看一个链接的哈希地图实例，它根据条目插入地图的方式对其进行排序。它还保证这个顺序在地图的整个生命周期内都会被保持。

@Test
public void givenLinkedHashMap_whenGetsOrderedKeyset_thenCorrect() {
    LinkedHashMap<Integer, String> map = new LinkedHashMap<>();
    map.put(1, null);
    map.put(2, null);
    map.put(3, null);
    map.put(4, null);
    map.put(5, null);

    Set<Integer> keys = map.keySet();
    Integer[] arr = keys.toArray(new Integer[0]);

    for (int i = 0; i < arr.length; i++) {
        assertEquals(new Integer(i + 1), arr[i]);
    }
}

Here, we’re simply making a rudimentary, non-conclusive test on the ordering of entries in the linked hash map.

在这里，我们只是对链接的哈希图中的条目排序做了一个简单的、非结论性的测试。

We can guarantee that this test will always pass as the insertion order will always be maintained. We cannot make the same guarantee for a HashMap.

我们可以保证该测试将始终通过，因为插入顺序将始终被保持。我们无法对HashMap做出同样的保证。

This attribute can be of great advantage in an API that receives any map, makes a copy to manipulate and returns it to the calling code. If the client needs the returned map to be ordered the same way before calling the API, then a linked hashmap is the way to go.

这个属性在接收任何地图的API中都有很大的优势，它可以制作一个副本进行操作，并将其返回给调用代码。如果客户需要在调用API之前对返回的地图进行同样的排序，那么链接的哈希图就是最好的选择。

Insertion order is not affected if a key is re-inserted into the map.

如果一个键被重新插入到地图中，插入顺序不受影响。

4. Access-Order LinkedHashMap

4.访问顺序LinkedHashMap

LinkedHashMap provides a special constructor which enables us to specify, among custom load factor (LF) and initial capacity, a different ordering mechanism/strategy called access-order:

LinkedHashMap提供了一个特殊的构造函数，使我们能够在自定义负载因子（LF）和初始容量中，指定一种不同的排序机制/策略，称为访问顺序。

LinkedHashMap<Integer, String> map = new LinkedHashMap<>(16, .75f, true);

The first parameter is the initial capacity, followed by the load factor and the last param is the ordering mode. So, by passing in true, we turned on access-order, whereas the default was insertion-order.

第一个参数是初始容量，其次是负载系数，最后一个参数是排序模式。因此，通过传入true，我们打开了访问顺序，而默认的是插入顺序。

This mechanism ensures that the order of iteration of elements is the order in which the elements were last accessed, from least-recently accessed to most-recently accessed.

这种机制保证了元素的迭代顺序是元素最后被访问的顺序，从最近被访问最少的到最近被访问最多的。

And so, building a Least Recently Used (LRU) cache is quite easy and practical with this kind of map. A successful put or get operation results in an access for the entry:

因此，用这种地图建立一个最近使用最少的缓存（LRU）是相当容易和实用的。一个成功的put或get操作会导致对该条目的访问。

@Test
public void givenLinkedHashMap_whenAccessOrderWorks_thenCorrect() {
    LinkedHashMap<Integer, String> map 
      = new LinkedHashMap<>(16, .75f, true);
    map.put(1, null);
    map.put(2, null);
    map.put(3, null);
    map.put(4, null);
    map.put(5, null);

    Set<Integer> keys = map.keySet();
    assertEquals("[1, 2, 3, 4, 5]", keys.toString());
 
    map.get(4);
    assertEquals("[1, 2, 3, 5, 4]", keys.toString());
 
    map.get(1);
    assertEquals("[2, 3, 5, 4, 1]", keys.toString());
 
    map.get(3);
    assertEquals("[2, 5, 4, 1, 3]", keys.toString());
}

Notice how the order of elements in the key set is transformed as we perform access operations on the map.

请注意，当我们对地图进行访问操作时，键集中的元素顺序是如何转变的。

Simply put, any access operation on the map results in an order such that the element that was accessed would appear last if an iteration were to be carried out right away.

简单地说，对地图的任何访问操作都会产生一个顺序，如果立即进行迭代，被访问的元素会出现在最后。

After the above examples, it should be obvious that a putAll operation generates one entry access for each of the mappings in the specified map.

经过上面的例子，应该很明显，putAll操作为指定地图中的每个映射产生一个入口访问。

Naturally, iteration over a view of the map does’t affect the order of iteration of the backing map; only explicit access operations on the map will affect the order.

当然，对地图的一个视图的迭代并不影响后援地图的迭代顺序；只有对地图的显式访问操作才会影响这个顺序。

LinkedHashMap also provides a mechanism for maintaining a fixed number of mappings and to keep dropping off the oldest entries in case a new one needs to be added.

LinkedHashMap还提供了一种机制，用于维护固定数量的映射，并在需要添加新的条目时不断放弃最旧的条目。

The removeEldestEntry method may be overridden to enforce this policy for removing stale mappings automatically.

removeEldestEntry方法可以被重写，以执行这一政策，自动删除陈旧的映射。

To see this in practice, let us create our own linked hash map class, for the sole purpose of enforcing the removal of stale mappings by extending LinkedHashMap:

为了在实践中看到这一点，让我们创建我们自己的链接哈希图类，唯一的目的是通过扩展LinkedHashMap来强制删除陈旧的映射。

public class MyLinkedHashMap<K, V> extends LinkedHashMap<K, V> {

    private static final int MAX_ENTRIES = 5;

    public MyLinkedHashMap(
      int initialCapacity, float loadFactor, boolean accessOrder) {
        super(initialCapacity, loadFactor, accessOrder);
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry eldest) {
        return size() > MAX_ENTRIES;
    }

}

Our override above will allow the map to grow to a maximum size of 5 entries. When the size exceeds that, each new entry will be inserted at the cost of losing the eldest entry in the map i.e. the entry whose last-access time precedes all the other entries:

我们上面的覆盖将允许地图增长到最大5个条目的大小。当超过这个大小时，每个新条目的插入将以失去地图中最年长的条目为代价，即最后访问时间在所有其他条目之前的条目。

@Test
public void givenLinkedHashMap_whenRemovesEldestEntry_thenCorrect() {
    LinkedHashMap<Integer, String> map
      = new MyLinkedHashMap<>(16, .75f, true);
    map.put(1, null);
    map.put(2, null);
    map.put(3, null);
    map.put(4, null);
    map.put(5, null);
    Set<Integer> keys = map.keySet();
    assertEquals("[1, 2, 3, 4, 5]", keys.toString());
 
    map.put(6, null);
    assertEquals("[2, 3, 4, 5, 6]", keys.toString());
 
    map.put(7, null);
    assertEquals("[3, 4, 5, 6, 7]", keys.toString());
 
    map.put(8, null);
    assertEquals("[4, 5, 6, 7, 8]", keys.toString());
}

Notice how oldest entries at the start of the key set keep dropping off as we add new ones to the map.

请注意，当我们在地图上添加新的条目时，钥匙集开始的最老的条目是如何不断下降的。

5. Performance Considerations

5.性能考虑因素

Just like HashMap, LinkedHashMap performs the basic Map operations of add, remove and contains in constant-time, as long as the hash function is well-dimensioned. It also accepts a null key as well as null values.

就像HashMap一样，LinkedHashMap在恒定时间内执行基本的Map操作，即添加、删除和包含，只要哈希函数的尺寸足够大。它还接受空键和空值。

However, this constant-time performance of LinkedHashMap is likely to be a little worse than the constant-time of HashMap due to the added overhead of maintaining a doubly-linked list.

然而，由于维护双重链接列表的额外开销，LinkedHashMap的这种恒定时间性能可能会比HashMap的恒定时间差一点。

Iteration over collection views of LinkedHashMap also takes linear time O(n) similar to that of HashMap. On the flip side, LinkedHashMap‘s linear time performance during iteration is better than HashMap‘s linear time.

对LinkedHashMap的集合视图进行迭代也需要类似于HashMap的线性时间O(n)。反过来说，LinkedHashMap在迭代过程中的线性时间性能比HashMap的线性时间好。

This is because, for LinkedHashMap, n in O(n) is only the number of entries in the map regardless of the capacity. Whereas, for HashMap, n is capacity and the size summed up, O(size+capacity).

这是因为，对于LinkedHashMap，O(n)中的n只是地图中的条目数，与容量无关。而对于HashMap，n是容量和大小之和，O(size+capacity)。

Load Factor and Initial Capacity are defined precisely as for HashMap. Note, however, that the penalty for choosing an excessively high value for initial capacity is less severe for LinkedHashMap than for HashMap, as iteration times for this class are unaffected by capacity.

负载因子和初始容量的定义与HashMap一样精确。但是请注意，对于LinkedHashMap来说，为初始容量选择一个过高的值的惩罚比HashMap要轻，因为这个类别的迭代时间不受容量的影响。

6. Concurrency

6.并发性

Just like HashMap, LinkedHashMap implementation is not synchronized. So if you are going to access it from multiple threads and at least one of these threads is likely to change it structurally, then it must be externally synchronized.

就像HashMap，LinkedHashMap的实现是不同步的。因此，如果你要从多个线程中访问它，并且这些线程中至少有一个可能会改变它的结构，那么它必须是外部同步的。

It’s best to do this at creation:

最好是在创建时就这样做。

Map m = Collections.synchronizedMap(new LinkedHashMap());

The difference with HashMap lies in what entails a structural modification. In access-ordered linked hash maps, merely calling the get API results in a structural modification. Alongside this, are operations like put and remove.

与HashMap的区别在于什么会导致结构修改。在访问排序的链接哈希图中，仅仅调用get API就会导致结构修改。与此同时，还有像put和remove这样的操作。

7. Conclusion

7.结论

In this article, we have explored Java LinkedHashMap class as one of the foremost implementations of Map interface in terms of usage. We have also explored its internal workings in terms of the difference from HashMap which is its superclass.

在这篇文章中，我们探讨了Java LinkedHashMap类作为Map接口的最主要实现之一的使用情况。我们还探讨了它与HashMap的内部工作原理，后者是它的超类。

Hopefully, after having read this post, you can make more informed and effective decisions as to which Map implementation to employ in your use case.

希望在读完这篇文章后，你可以就在你的用例中采用哪种地图实现做出更明智和有效的决定。

The full source code for all the examples used in this article can be found in the GitHub project.

本文中使用的所有示例的完整源代码可以在GitHub项目中找到。