Java源码系列3——LinkedHashMap
什么是LinkedHashMap？
LinkedHashMap 是 HashMap 的有序实现。LinkedHashMap 用一条双向链表来维护顺序，迭代的时候也使用自己实现的迭代器。
public static void main(String[] args) {
HashMap<String, Integer> h = new HashMap<>(33);
h.put("one", 1);
h.put("two", 2);
h.put("three", 3);
h.put("four", 4);
for (String key : h.keySet()) {
System.out.println("key:" + key + "value:" + h.get(key));
}
LinkedHashMap<String, Integer> lh = new LinkedHashMap<>(33);
lh.put("one", 1);
lh.put("two", 2);
lh.put("three", 3);
lh.put("four", 4);
for (String key : lh.keySet()) {
System.out.println("key:" + key + "value:" + lh.get(key));
}
}输出
key:twovalue:2
key:threevalue:3
key:fourvalue:4
key:onevalue:1
key:onevalue:1
key:twovalue:2
key:threevalue:3
key:fourvalue:4底层数组结构
HashMap的底层是由数组，链表，红黑树组成的。数组用来存储节点，当出现哈希碰撞时使用链表存储，当链表超过一定长度后会优化成红黑树。
LinkedHashMap 的底层除了继承自 HashMap 的数组，链表，红黑树，还多了链接所有节点的双向链表（图中红色和绿色箭头），用于存储各个节点的顺序。
Entry的继承关系
LinkedHashMap.Entry 继承了 HashMap.Node，多维护了 before 和 after 两个指针，这两个属性指向该Entry的前一个Entry和后一个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);
}
}但是 LinkedHashMap 中确没有覆写 HashMap 中 TreeNode 的代码，那红黑树中各个节点的顺序是如何存储的。
我们可以从 HashMap.TreeNode 的继承关系中找出端倪：
呦吼，这一小家子也真够乱的，子类继承了父类的内部类，父类的内部类又继承了子类的内部类，上演一出鸡生蛋，蛋生鸡的戏码。
// 继承了 LinkedHashMap.Entry
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
}为什么 HashMap.TreeNode 要继承 LinkedHashMap.Entry，继承过来的 before 和 after 指针在 HashMap 中也没有被用到，何不直接继承 HashMap.Node？
这样的继承关系其实并不是为 HashMap 设计的，在 HashMap 中确实没什么用。但在 LinkedHashMap 中，就可以直接使用继承过来的 HashMap.TreeNode，因为 TreeNode 这个类通过继承已经拥有了 before 和 after 指针。
这就是为什么，LinkedHashMap 中有一个继承了 HashMap.Node 的内部类，却没有继承 HashMap.TreeNode 的内部类。
链表的创建过程
链表的创建过程是在第一个元素插入的时候才开始的，一开始链表的头部(head)和尾巴(tail)都为null。
LinkedHashMap 没有覆写父类的put方法，元素的插入流程基本相同，只是 HashMap 插入的是 Node 类型的节点，LinkedHashMap 插入的是 Entry 类型的节点，并且更新链表。
那么 LinkedHashMap 是怎么插入节点，并且更新链表的呢？
// HashMap 中实现
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
// HashMap 中实现
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);
// 哈希碰撞了，本节不介绍，可以看上一篇讲 HashMap 的文章
else {
// ... 省略部分代码
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}
// HashMap 中实现的 newNode
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}
// LinkedHashMap 中覆写的 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;
}
// LinkedHashMap 中实现
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
LinkedHashMap.Entry<K,V> last = tail;
tail = p;
// 如果链表为空，头部和尾部都赋值为p
if (last == null)
head = p;
// 把新插入的节点放在链表尾部
else {
p.before = last;
last.after = p;
}
}从代码里可以很明显的看出，LinkedHashMap 中索引的计算，桶的赋值，哈希碰撞时链表或者红黑树的创建，都使用的 HashMap 的实现。LinkedHashMap 只需要覆写节点的创建，并且在创建节点的时候，更新储存顺序的链表。真的是把复用利用到了极致。
节点的删除
与插入操作一样，LinkedHashMap 也是使用的父类的删除操作，然后覆写了回调方法 afterNodeRemoval，用于维护双向链表。
// HashMap 中实现
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 (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);
return node;
}
}
return null;
}
// LinkedHashMap 中覆写
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;
// 如果b为空，则为头节点
if (b == null)
head = a;
else
b.after = a;
// 如果a为空，则为尾节点
if (a == null)
tail = b;
else
a.before = b;
}访问顺序的维护
如果我们在初始化 LinkedHashMap 时，把 accessOrder 参数设为 true，那么我们不仅在插入的时候会维护链表，在访问节点的时候也会维护链表。
当我们调用 get, getOrDefault, replace 等方法时，会更新链表，把访问的节点移动到链表尾部。
// LinkedHashMap 中覆写
public V get(Object key) {
Node<K,V> e;
// 调用了 HashMap 中的 getNode 方法
if ((e = getNode(hash(key), key)) == null)
return null;
// 如果accessOrder为true，调用afterNodeAccess
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
// LinkedHashMap 中覆写
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;
// 如果b为空，则为头部
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
// 尾部不会为空，不知为何要多一个判断
else
last = b;
if (last == null)
head = p;
else {
// 把尾部赋值为p
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}使用测试代码体验一下效果
public static void main(String[] args) {
LinkedHashMap<String, Integer> lh = new LinkedHashMap<>(33, 0.75f, true);
lh.put("one", 1);
lh.put("two", 2);
lh.put("three", 3);
lh.put("four", 4);
lh.get("two");
for (String key : lh.keySet()) {
System.out.println("key:" + key + "value:" + lh.get(key));
}
}竟然报错了
看一下 LinkedHashMap 覆写的迭代器代码
final LinkedHashMap.Entry<K,V> nextNode() {
LinkedHashMap.Entry<K,V> e = next;
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
current = e;
next = e.after;
return e;
}ConcurrentModificationException 这个报错是为了防止并发条件下，遍历的同时链表发生变化。因为我们在遍历的时候又调用了 get 方法，导致链表发生变化，才会抛这个错。
accessOrder 为 true 时的正确遍历姿势如下，使用 LinkedHashMap 覆写forEach 方法，就不会在读取值的时候修改顺序链表了。
lh.forEach((String k, Integer v) -> {
System.out.println("key:" + k + ", value:" + v);
});使用 LinkedHashMap 实现简单的 LRU
LRU 全称 Least Recently Used，也就是最近最少使用的意思，是一种内存管理算法，该算法最早应用于 Linux 操作系统。 这个算法基于一种假设：长期不被使用的数据，在未来被用到的几率也不大。因此，当数据所占内存达到一定阈值时，我们要移除最近最少被使用的数据。
下面我们介绍一下前置知识。
afterNodeInsertion 是一个回调方法，在插入元素的时候回调。LinkedHashMap 覆写了这个方法，主要用来判断是否需要将链表的 head 移除。
// LinkedHashMap 中覆写
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
// 根据条件判断是否移除链表的head节点
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
// LinkedHashMap 中实现，默认返回false
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}下面我们将继承 LinkedHashMap，通过覆写 removeEldestEntry，达到当 Map 的节点个数超过指定阈值时，删除最少访问的节点。从而实现 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;
}
/**
* 判断节点数是否超出限制
* @param eldest
* @return boolean
*/
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > limit;
}
/**
* 测试
*/
public static void main(String[] args) {
SimpleCache<Integer, Integer> cache = new SimpleCache<>(3);
for (int i = 0; i < 10; i++) {
cache.put(i, i * i);
}
System.out.println("插入10个键值对后，缓存内容：");
System.out.println(cache);
System.out.println("访问键值为7的节点后，缓存的内容：");
cache.get(7);
System.out.println(cache);
System.out.println("插入键值为1的键值对后，缓存的内容：");
cache.put(1, 1);
System.out.println(cache);
}
}测试结果如下：
总结
本文围绕 LinkedHashMap 如何维护存储顺序的双向链表展开，介绍了 LinkedHashMap 和 HashMap 节点类的继承关系，介绍了新增，删除，访问时，LinkedHashMap 如何在复用 HashMap 的同时，维护双向链表。最后通过继承 LinkedHashMap 很简单的实现了 LRU 缓存策略。
全文的代码量较多，但都较为好理解。理解JDK的设计思路，探寻背后的实现原理，也是一件很有趣的事。
本文讨论的源代码都基于JDK1.8版本。
参考资料
【Java入门提高篇】Day28 Java容器类详解（十）LinkedHashMap详解
本文首发于我的个人博客 http://chaohang.top 作者张小超 转载请注明出处