Fork me on GitHub

2019-7-19 jdk源码分析(5)-LinkedHashMap

jdk源码分析(5)-LinkedHashMap

LinkedHashMap实质是HashMap+LinkedList,提供了顺序访问的功能

一、整体结构

1. 定义

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

从上述定义中也能看到LinkedHashMap其实就是继承了HashMap,并加了双向链表记录顺序,代码和结构本身不难,但是其中结构的组织,代码复用这些地方十分值得我们学习;具体结构如图所示

2. 构造函数和成员变量

1
2
3
4
5
6
7
8
9
10
11
12
public LinkedHashMap(int initialCapacity, float loadFactor) {}
public LinkedHashMap(int initialCapacity) {}
public LinkedHashMap() {}
public LinkedHashMap(Map<? extends K, ? extends V> m) {}
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {}

/**
* The iteration ordering method for this linked hash map: <tt>true</tt>
* for access-order, <tt>false</tt> for insertion-order.
* @serial
*/
final boolean accessOrder;

可以看到LinkedHashMap的5个构造函数和HashMap的作用基本是一样的,都是初始化initialCapacityloadFactor,但是多了一个accessOrder,这也是LinkedHashMap最重要的一个成员变量了;

  • accessOrdertrue的时候,表示LinkedHashMap中记录的是访问顺序,也是就没放get一个元素的时候,这个元素就会被移到链表的尾部;
  • accessOrderfalse的时候,表示LinkedHashMap中记录的是插入顺序;

3. Entry关系

扎眼一看可能会觉得HashMap体系的节点继承关系比较混乱;一所以这样设计因为

  • LinkedHashMap继承至HashMap,其中的节点同样有普通节点和树节点两种;并且树节点很少使用;
  • 现在的设计中,树节点是可以完全复用的,但是HashMap的树节点,会浪费双向链表的能力;
  • 如果不这样设计,则至少需要两条继承关系,并且需要抽出双向链表的能力,整个继承体系以及方法的复用会变得非常复杂,不利于扩展;

二、重要方法

上面我们已经讲了LinkedHashMap就是HashMap+链表,所以我们只需要在结构有可能改变的地方加上链表的修改就可以了,结构可能改变的地方只要有put/get/replace,这里需要注意扩容的时候虽然结构改变了,但是节点的顺序仍然保持不变,所以扩容可以完全复用;

1. put 方法

  • 未找到key时,直接在最后添加一个节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
}

TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
TreeNode<K,V> p = new TreeNode<K,V>(hash, key, value, next);
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;
}
}

上面代码很简单,但是很清晰的将添加节点到最后的逻辑抽离的出来;

2. get 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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;
}

public V getOrDefault(Object key, V defaultValue) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return defaultValue;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}

get方法主要也是通过afterNodeAccess来维护链表位置关系;
以上就是LinkedHashMap链表位置关系调整的主要方法了;

3. containsValue 方法

1
2
3
4
5
6
7
8
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,在HashMap中寻找value的时候,需要遍历所有节点,他是遍历每个哈希桶,在依次遍历桶中的链表;而在LinkedHashMap里面要遍历所有节点的时候,就可以直接通过双向链表进行遍历了;

三、总结

  • 总体而言LinkedHashMap的代码比较简单
-------------本文结束感谢您的阅读-------------
坚持原创技术分享,您的支持将鼓励我继续创作!