Map 大家族的那点事儿 ( 6 ) :LinkedHashMap

java admin 2500 0 评论

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

 

转载请注明: 飞嗨_分享互联网 » Map 大家族的那点事儿 ( 6 ) :LinkedHashMap

赞 (0) or 分享 (0)
游客 发表我的评论   换个身份
取消评论

表情
(0)个小伙伴在吐槽

高效,专业,符合SEO

联系我们