Java中的LinkedHashMap的指南

1.概述

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

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

2. LinkedHashMap 与 HashMap

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

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

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

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

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

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

3. LinkedHashMap的插入顺序

让我们来看看一个LinkedHashMap实例，它根据条目插入map的方式对其进行排序。它还保证这个顺序在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]);
    }
}

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

我们可以保证这个测试总是通过，因为插入顺序总是被保持的。我们不能对HashMap做出同样的保证。

此属性在接收任何映射、创建副本以进行操作并将其返回给调用代码的 API 中具有很大优势。 如果客户端需要在调用 API 之前以相同的方式对返回的映射进行排序，那么LinkedHashMap就是最好的选择。

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

4. LinkedHashMap的访问顺序

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

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

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

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

因此，用这种地图建立一个最近使用最少的缓存（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());
}

请注意当我们在map上执行访问操作时，键集中元素的顺序是如何转换的。

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

经过上面的例子，应该很明显，putAll操作为指定的映射中的每个映射生成一个条目访问。

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

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

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

为了在实践中看到这一点，让我们创建我们自己的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;
    }

}

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

@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());
}

请注意，当我们在地图上添加新的条目时，健集开头的最老的条目会不断地减少。

5.性能方面的考虑

就像HashMap一样，LinkedHashMap在恒定时间内执行基本的Map操作，即添加、删除和包含，只要哈希函数的维度良好。它也接受空键和空值。

但是，由于增加了维护双向链表的开销，LinkedHashMap 的这种恒定时间性能可能比 HashMap 的恒定时间性能差一点。

对LinkedHashMap的集合视图进行迭代也需要O(n)的线性时间，与HashMap类似。另一方面， LinkedHashMap在迭代过程中的线性时间性能优于HashMap的线性时间。

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

负载因子和初始容量的定义与HashMap的定义完全相同。但是请注意，对初始容量选择过高的值的惩罚对LinkedHashMap来说比HashMap要轻，因为该类的迭代时间不受容量的影响。

6.并发

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

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

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

与HashMap的区别在于需要进行结构修改。在存取有序的LinkedHashMap中，仅仅调用get API就会导致结构修改。与此同时，还有put和remove等操作。

7.结语

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

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

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