概述
LinkedHashMap是HashMap的子类,它的大部分实现与HashMap相同,两者最大的区别在于,HashMap的对哈希表进行迭代时是无序的,而LinkedHashMap对哈希表迭代是有序的,LinkedHashMap默认的规则是,迭代输出的结果保持和插入key-value pair的顺序一致(当然具体迭代规则可以修改)。LinkedHashMap除了像HashMap一样用数组、单链表和红黑树来组织数据外,还额外维护了一个双向链表,每次向linkedHashMap插入键值对,除了将其插入到哈希表的对应位置之外,还要将其插入到双向循环链表的尾部。
底层实现
先来看一下LinekedHashMap的定义:
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>
除了继承自HashMap以外并无太多特殊之处,这里特地标注实现了Map接口应该也只是为了醒目。
大家最关心的应该是LinkedHashMap如何实现有序迭代,下面将逐步通过源码来解答这一问题。
先看一下一个重要的静态内部类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); } }
该类继承自HashMap的Node内部类,前面已经介绍过,Node是一个单链表结构,这里Entry添加了前继引用和后继引用,则是一个双向链表的节点。在双向链表中,每个节点可以记录自己前后插入的节点信息,以维持有序性,这也是LinkedHashMap实现有序迭代的关键。
按插入顺序有序和按访问顺序有序
按插入有序
按插入有序即先添加的在前面,后添加的在后面,修改操作不影响顺序。以如下代码为例:
Map<String,Integer> seqMap = new LinkedHashMap<>(); seqMap.put("c", 100); seqMap.put("d", 200); seqMap.put("a", 500); seqMap.put("d", 300); for(Entry<String,Integer> entry : seqMap.entrySet()){ System.out.println(entry.getKey()+" "+entry.getValue()); }
运行结
运行结果是:
c 100 d 300 a 500
可以看到,键是按照”c”, “d”, “a”的顺序插入的,修改”d”的值不会修改顺序。
按访问有序
按访问有序是,序列末尾存放的是最近访问的key-value pair,每次访问一个key-value pair后,就会将其移动到末尾。
Map<String,Integer> accessMap = new LinkedHashMap<>(16, 0.75f, true); accessMap.put("c", 100); accessMap.put("d", 200); accessMap.put("a", 500); accessMap.get("c"); accessMap.put("d", 300); for(Entry<String,Integer> entry : accessMap.entrySet()){ System.out.println(entry.getKey()+" "+entry.getValue()); }
运行结果为:
a 500 c 100 d 300
针对不同的应用场景,LinkedHashMap可以在这两种排序方式中进行抉择。
LinkedHashMap定义了三个重要的字段:
//双链表的头节点 transient LinkedHashMap.Entry<K,V> head; //双链表的尾节点 transient LinkedHashMap.Entry<K,V> tail; /** * 这个字段表示哈希表的迭代顺序 * true表示按访问顺序迭代 * false表示按插入顺序迭代 * LinkedHashMap的构造函数均将该值设为false,因此默认为false */ final boolean accessOrder;
关于它们的具体作用已在注释中标出。
LinkedHashMap有五个构造方法,其中有一个可以指定accessOrder的值:
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; }
重要方法
在HashMap中定义了几个“钩子”方法(关于钩子的详细内容,请参考笔者的博客设计模式(9)——模板方法模式),这里特地列出其中的三个:
afterNodeRemoval(e)
afterNodeInsertion
afterNodeInsertion
它们与迭代有序性的实现息息相关。
此外还有两个重要的APIget
和containsValue
,这里也分析一下它们的源码实现,至于put
方法,LinkedHashMap并没有覆写该方法,因此其实现与HashMap相同。
afterNodeRemoval(e)方法
void afterNodeRemoval(Node<K,V> e) { // unlink LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; p.before = p.after = null; if (b == null) head = a; else b.after = a; if (a == null) tail = b; else a.before = b; }
在HashMap的removeNode
方法中调用了该钩子方法,对于LinkedHashMap,在执行完对哈希桶中单链表或红黑树节点的删除操作后,还需要调用该方法将双向链表中对应的Entry删除。