LinkedHashMap源码解读
可能大家都知道，hashmap是不保证插入顺序的，LinkedHashMap是保证插入顺序的，但是如何保证插入顺序的呢
咳咳，如下会解答
LinkedHashMap还能根据访问顺序排序，mm我之前还真不知道，读完源码后才发现他跟LRU算法的逻辑一样一样哒
当然要读懂我写的前提是对hashmap源码也得研究透，我是在hashmap基础上讲的，看不懂的mm 和 gg就看下我之前写的hashmap源码，关注下我的 心情开花 就可以看啦
先看下LinkedHash的结构图
HashMap与LinkedHashMap
LinkedHashMap是HashMap的一个子类，LinkedHashMap 实现与 HashMap 的不同之处在于，LinkedHashMap 维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。如果你不明白为什么要保存插入顺序或者是访问顺序，建议你去看一下LRU算法，你就会明白LinkedHashMap的用处。
还是像之前一样，先看下LinkedHashMap的基本结构
LinkedHashMap可以看成是HashMap+LinkedList，即它即维护HashMap操作数据结构，又使用LinkedList维护插入元素的先后顺序
LinkedHashMap的定义为：
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
即LinkedHashMap 是HashMap的子类，所以LinkedHashMap 继承了HashMap中的非private得方法
LinkedHashMap有这些方法
看下LinkedHashMap的数据结构
LinkedHashMap有这些方法
看下LinkedHashMap的数据结构
private static final long serialVersionUID = 3801124242820219131L;
transient LinkedHashMap.Entry<K,V> head;
transient LinkedHashMap.Entry<K,V> tail;
final boolean accessOrder;//默认是false 按插入顺序排序
可以看到在HashMap基础上加了三个属性 head tail。是让LinkedHashMap的head和tail引用同时指向新节点，链表就算建立了，以后会有新的节点，accessOrder 0代表按插入顺序排序 1是按照访问顺序排序
插入，通过将新节点接在tail节点的后面，即可实现链表的更新
再接着看下Entry的结构
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);
}
}
继承自Node，当然就是Node里面的属性他都有
多了两个属性 before and after 意思是链表节点的前节点和后续节点
这是Entry的全部属性
K key
V value
Entry<K, V> next
int hash
Entry<K, V> before
Entry<K, V> after
童鞋们不要搞错了next和after、before
next是用于维护HashMap指定table位置上的Entry顺序的，before、after是用于维护Entry 插入的先后顺序的
然后看下LinkedHashMap的构造函数
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
public LinkedHashMap() {
super();
accessOrder = false;
}
无非就是调用父类的构造函数，赋值accessOrder 0代表按插入顺序排序 1是按照访问顺序排序
先分析按插入排序的过程
LinkedHashMap是用的父类的put方法
先看put函数
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);//如果hash桶的为空，就新建一个节点 如果是linkedHashmap还会再在顺序链表里再建一个节点
else {//如果此hash桶不为空
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
可能就会有疑问了，是怎么区分出是hashmap的插入还是LinkedHashMap的插入呢
可以看到LinkedHashMap 定义了自己的 newNode(hash, key, value, null)方法
点进他的newNode方法里面
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;
}
哇，果然有链表的插入过程呀
点进 linkNodeLast函数里看
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;//新建一个last节点指向tail尾节点
tail = p;//tail节点指向待插入的节点p
if (last == null)
head = p;//如果last节点为空说明是第一次插入 tail节点为空 那么就让head节点指向p节点
else {
p.before = last;//如果未节点不为空说明链表不为空，就是p节点插入前已经有其他节点插入了，那么就将节点插入到尾节点后面
last.after = p;
}
再看删除的过程
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);//可能会疑问 删除了hash桶里的链表节点了，那么维护顺序的双链表的删除操作在哪里呢？就在这里，接着往下看
return node;
}
}
return null;
}
看afterNodeRemoval方法
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.before = p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a == null)
tail = b;
else
a.before = b;
}
这句话大概意思就是如果要插入的节点p的前序节点为空，那么删除把head节点指向p节点的后续节点（如果p→before是空就说明p的前序节点是空的）
如果p的节点不是第一个节点 但是是最后一个节点，就把尾节点指向指向p节点的前序节点
如果p节点是中间节点，p的后序节点的前续节点指向p的前序节点
这段不懂的可以看下双链表的删除指针是什么操作的
再看get方法
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)//按插入顺序排序 accessOrder是false
afterNodeAccess(e);
return e.value;
}
按插入顺序排序 跟hashmap的差不多
以上是按插入顺序排序的过程
按访问顺序排序的过程
大家有没有联想到LRU算法呢，如果想了解LRU算法，我可以推荐一篇文章写得不错 https://segmentfault.com/a/1190000014229168 读了以后会对LRU算法有了更加深刻的理解了，那么再来看LinkedHashMap
看get函数
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)//按访问顺序排序 accessOrder是true
afterNodeAccess(e);
return e.value;
}
接着看
afterNodeAccess方法
这个方法是调整顺序链表的顺序的，把访问的key放在tail后面 如果之前有访问过key，那么这个key就在这个链表里了，那么需要删掉
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
p.after = null;//把p的后续节点指向null
if (b == null) //这两段代码意思是如果p节点是第一个节点 就让头节点指向p节点的后续节点 也就是把这个节点删了
head = a;
else //p节点不是第一个节点
b.after = a;//把p节点的前序节点的后续节点指向p节点的后续节点
if (a != null）//如果p节点不是最后一个节点 也就是说是中间节点 就把p节点的后续节点指向p节点的前序节点
a.before = b;
//前面的所有操作是在节点不是链表唯一节点的情况下的（也就是说map不只一个key value）是删除这个节点的操作
else
last = b;//p节点是最后一个节点把节点放在尾节点的后面
if (last == null) //如果p节点不是唯一的节点 就把p节点放在尾部节点后面
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
//不懂的可以参考下双链表的不同的情况下的删除操作
先看put函数
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);//如果hash桶的为空，就新建一个节点 如果是linkedHashmap还会再在顺序链表里再建一个节点
else {//如果此hash桶不为空
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);//如果key重复，在覆盖key后会调整顺序链表的顺序 这个已经在get方法里讲了，不再重复讲了
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
removeEldestEntry(first) LinkedHashMap这个返回false，意思是LinkedHashMap是不支持LRU缓存的，但是如果想支持咋办，后续讲解
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode)
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p)
tab[index] = node.next;
else //删除对应hash槽链表里的节点
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node);//删除顺序链表里的节点 此方法已经在删除链表里讲过了，就不再讲了
return node;
}
}
如果LinedHashMap 支持LRU 就是把最最近最不常访问的节点删除点，就是链表节点的第一个节点 逻辑就是找到删除节点的hash槽对应的位置，然后删除掉 然后再把key在顺序链表里删除掉
上面的代码做的事情比较简单，就是通过一些条件，判断是否移除最近最少被访问的节点。看到这里，大家应该知道上面两个方法的用途了。当我们基于 LinkedHashMap 实现缓存时，通过覆写removeEldestEntry方法可以实现自定义策略的 LRU 缓存。比如我们可以根据节点数量判断是否移除最近最少被访问的节点，或者根据节点的存活时间判断是否移除该节点等。本节所实现的缓存是基于判断节点数量是否超限的策略。在构造缓存对象时，传入最大节点数。当插入的节点数超过最大节点数时，移除最近最少被访问的节点。实现代码如下：
代码如下
public class SimpleCache<K, V> extends LinkedHashMap<K, V> {
private static final int MAX_NODE_NUM = 100;
private int limit;
public SimpleCache() {
this(MAX_NODE_NUM);
}
public SimpleCache(int limit) {
super(limit, 0.75f, true);
this.limit = limit;
}
public V save(K key, V val) {
return put(key, val);
}
public V getOne(K key) {
return get(key);
}
public boolean exists(K key) {
return containsKey(key);
}
/** * 判断节点数是否超限 * @param eldest * @return 超限返回 true，
否则返回 false */
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > limit;
}
}
测试代码如下
public class SimpleCacheTest { @Test
public void test() throws Exception {
SimpleCache<Integer, Integer> cache = new SimpleCache<>(3);
for (int i = 0; i < 10; i++) {
cache.save(i, i * i);
}
System.out.println("插入10个键值对后，缓存内容：");
System.out.println(cache + "\n");
System.out.println("访问键值为7的节点后，缓存内容：");
cache.getOne(7);
System.out.println(cache + "\n");
System.out.println("插入键值为1的键值对后，缓存内容：");
cache.save(1, 1);
System.out.println(cache);
}
}
这是我读的jdk的第四个源码了，越发的觉得有趣，我会坚持下去
作者：
猫眼电影java工程师 敏敏 爱好钻研技术，一直在成长的路上