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