LinkedHashMap源码简读

LinkedHashMap

1、LinkedHashMap继承自HashMap&＃xff0c;HashMap具有的特性它都具有。

2、实际上&＃xff0c;LinkedHashMap是通过双向链表和散列表这两种数据组合实现的。LinkedHashMap中的“Linked”实际上指的是双向链表&＃xff0c;并非指“用链表法解决散列冲突”。

3、LinkedHashMap不仅支持按照插入顺序遍历数据&＃xff0c;还支持按照访问顺序来遍历数据。通过设置accessOrder属性为true即可。也就是说它本身就是一个支持LRU缓存淘汰策略的缓存系统。

查询、插入、删除方法。

LinkedHashMap继承自HashMap&＃xff0c;而HashMap是用散列表实现的&＃xff0c;所以LinkedHashMap在HashMap的基础上增加了双向链表来存储数据。那么是在哪儿添加的呢&＃xff1f;我们对get、put、remove三个方法逐个分析。

首先LinkedHashMap中关于双向链表的变量定义&＃xff1a;

/*** The head (eldest) of the doubly linked list.*/
transient LinkedHashMapEntry head;/*** The tail (youngest) of the doubly linked list.*/
transient LinkedHashMapEntry tail;


LinkedHashMap#get(Object key)方法

public V get(Object key) {Node e;if ((e &＃61; getNode(hash(key), key)) &＃61;&＃61; null)return null;if (accessOrder)afterNodeAccess(e);return e.value;
}


LinkedHashMap重写了HashMap中的get(Object key)方法&＃xff0c;主要就是增加了accessOrder相关操作。核心的查找操作还是通过HashMap中的方法去进行。

LinkedHashMap#put(K key, V value)方法

LinkedHashMap完全继承了HasMap的get(K key, V value)方法&＃xff0c;没有做任何修改&＃xff0c;那么是它是如何将新增的数据也添加进双向链表中呢&＃xff1f;

HashMap中&＃xff0c;put方法调用了putVal方法&＃xff0c;代码如下&＃xff1a;

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node[] tab; Node p; int n, i;if ((tab &＃61; table) &＃61;&＃61; null || (n &＃61; tab.length) &＃61;&＃61; 0)n &＃61; (tab &＃61; resize()).length;if ((p &＃61; tab[i &＃61; (n - 1) & hash]) &＃61;&＃61; null)// 注释一tab[i] &＃61; newNode(hash, key, value, null);else {Node e; K k;if (p.hash &＃61;&＃61; hash &&((k &＃61; p.key) &＃61;&＃61; key || (key !&＃61; null && key.equals(k))))e &＃61; p;else if (p instanceof TreeNode)e &＃61; ((TreeNode)p).putTreeVal(this, tab, hash, key, value);else {for (int binCount &＃61; 0; ; &＃43;&＃43;binCount) {if ((e &＃61; p.next) &＃61;&＃61; null) {// 注释二p.next &＃61; newNode(hash, key, value, null);if (binCount >&＃61; TREEIFY_THRESHOLD - 1) // -1 for 1sttreeifyBin(tab, hash);break;}if (e.hash &＃61;&＃61; hash &&((k &＃61; e.key) &＃61;&＃61; key || (key !&＃61; null && key.equals(k))))break;p &＃61; e;}}if (e !&＃61; null) { // existing mapping for keyV oldValue &＃61; e.value;if (!onlyIfAbsent || oldValue &＃61;&＃61; null)e.value &＃61; value;// 注释三afterNodeAccess(e);return oldValue;}}&＃43;&＃43;modCount;if (&＃43;&＃43;size > threshold)resize();afterNodeInsertion(evict);return null;
}


如上所示&＃xff0c;HashMap在插入数据时&＃xff0c;会先去查找该数据是否已存在。如果不存在&＃xff0c;就调用newNode方法来创建新元素&＃xff1b;如果存在&＃xff0c;就进行相应的处理&＃xff0c;同时调用afterNodeAccess方法。需要注意的是newNode和afterNodeAccess均已被LinkedHashMap重写&＃xff0c;做了额外的工作&＃xff0c;来讲数据添加进双向链表里面。

下面针对细节进行解释&＃xff1a;
注释一&＃xff1a;
这里新生成了一个node&＃xff0c;然后将其插入到数组中。
另外newNode方法被LinkedHashMap重写了&＃xff0c;它在new的同时&＃xff0c;还将node添加进了双向链表。
LinkedHashMap#newNode():

Node newNode(int hash, K key, V value, Node e) {LinkedHashMapEntry p &＃61;new LinkedHashMapEntry(hash, key, value, e);linkNodeLast(p);return p;
}


LinkedHashMap#linkNodeLast():将node链接到双向链表尾部。

// link at the end of list
private void linkNodeLast(LinkedHashMapEntry p) {LinkedHashMapEntry last &＃61; tail;tail &＃61; p;if (last &＃61;&＃61; null)head &＃61; p;else {p.before &＃61; last;last.after &＃61; p;}
}


注释二&＃xff1a;操作同上。

注释三&＃xff1a;
先看下HashMap中afterNodeAccess方法的定义&＃xff0c;注释写的很明白&＃xff0c;下面三个方法是专门让LinkedHashMap去重写的。

// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node p) { }


那我们来看下LinkedHashMap中的afterNodeAccess方法&＃xff1a;将node移动到链表结尾。

void afterNodeAccess(Node e) { // move node to lastLinkedHashMapEntry last;if (accessOrder && (last &＃61; tail) !&＃61; e) {LinkedHashMapEntry p &＃61;(LinkedHashMapEntry)e, b &＃61; p.before, a &＃61; p.after;p.after &＃61; null;if (b &＃61;&＃61; null)head &＃61; a;elseb.after &＃61; a;if (a !&＃61; null)a.before &＃61; b;elselast &＃61; b;if (last &＃61;&＃61; null)head &＃61; p;else {p.before &＃61; last;last.after &＃61; p;}tail &＃61; p;&＃43;&＃43;modCount;}
}


LinkedHashMap#remove(Object key)方法

LinkedHashMap也是继承自

public V remove(Object key) {Node e;return (e &＃61; removeNode(hash(key), key, null, false, true)) &＃61;&＃61; null ?null : e.value;
}


LinkedHashMap#removeNode方法&＃xff1a;

final Node removeNode(int hash, Object key, Object value,boolean matchValue, boolean movable) {Node[] tab; Node p; int n, index;if ((tab &＃61; table) !&＃61; null && (n &＃61; tab.length) > 0 &&...if (node !&＃61; null && (!matchValue || (v &＃61; node.value) &＃61;&＃61; value ||(value !&＃61; null && value.equals(v)))) {...afterNodeRemoval(node);return node;}}return null;
}


可以看到&＃xff0c;删除时调用了afterNodeRemoval方法&＃xff0c;这个方法在HashMap中是空实现&＃xff0c;在LinkedHashMap中被重写。
LinkedHashMap#afterNodeRemoval方法&＃xff1a;将node元素从双向链表中移除。

void afterNodeRemoval(Node e) { // unlinkLinkedHashMapEntry p &＃61;(LinkedHashMapEntry)e, b &＃61; p.before, a &＃61; p.after;p.before &＃61; p.after &＃61; null;if (b &＃61;&＃61; null)head &＃61; a;elseb.after &＃61; a;if (a &＃61;&＃61; null)tail &＃61; b;elsea.before &＃61; b;
}


总结&＃xff1a;

HashMap底层是用数组来实现的&＃xff0c;利用散列表我们可以实现快速访问、存取元素&＃xff0c;但是元素的顺序得不到保障。
LinkedHashMap在HashMap的基础上&＃xff0c;将元素添加进了双向链表中&＃xff0c;所以可以在快速访问、存取元素的同时&＃xff0c;还可以保证元素的顺序。
另外&＃xff0c;LinkedHashMap天生就是一个支持LRU缓存淘汰策略的缓存系统。

参考&＃xff1a;
https://time.geekbang.org/column/article/64858