最近正准备回顾一下Java,所以在此做一些记录。

LinkedHashMap继承了HashMap,大多数的操作调用的是HashMap的实现,在进行操作的时候多维护了一层双向链表

LinkedHashMap的节点也继承了HashMap的节点,多维护了前置节点和后置节点两个属性

1  static class Entry<K,V> extends HashMap.Node<K,V> {
2         Entry<K,V> before, after;
3         Entry(int hash, K key, V value, Node<K,V> next) {
4             super(hash, key, value, next);
5         }
6     }
View Code

1.put(K key, V value) 存放一个键值对,其实是调用了HashMap的put方法,通过重写HashMap里的部分方法来实现链表的维护

 1 HashMap的put方法会生成一个节点,调用了newNode方法,而LinkedHashMap重写了此方法
 2  /**
 3      * 创建一个节点
 4      * @param hash  hash值
 5      * @param key   键
 6      * @param value 值
 7      * @param e     下一个节点,这个是HashMap节点的属性
 8      * @return
 9      */
10     Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
11         //调用构造方法
12         LinkedHashMap.Entry<K,V> p =
13             new LinkedHashMap.Entry<K,V>(hash, key, value, e);
14         //维护链表
15         linkNodeLast(p);
16         return p;
17     }
18
19 /**
20      * 添加一个节点到末尾
21      * @param p 节点
22      */
23     private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
24         //保存尾部节点
25         LinkedHashMap.Entry<K,V> last = tail;
26         //更新尾部节点
27         tail = p;
28         //判断之前的尾部节点是否为空
29         if (last == null)
30             //之前的尾部节点为空,说明还没有数据,设置一下头节点
31             head = p;
32         else {
33             //说明之前已经有数据了,将新的节点作为尾部节点连接起来
34             p.before = last;
35             last.after = p;
36         }
37     }
38
39 HashMap当put一个已经存在的key时,会触发是否更新的操作,之后会调用afterNodeAccess方法,LinkedHashMap重写了此方法
40 /**
41      * accessOrder为true时,将操作的节点移到链表尾部
42      * @param e 节点
43      */
44     void afterNodeAccess(Node<K,V> e) {
45         LinkedHashMap.Entry<K,V> last;
46         //accessOrder 这个参数是指在进行操作的时候,是否将操作的节点移动到链表的最后,默认false
47         //也就是说accessOrder为false的时候链表就是按照插入顺序维护的
48         //true的时候,会将最近使用的节点移动到链表最后
49         if (accessOrder && (last = tail) != e) {
50             //保存当前节点和其前置节点和后置节点
51             LinkedHashMap.Entry<K,V> p =
52                 (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
53             //清空后置节点,因为当前节点要被移动到最后了
54             p.after = null;
55             //判断前置节点是否为空节点
56             if (b == null)
57                 //前置节点为空,说明当前节点是头节点,将它的后置节点也就是第二个节点设置为头节点
58                 head = a;
59             else
60                 //存在前置节点,将前置节点的后置节点连接到当前节点的下一个节点
61                 b.after = a;
62             //判断后置节点是否为空
63             if (a != null)
64                 //后置节点不为空,更新后置节点的前置节点
65                 a.before = b;
66             else
67                 //说明该节点就是尾部节点,设置前置节点为后节点
68                 //a == null 说明p就是尾部节点? 有点不清楚
69                 last = b;
70             //统一更新尾部节点
71             if (last == null)
72                 //说明只有这么一个节点
73                 head = p;
74             else {
75                 //将当前节点挂到链表末尾
76                 p.before = last;
77                 last.after = p;
78             }
79             //设置尾部节点
80             tail = p;
81             ++modCount;
82         }
83     }
84
85 LinkedHashMap也重写了afterNodeInsertion方法
86 void afterNodeInsertion(boolean evict) {
87         LinkedHashMap.Entry<K,V> first;
88         if (evict && (first = head) != null && removeEldestEntry(first)) {
89             K key = first.key;
90             removeNode(hash(key), key, null, false, true);
91         }
92     }
93
94 protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
95         return false;
96     }
97
98 其实LinkedHashMap中这个方法并不生效
View Code

2.get(Object key) 根据key获取值

 1 /**
 2      * 获取值
 3      * @param key 键
 4      * @return
 5      */
 6     public V get(Object key) {
 7         Node<K,V> e;
 8         //调用了HashMap中的getNode方法
 9         if ((e = getNode(hash(key), key)) == null)
10             return null;
11         if (accessOrder)
12             //移动当前操作的节点到链表最后
13             afterNodeAccess(e);
14         return e.value;
15     }
View Code

3. containsValue(Object value) 是否存在某个值

1  public boolean containsValue(Object value) {
2         //通过遍历链表实现
3         for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
4             V v = e.value;
5             if (v == value || (value != null && value.equals(v)))
6                 return true;
7         }
8         return false;
9     }
View Code

4.remove(Object key)  删除key

 1 LinkedHashMap调用了HashMap的remove方法
 2 重写了afterNodeRemoval方法
 3  /**
 4      * 删除链表中的节点
 5      * @param e
 6      */
 7     void afterNodeRemoval(Node<K,V> e) {
 8         //获取当前节点的前置后置节点
 9         LinkedHashMap.Entry<K,V> p =
10             (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
11         //清空前置后置节点
12         p.before = p.after = null;
13
14         if (b == null)
15             //前置节点为空,说明为头节点,更新头节点为后置节点
16             head = a;
17         else
18             //前置节点不为空,设置前置节点的后置节点为删除节点的后置节点
19             b.after = a;
20         if (a == null)
21             //后置节点为空,说明为尾部节点,更新尾部节点为其前置节点
22             tail = b;
23         else
24             //后置节点不为空,更新后置节点的前置节点
25             a.before = b;
26     }
View Code
01-04 08:44