LinkedHashMap分析

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

1     /**
2      * LinkedHashMap的Entry对象，除了继承于HashMap Node的4个属性，额外添加了两个属性before,after用于维护双向链表的前后结点关系
3      */
4     static class Entry<K,V> extends HashMap.Node<K,V> {
5         Entry<K,V> before, after;
6         Entry(int hash, K key, V value, Node<K,V> next) {
7             super(hash, key, value, next);
8         }
9     }

 1     /**
 2      * 双向链表的头结点（最近最少使用的结点）
 3      */
 4     transient LinkedHashMap.Entry<K,V> head;
 5 
 6     /**
 7      * 双向链表的尾结点(最近最多使用的结点)
 8      */
 9     transient LinkedHashMap.Entry<K,V> tail;
10 
11     /**
12      * LinkedHashMap核心属性，该属性定义了双向链表中存储结点的顺序:
13      * 如果为true，则双向链表按照结点的访问顺序维护前后结点关系(访问、操作结点都会影响该结点在双向链表的位置),这种方式实现了LRU算法
14      * 如果为false，则双向链表仅仅按照结点的插入顺序维护前后结点关系(只有操作结点的动作才会影响该结点在双向链表的位置)
15      * 该值默认为false.
16      */
17     final boolean accessOrder;

 1     /**
 2      * 带capacity和loadFactor的构造函数
 3      *
 4      * @param  initialCapacity 自定义初始容量
 5      * @param  loadFactor      自定义负载因子
 6      * @throws IllegalArgumentException  初始容量或负载因子为负数，抛出异常
 7      *         
 8      */
 9     public LinkedHashMap(int initialCapacity, float loadFactor) {
10         super(initialCapacity, loadFactor);   //调用HashMap的构造函数
11         accessOrder = false;
12     }
13 
14     /**
15      * 只带capacity参数的构造函数，此时loadFactor为默认的0.75
16      *
17      * @param  initialCapacity 自定义初始容量
18      * @throws IllegalArgumentException 初始容量为负数，抛出异常
19      */
20     public LinkedHashMap(int initialCapacity) {
21         super(initialCapacity); //调用HashMap的构造函数
22         accessOrder = false;
23     }
24 
25     /**
26      * 无参数构造函数。初始容量为默认的16，负载因子为默认的0.75
27      */
28     public LinkedHashMap() {
29         super();  //调用HashMap的构造函数
30         accessOrder = false;
31     }
32 
33 
34     /**
35      * 三个参数的构造函数，可以控制双向链表的存储方式
36      *
37      * @param  initialCapacity 初始容量
38      * @param  loadFactor      负载因子
39      * @param  accessOrder     双向链表维护的存储顺序
40      * @throws IllegalArgumentException 初始容量或负载因子为负数，抛出异常
41      */
42     public LinkedHashMap(int initialCapacity,
43                          float loadFactor,
44                          boolean accessOrder) {
45         super(initialCapacity, loadFactor);  //调用HashMap的构造方法
46         this.accessOrder = accessOrder;
47     }

 1    /**
 2      * LinkedHashMap重写了HashMap的newNode()方法
 3      * 该方法在HashMap的putVal()方法中判断需要新增结点时会被调用
 4      * @param hash
 5      * @param key
 6      * @param value
 7      * @param e
 8      * @return
 9      */
10     Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
11         LinkedHashMap.Entry<K,V> p =
12             new LinkedHashMap.Entry<K,V>(hash, key, value, e);  //新增一个key-value的结点
13         linkNodeLast(p);  //LinkedHashMap生成新结点时除了新增一个结点外，还将该结点在双向链表中的位置移动到尾部，这个操作默认按元素插入顺序维护了链表前后结点关系
14         return p;
15     }
16 
17 
18    /**
19      * 将结点在双向链表中的位置移动到尾部
20      * @param p
21      */
22     private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
23         LinkedHashMap.Entry<K,V> last = tail;  //将当前双向链表的尾结点保存下来
24         tail = p;  //尾结点设置为传入的结点
25         if (last == null)  //如果之前链表中没有结点，即这次新增的结点是链表的头结点
26             head = p;
27         else {  //如果这次新增的结点不是链表的头结点，则将其移动到链表的尾部
28             p.before = last;  //当前结点的前驱指向之前链表的尾结点
29             last.after = p;  //之前链表尾结点后驱指向当前结点
30         }
31     }
32 
33 
34     /**
35      * 某个结点被删除后的回调方法
36      * LinkedHashMap在维护的双向链表中也要把该结点与前后结点的关系移除
37      * @param e
38      */
39     void afterNodeRemoval(Node<K,V> e) { // unlink
40         LinkedHashMap.Entry<K,V> p =
41             (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
42         p.before = p.after = null;  //移除被删除结点和前后结点之前的引用关系
43         if (b == null)  //如果双向链表中被移除的结点就是首结点
44             head = a;  //将下一个结点变为首结点
45         else
46             b.after = a;  //否则就把被删除结点的前一个结点的后驱指向被删除结点的后一个结点
47         if (a == null) //如果双向链表中被移除的结点就是尾结点
48             tail = b;  //将上一个结点变为尾结点
49         else
50             a.before = b;  //否则就把被删除结点的后一个结点的前驱指向被删除结点的前一个结点
51     }
52 
53 
54    /**
55      * 某个结点被访问后的回调方法
56      * 如果在创建LinkedHashMap时构造方法中的accessOrder设置为true
57      * 则双向链表需要按照元素访问的顺序维护双向链表中结点的前后引用关系以实现LRU算法
58      * 在每次get/put结点后，都需要调用这个回调方法，将结点在双向链表中的位置移动到尾部(因为最近这个结点被访问了)
59      * @param e
60      */
61     void afterNodeAccess(Node<K,V> e) { // move node to last
62         LinkedHashMap.Entry<K,V> last;
63         if (accessOrder && (last = tail) != e) {  //如果指定accessOrder为true并且当前访问的结点在双向链表中不是尾结点才继续做如下操作
64             LinkedHashMap.Entry<K,V> p =
65                 (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
66             p.after = null;  //将当前被访问结点在双向链表中的后驱引用设置为null
67             if (b == null)  //如果原先被访问结点的前驱引用为null，说明这个被访问结点原先就是双向链表的头结点
68                 head = a;  //将头结点变更为被访问结点的后一个结点
69             else
70                 b.after = a;  //否则将被访问结点的前一个结点的后驱指向被访问结点的后一个结点
71             if (a != null)  //如果原先被访问结点在双向链表中有下一个结点
72                 a.before = b;  //那么将下一个结点的前驱引用指向被访问结点的前一个结点
73             else
74                 last = b;  //否则将尾结点引用指向设置为当前被访问结点的前一个结点
75             if (last == null)  //如果原先双向链表中没有尾结点，则说明此次访问的结点是该双向链表中第一个结点
76                 head = p;  //将双向头结点设置为此次被访问的结点
77             else {  //将被访问的结点移动到双向链表的尾部
78                 p.before = last;  //否则将当前结点的前驱引用指向原来双向链表的尾结点
79                 last.after = p;   //再将原先双向链表尾结点的后驱引用指向当前被访问的结点
80             }
81             tail = p;  //双向链表尾结点变更为当前被访问的结点 
82             ++modCount; 
83         }
84     }