本文我们深入Java Map接口的一个实现类LinkedHashMap的内部。它是HashMap的子类，继承了父类的核心代码。因此读者应该先了解HashMap的工作原理。

LinkedHashMap 与 HashMap

*LinkedHashMap *在大多数方面 与 HashMap 类似，但LinkedHashMap 是基于hash 表与链表结构用于增强hashMap。其底层除了有缺省为16大小的数组外，还维护了一个双向链表连结所有项。

为了维护元素顺序，LinkedHashMap 修改了 HashMap类的Map.Entry类，在其中增加了before 和 after 指针对象，源码如下：

    /**
     * HashMap.Node subclass for normal LinkedHashMap entries.
     */
    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类简单增加两个指针用于连接链表，另外使用Entry类实现HashMap。

我们在看构造函数,默认定义了迭代顺序，缺省按照插入顺序：

    public LinkedHashMap(int initialCapacity, float loadFactor) {
        super(initialCapacity, loadFactor);
        accessOrder = false;
    }

插入顺序(Insertion-Order)

下面通过实例来了解插入顺序：

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

上面代码插入5个实体，然后获取其键集合，最后迭代验证键顺序。LinkHashMap可以保证键的顺序按照插入的顺序，HashMap不能保证键的顺序。

整个特性在一些场景非常有用。如对API的调用需要按照客户端来的先后次序进行返回，那么LinkHashMap则可以轻松满足。

注：如果将键重新插入映射中，则插入顺序不受影响。

访问顺序(Access-Order)

前节我们看到构造函数包括三个参数，初始容量、载入因子以及排序策略，默认为插入顺序，还可以设为访问顺序，该机制保证迭代元素的顺序按照元素最后被访问的顺序，从最近最少访问到最近最多访问顺序：

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

这种策略很容易实现Least Recently Used (LRU)缓存算法。对map特定键的访问操作，将导致改键在迭代时出现在最后。通过上面示例，显然迭代LinkHashMap不会影响顺序，仅仅显示的访问操作会影响。

LinkHashMap还提供了维护map条目为固定大小的机制，对已经条目数量为最大时，当插入新的元素则最老的元素会被删除。

我们可以重写removeEldestEntry方法，以强制该策略自动删除过时的条目。下面示例定义MyLinkedHashMap类，重写

removeEldestEntry方法：

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

}

当条目超过最大值时，新条目被插入，代价是丢弃最旧的条目，即最近访问的条目优先于其他条目：

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

我们看到当增加新条目时，在键set开头的最老的条目丢失了。

其他方面

• 并发

和HashMap一样，LinkHashMap 实现没有同步功能，所以如果多个线程同时访问时，需要在外部增加同步控制。可以使用这种方式创建：

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

与HashMap不同的是什么操作会有结构性修改，顺序访问LInkHashMap，仅调用get 操作就会有结构性修改，另外put和remove也如此。

• 性能说明

与HashMap一样，LInkHashMap执行基本的Map操作，如add , remove以及 contain 操作时间都是常量，只要hash函数有足够的维度，也支持存储null 键和值。

但LInkHashMap的常量时间要比HashMap要稍大，因为需要额外维护双向链表。迭代LInkHashMap集合与HashMap一样都是线性O(n),LInkHashMap性能要优于HashMap。这是因为LInkHashMap的元素数量与容量无关，HashMap的n 是容量和size的和，即O(size+capacity)。

载入因子和初始化容量与HashMap一样，但对于LinkHashMap的影响要小，因为迭代并不受容量影响。

总结

本文我们学习了LinkHashMap，它是Map接口最重要的实现。通过探索其特性、与HashMap的差异、内部工作原理及应用场景。