一、介绍
LinkedHashMap 继承 了 HashMap。LinkedHashMap实现与HashMap的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。具有一定的顺序性。
HashMap可以参考之前的文章：https://so.csdn.net/so/search?q=HashMap&t=blog&u=weixin_43732955
public class LinkedHashMap
存储结构：
二、源码分析
那么LinkedHashMap底层是如何维护插入顺序的双链表的呢。
2.0 初始化
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
public LinkedHashMap() {
super();
accessOrder = false;
}
可以看到 LinkedHashMap底层是调用 HashMap的构造方法信息初始化
2.1 插入
插入方法为map.put()方法但是我们看到 LinkedHashMap类中并没有实现，其方法是继承了HashMap中的put方法。
/
* hash(key) 方法在jdk1.8中进行是 高位异或 目的就是为了增加散列程度
*
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node
// 数组为空 那么初始化
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
/**
* 获取当前key 的在数组中的位置
* 巧妙之处 ： 利用 n-1 & hash 替代 hash % n 求摩
*/
// 不存在
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
// 存在
Node
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 已转换为红黑树，进行红黑数的插入方法
else if (p instanceof TreeNode)
e = ((TreeNode
else {
for (int binCount = 0; ; ++binCount) {
//尾插入法 插入到最后一个元素的后面
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
//链表长度大于8 也就是存储链表的第9个元素之后
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 红黑数转换
treeifyBin(tab, hash);
break;
}
//遍历过程判断是否存在相同的key
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//如果有存在key 与put进入的key相同
//进行元素覆盖 相同的key的 覆盖
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//**** 重要 *****//
// 方法回调： key被访问后
afterNodeAccess(e);
return oldValue;
}
}
/**
* size > 容量 * 负载因子
*/
++modCount;
if (++size > threshold)
resize();
//**** 重要 *****//
// 方法回调：key被插入后
afterNodeInsertion(evict);
return null;
}
在put方法中有两个重要的回掉用函数：afterNodeAccess() 和 afterNodeInsertion(),下面来分别介绍一下这两个函数的作用；
afterNodeAccess 表示在节点值被访问之后的操作，在LinkedHashMap被重写，将访问的节点移在链表的尾部 。
/**
* 1. 使用 get 方法会访问到节点, 从而触发调用这个方法
* 2. 使用 put 方法插入节点, 如果 key 存在, 也算要访问节点, 从而触发该方法
* 3. 只有 accessOrder 是 true 才会调用该方法
* 4. 这个方法会把访问到的最后节点重新插入到双向链表结尾
*/
void afterNodeAccess(Node
// 用 last 表示插入 e 前的尾节点
// 插入 e 后 e 是尾节点, 所以也是表示 e 的前一个节点
LinkedHashMap.Entry
//如果是访问序，且当前节点并不是尾节点
//将该节点置为双向链表的尾部
if (accessOrder && (last = tail) != e) {
// p: 当前节点
// b: 前一个节点
// a: 后一个节点
// 结构为: b <=> p <=> a
LinkedHashMap.Entry
(LinkedHashMap.Entry
// 结构变成: b <=> p <- a
p.after = null;
// 如果当前节点 p 本身是头节点, 那么头结点要改成 a
if (b == null)
head = a;
// 如果 p 不是头尾节点, 把前后节点连接, 变成: b -> a
else
b.after = a;
// a 非空, 和 b 连接, 变成: b <- a
if (a != null)
a.before = b;
// 如果 a 为空, 说明 p 是尾节点, b 就是它的前一个节点, 符合 last 的定义
// 这个 else 没有意义，因为最开头if已经确保了p不是尾结点了，自然after不会是null
else
last = b;
// 如果这是空链表, p 改成头结点
if (last == null)
head = p;
// 否则把 p 插入到链表尾部
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
afterNodeInsertion()方法
/**
* 在插入之后的 回调方法，可以根据策略维护 双链表
* 因为removeEldestEntry 方法在 LinkedHashMap 当中一直是返回 false 所以这个方法不会被调用
* 备注：我们可以利用这个回调来维护 LRU
* @param evict
*/
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
// 删除队头 最久没有被访问的数据
removeNode(hash(key), key, null, false, true);
}
}
2.2 删除
也是用HashMap.remove(e)方法，在内部同样也有一个回调函数：
afterNodeRemoval(node) 在 LinkedHashMap的重写如下：
/**
* 删除当前节点
* @param e
*/
void afterNodeRemoval(Node
LinkedHashMap.Entry
(LinkedHashMap.Entry
// b - > p -> a
p.before = p.after = null;
// p 是头节点 那么 p.next 变为头节点
if (b == null)
head = a;
else
b.after = a;
// p是不是尾节点 如果是那么尾 节点为b
if (a == null)
tail = b;
// 连接前节点
else
a.before = b;
}
三、LinkedHashMap 实现 LRU
基于上述的回调函数，我们可以很快就构建一个 LRU的一个缓存存储结构。
class LRUCache extends LinkedHashMap
private int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75F, true);
this.capacity = capacity;
}
public int get(int key) {
return super.getOrDefault(key, -1);
}
//
public void put(int key, int value) {
super.put(key, value);
}
/**
* removeEldestEntry 在插入时 ，当evict为ture时，回调该函数
* 用来判断 删除队头的 条件
/
@Override
protected boolean removeEldestEntry(Map.Entry
return size() > capacity;
}
}
参考：
搞懂 Java LinkedHashMap 源码
相关链接
发表评论