LinkedHashMap继承HashMap并实现了Map接口,同时具有可预测的迭代顺序(按照插入顺序排序)。它与HashMap的不同之处在于,维护了一条贯穿其全部Entry的双向链表(因为额外维护了链表的关系,性能上要略差于HashMap,不过集合视图的遍历时间与元素数量成正比,而HashMap是与buckets数组的长度成正比的),可以认为它是散列表与链表的结合。
/** * The head (eldest) of the doubly linked list. */ transient LinkedHashMap.Entry<K,V> head; /** * The tail (youngest) of the doubly linked list. */ transient LinkedHashMap.Entry<K,V> tail; /** * 迭代顺序模式的标记位,如果为true,采用访问排序,否则,采用插入顺序 * 默认插入顺序(构造函数中默认设置为false) */ final boolean accessOrder; /** * Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance * with the default initial capacity (16) and load factor (0.75). */ public LinkedHashMap() { super(); accessOrder = false; }
LinkedHashMap的Entry实现也继承自HashMap,只不过多了指向前后的两个指针。
/** * 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); } }
你也可以通过构造函数来构造一个迭代顺序为访问顺序(accessOrder设为true)的LinkedHashMap,这个访问顺序指的是按照最近被访问的Entry的顺序进行排序(从最近最少访问到最近最多访问)。基于这点可以简单实现一个采用LRU(Least Recently Used)策略的缓存。
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) { super(initialCapacity, loadFactor); this.accessOrder = accessOrder; }
LinkedHashMap复用了HashMap的大部分代码,所以它的查找实现是非常简单的,唯一稍微复杂点的操作是保证访问顺序。
public V get(Object key) { Node<K,V> e; if ((e = getNode(hash(key), key)) == null) return null; if (accessOrder) afterNodeAccess(e); return e.value; }
还记得这些afterNodeXXXX命名格式的函数吗?我们之前已经在HashMap中见识过了,这些函数在HashMap中只是一个空实现,是专门用来让LinkedHashMap重写实现的hook函数。
// 在HashMap.removeNode()的末尾处调用 // 将e从LinkedHashMap的双向链表中删除 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.putVal()的末尾处调用 // evict是一个模式标记,如果为false代表buckets数组处于创建模式 // HashMap.put()函数对此标记设置为true void afterNodeInsertion(boolean evict) { // possibly remove eldest LinkedHashMap.Entry<K,V> first; // LinkedHashMap.removeEldestEntry()永远返回false // 避免了最年长元素被删除的可能(就像一个普通的Map一样) if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; removeNode(hash(key), key, null, false, true); } } // HashMap.get()没有调用此函数,所以LinkedHashMap重写了get() // get()与put()都会调用afterNodeAccess()来保证访问顺序 // 将e移动到tail,代表最近访问到的节点 void afterNodeAccess(Node<K,V> e) { // move node to last LinkedHashMap.Entry<K,V> last; if (accessOrder && (last = tail) != e) { LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; p.after = null; if (b == null) head = a; else b.after = a; if (a != null) a.before = b; else last = b; if (last == null) head = p; else { p.before = last; last.after = p; } tail = p; ++modCount; } }
注意
removeEldestEntry()
默认永远返回false,这时它的行为与普通的Map无异。如果你把
removeEldestEntry()
重写为永远返回true,那么就有可能使LinkedHashMap处于一个永远为空的状态(每次
put()
或者
putAll()
都会删除头节点)。
一个比较合理的实现示例:
protected boolean removeEldestEntry(Map.Entry eldest){ return size() > MAX_SIZE; }
LinkedHashMap重写了
newNode()
等函数,以初始化或连接节点到它内部的双向链表:
// 链接节点p到链表尾部(或初始化链表) private void linkNodeLast(LinkedHashMap.Entry<K,V> p) { LinkedHashMap.Entry<K,V> last = tail; tail = p; if (last == null) head = p; else { p.before = last; last.after = p; } } // 用dst替换掉src private void transferLinks(LinkedHashMap.Entry<K,V> src, LinkedHashMap.Entry<K,V> dst) { LinkedHashMap.Entry<K,V> b = dst.before = src.before; LinkedHashMap.Entry<K,V> a = dst.after = src.after; // src是头节点 if (b == null) head = dst; else b.after = dst; // src是尾节点 if (a == null) tail = dst; else a.before = dst; } Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) { LinkedHashMap.Entry<K,V> p = new LinkedHashMap.Entry<K,V>(hash, key, value, e); linkNodeLast(p); return p; } Node<K,V> replacementNode(Node<K,V> p, Node<K,V> next) { LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p; LinkedHashMap.Entry<K,V> t = new LinkedHashMap.Entry<K,V>(q.hash, q.key, q.value, next); transferLinks(q, t); return t; } TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) { TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next); linkNodeLast(p); return p; } TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) { LinkedHashMap.Entry<K,V> q = (LinkedHashMap.Entry<K,V>)p; TreeNode<K,V> t = new TreeNode<K,V>(q.hash, q.key, q.value, next); transferLinks(q, t); return t; }
遍历LinkedHashMap所需要的时间与Entry数量成正比,这是因为迭代器直接对双向链表进行迭代,而链表中只会含有Entry节点。迭代的顺序是从头节点开始一直到尾节点,插入操作会将新节点链接到尾部,所以保证了插入顺序,而访问顺序会通过
afterNodeAccess()
来保证,访问次数越多的节点越接近尾部。
abstract class LinkedHashIterator { LinkedHashMap.Entry<K,V> next; LinkedHashMap.Entry<K,V> current; int expectedModCount; LinkedHashIterator() { next = head; expectedModCount = modCount; current = null; } public final boolean hasNext() { return next != null; } final LinkedHashMap.Entry<K,V> nextNode() { LinkedHashMap.Entry<K,V> e = next; if (modCount != expectedModCount) throw new ConcurrentModificationException(); if (e == null) throw new NoSuchElementException(); current = e; next = e.after; return e; } public final void remove() { Node<K,V> p = current; if (p == null) throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); current = null; K key = p.key; removeNode(hash(key), key, null, false, false); expectedModCount = modCount; } } final class LinkedKeyIterator extends LinkedHashIterator implements Iterator<K> { public final K next() { return nextNode().getKey(); } } final class LinkedValueIterator extends LinkedHashIterator implements Iterator<V> { public final V next() { return nextNode().value; } } final class LinkedEntryIterator extends LinkedHashIterator implements Iterator<Map.Entry<K,V>> { public final Map.Entry<K,V> next() { return nextNode(); } }