深入理解Java LinkedHashMap

本文我们深入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的差异、内部工作原理及应用场景。

上一篇:Selenium - 鼠标与键盘操作


下一篇:Redis分布式锁