LinkedHashMap,源码解读就是这么简单

By | 2019年9月10日

概述

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

它们与迭代有序性的实现息息相关。

此外还有两个重要的APIgetcontainsValue,这里也分析一下它们的源码实现,至于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删除。

afterNodeInsertion方法

,

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)){
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

 

在HashMap的putVal方法中调用了该方法,可以看出,在判断条件成立的情况下,该方法会删除双链表中的头节点(当然是在哈希桶和双向链表中同步删除该节点)。判断条件涉及了一个removeEldestEntry(first)方法,它的源码如下:

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

 

可以看到,它默认是返回false的,即不删除头节点。如果需要定义是否需要删除头节点的规则,只需覆盖该方法并提供相关实现即可。该方法的作用在于,它提供了当一个新的entry被添加到linkedHashMap中,删除头节点的机会。这是非常有意义的,可以通过删除头节点来减少内存消耗,避免内存溢出。

afterNodeAccess(e)方法

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

 

该方法在HashMap的putVal方法、LinkedHashMap的get方法中都被调用,它的作用是:如果accessOrder返回值为true(即按照访问顺序迭代),则将最近访问的节点调整至双向队列的队尾,这也就保证了按照访问顺序迭代时Entry的有序性。

get(key)方法

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

 

该方法增加了按访问顺序或插入顺序进行排序的选择功能,会根据AccessOrder的值调整双向链表中节点的顺序,获取节点的过程与HashMap中一致。

containsValue(value)方法

public boolean containsValue(Object value) {
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
        V v = e.value;
        if (v == value || (value != null && value.equals(v)))
            return true;
    }
    return false;
}

 

由于LinkedHashMap维护了一个双向链表,因此它的containsValue(value)方法直接遍历双向链表查找对应的Entry即可,而无需去遍历哈希桶。

LinkedHashMap与HashMap

LinkedHashMap是HashMap的子类,它们最大的区别是,HashMap的迭代是无序的,而LinkedHashMap是有序的,并且有按插入顺序和按访问顺序两种方式。为了实现有序迭代,LinkedHashMap相比HashMap,额外维护了一个双向链表,因此一般情况下,遍历HashMap比LinkedHashMap效率要高,在没有按序访问key-value pair的情况下,一般建议使用HashMap(当然也有例外,当HashMap容量很大,实际数据较少时,遍历起来可能会比 LinkedHashMap慢,因为LinkedHashMap的遍历速度只和实际数据有关,和容量无关,而HashMap的遍历速度和他的容量有关)。

 

————————推荐阅读————————

2019年JVM最新面试题,必须收藏它

最全面的阿里多线程面试题,你能回答几个?

Java面试题:Java中的集合及其继承关系

花了近十年的时间,整理出史上最全面Java面试题

Category: 未分类

发表评论

电子邮件地址不会被公开。 必填项已用*标注