GuangchaoSun's Blog

LinkedHashMap源码解析

发表于  |    |   
1
2
3
public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>

上面可以看出LinkedHashMap是HashMap的子类。它的特点是：

LinkedHashMap是Hash表和链表的实现，并且依靠着双向链表保证了迭代顺序使插入的顺序。非线程安全

设计原理

LinkedHashMap相比较HashMap来说，增加了一个双向链表来保证key的顺序。
环形双向链表
双向链表这种数据结构，最关键的是保证在增加节点、删除节点时不要断链。

1
private transient Entry<K, V> header;

在LinkedHashMap定义了一个头指针header，它不存储任何数据。标记before和after两个指针。

1
2
3
4
5
6
7
8
9
10
11
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);
       }
   }
 //双向链表的头结点
 transient LinkedHashMap.Entry<K,V> head;
 //双向链表的尾节点
 transient LinkedHashMap.Entry<K,V> tail;

bullet的实体Entry继承了HashMap的Node并且增加了before和after两个指针。

1
private final boolean accessOrder;

LinkedHashMap还有一个私有变量accessOrder，默认为false，即按照插入顺序遍历。如果设置为true则按照访问顺序遍历。这里我不太懂按照访问顺序遍历什么意思，还专门搜了一下：当调用LinkedHashMap的get(key)或者put(key, value)时，碰巧key在map中被包含，那么LinkedHashMap会将key对象的entry放在线性结构的最后。

构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
//默认是false，则迭代时输出的顺序是插入节点的顺序。若为true，则输出的顺序是按照访问节点的顺序。
//为true时，可以在这基础之上构建一个LruCach
final boolean accessOrder;
public LinkedHashMap() {
    super();
    accessOrder = false;
}
//指定初始化时的容量，
public LinkedHashMap(int initialCapacity) {
    super(initialCapacity);
    accessOrder = false;
}
//指定初始化时的容量，和扩容的加载因子
public LinkedHashMap(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor);
    accessOrder = false;
}
//指定初始化时的容量，和扩容的加载因子，以及迭代输出节点的顺序
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}
//利用另一个Map 来构建，
public LinkedHashMap(Map<? extends K, ? extends V> m) {
    super();
    accessOrder = false;
    //该方法上文分析过，批量插入一个map中的所有数据到 本集合中。
    putMapEntries(m, false);
}

增

LinkedHashMap重写了newNode(),在每次构建新节点时，通过linkNodeLast()方法，将新节点链接到内部双向链表的尾部

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//在构建新节点时，构建的是`LinkedHashMap.Entry` 不再是`Node`.
 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;
 }
 //将新增的节点，连接在链表的尾部
 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;
     }
 }

删

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//在删除节点e时，同步将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 的前置后置节点都置空
    p.before = p.after = null;
    //如果前置节点是null，则p是以前的头结点，而现在的头结点应该是后置节点a
    if (b == null)
        head = a;
    else//否则将前置节点b的后置节点指向a
        b.after = a;
    //同理如果后置节点时null ，则尾节点应是b
    if (a == null)
        tail = b;
    else//否则更新后置节点a的前置节点为b
        a.before = b;
}

reference: