jdk LinkedHashMap工作原理分析

LinkedHashMap是一种会记录插入顺序的Map,内部维护着一个accessOrder属性,用于表示map数据的迭代顺序是基于访问顺序还是插入顺序。

LinkedHashMap原理分析

首先是LinkedHashMap的定义:

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
        implements Map<K,V>

LinkedHashMap继承HashMap,实现Map接口,所以它的结构跟HashMap是一样的,使用链表法解决哈希冲突的哈希表,基本操作跟HashMap也是一样的,就是多了一点额外的步骤用于处理链表。

LinkedHashMap有个内部类Entry,这个Entry就是链表中的节点,继承自HashMap.Node,多出了2个属性before和after,所以LinkedHashMap内部链表的节点是双向的,代码如下:

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

另外LinkedHashMap还有两个重要的属性head,tail,这2个属性用于存储插入的节点,形成一个双向链表:

// 首节点
transient LinkedHashMap.Entry<K,V> head;

// 尾节点
transient LinkedHashMap.Entry<K,V> tail;

跟HashMap一样,下面这个例子对应的LinkedHashMap结构图示如下所示,accessOrder为false,使用插入顺序:

Map<String, Integer> map = new LinkedHashMap<String, Integer>(5);
map.put("java", 1);
map.put("golang", 2);
map.put("python", 3);
map.put("ruby", 4);
map.put("scala", 5);

put操作

LinkedHashMap没有覆盖HashMap的put方法,所以put操作跟HashMap是一样的。但是它覆盖了newNode方法,也就是说构造新节点的时候,LinkedHashMap跟HashMap是不一样的:

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    // 使用Entry双向链表构造节点,而不是HashMap的Node单向链表
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    linkNodeLast(p); // 更新双向链表,这一操作在HashMap里面是没有的
    return p;
}

另外,LinkedHashMap重写了afterNodeInsertion这个钩子方法,在put一个关键字不存在的节点之后会调用这个方法:

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    // removeEldestEntry方法LinkedHashMap永远返回false,一些使用缓存策略的Map会覆盖这个方法,比如jackson的LRUMap,会移除最老的节点,也就是首节点
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

put操作如果关键字已经存在,会调用afterNodeAccess这个钩子方法:

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

get操作

LinkedHashMap复写了get方法:

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder) // 使用访问顺序的话,调用afterNodeAccess方法
        afterNodeAccess(e);
    return e.value;
}

remove操作

LinkedHashMap的remove方法没有复写HashMap的remove方法,但是同样实现了afterNodeRemoval这个钩子方法:

// 更新双向链表
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;
}

accessOrder属性分析

LinkedHashMap默认情况下,accessOrder属性为false,也就是使用插入顺序,这个插入顺序是根据LinkedHashMap内部的一个双向链表实现的。如果accessOrder为true,也就是使用访问顺序,那么afterNodeAccess这个钩子方法内部的逻辑会被执行,将会修改双向链表的结构,再来看一下这个方法的具体逻辑:

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

afterNodeAccess在使用get方法或者put方法遇到关键字已经存在的情况下,会被触发,一个例子如下:

Map<String, Integer> map = new LinkedHashMap<String, Integer>(5, 0.75f, true);
map.put("java", 1);
map.put("golang", 2);
map.put("python", 3);
map.put("ruby", 4);
map.put("scala", 5);
System.out.println(map.get("ruby"));

上面这段代码,LinkedHashMap的accessOrder属性为true,使用访问顺序,最后调用了get方法,触发afterNodeAccess方法,修改双向链表,效果如下:

注意点

LinkedHashMap使用访问顺序并且进行遍历的时候,如果使用如下代码,会发生ConcurrentModificationException异常:

for(String str : map.keySet()) {
    System.out.println(map.get(str));
}

不应该这么使用,而是应该直接读取value:

for(Integer it : map.values()) {
    System.out.println(it);
}

具体可以参考stackoverflow上的这篇帖子

总结

  1. LinkedHashMap也是一种使用拉链式哈希表的数据结构,除了哈希表,它内部还维护着一个双向链表,用于处理访问顺序和插入顺序的问题

  2. LinkedHashMap继承自HashMap,大多数的方法都是跟HashMap一样的,不过覆盖了一些方法

如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
本文作者:Format
原文链接: http://fangjian0423.github.io/2016/03/29/jdk_linkedhashmap/
版权归作者所有,转载请注明出处