JDK1.8源码阅读记录
JAVA.Util包
LinkedHashMap类
说明
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
LinkedHashMap继承于HashMap类，具有HashMap的绝大部分特点：key不重复，允许null，bucket桶数组+链表+红黑树的底层，不是线程安全的。
另外，LinkedHashMap不同于HashMap的是，LinkedHashMap新增了一条双向链表，存放了LinkedHashMap里的键值对，因此，与HashMap相比，虽然多出来的双向链表使LinkedHashMap在性能上略输于HashMap，但双向链表的存在，使LinkedHashMap在迭代上快于HashMap，同时LinkedHashMap的迭代还支持两种方式：要么按照LRU排列方式，要么按照元素插入的顺序。
注：LRU，Least Recently Used，即最近最少使用。LinkedHashMap按照LRU输出，即是将最近最少使用的元素优先输出，第一个输出，而最后一个输出的是LinkedHashMap最后一次调用get方法得到的元素。
成员变量
private static final long serialVersionUID = 3801124242820219131L;
/**
* The head (eldest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* The tail (youngest) of the doubly linked list.
*/
transient LinkedHashMap.Entry<K,V> tail;
/**
* 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;
- head：是LinkedHashMap用于迭代的双向链表中的头节点；
- tail：是LinkedHashMap用于迭代的双向链表中的尾节点；
- accessOrder：最终变量，一旦确定后不可修改，表明LinkedHashMap的迭代顺序是LRU还是按照插入顺序，true表示LRU顺序，false表示插入顺序。默认false。
构造方法
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
LinkedHashMap的构造方法一般都是对成员变量的初始化，如果不指定初始参数，则初始容量默认为16，负载因子默认为0.75，跟HashMap一样，accessOrder也就是迭代顺序，默认为false，按插入顺序迭代。
LinkedHashMap的键值对
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的基础上，多增了before和after变量，用于指示本节点（键值对）的前节点和后节点。
get方法
public V get(Object key) {
Node<K,V> e;
//调用HashMap的getNode的方法，根据hash和key返回节点
if ((e = getNode(hash(key), key)) == null)
return null;
//在取值后对参数accessOrder进行判断，如果为true，执行afterNodeAccess(见下)
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
此函数执行的效果就是将最近使用的Node，放在链表的最末尾
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
//仅当按照LRU原则且e不在最末尾，才执行修改链表，将e移到链表最末尾的操作
if (accessOrder && (last = tail) != e) {
//将e赋值临时节点p， b是e的前一个节点， a是e的后一个节点
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
//设置p的后一个节点为null，因为执行后p在链表末尾，after肯定为null
p.after = null;
//p前一个节点不存在，p为头部，前一个节点b不存在，那么考虑到p要放到最后面，则设置p的后一个节点a为head
if (b == null)
head = a;
else//原先p前一个节点存在，链接原先p的前节点和后节点
b.after = a;
if (a != null)//原先p的后节点存在，链接此后节点和原先p的前节点
a.before = b;
//p为尾部，后一个节点a不存在，那么考虑到统一操作，设置last为b
else
last = b;
if (last == null)//说明p为链表里的第一个节点，head=p
head = p;
//正常情况，将p设置为尾节点的准备工作，p的前一个节点为原先的last，last的after为p
else {
p.before = last;
last.after = p;
}
//将p设置为将p设置为尾节点
tail = p;
// 修改计数器+1
++modCount;
}
}
put方法
LinkedHashMap的put调用的还是HashMap里面的put，但在 HashMap 中，put 方法插入的是 HashMap 内部类 Node 类型的节点，该类型的节点并不具备与LinkedHashMap 内部类 Entry 及其子类型节点组成链表的能力。在介绍put方法前，还需要介绍下LinkedHashMap的三个工具方法
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
其中afterNodeAccess我们已经在上面介绍过了，下面来看其他2种方法
void afterNodeRemoval(Node<K,V> e) { // unlink
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// 将 p 节点的前驱后后继引用置空
p.before = p.after = null;
// b 为 null，表明 p 是头节点
if (b == null)
head = a;
else
b.after = a;
// a 为 null，表明 p 是尾节点
if (a == null)
tail = b;
else
a.before = b;
}
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);
}
}
介绍完三个工具方法，下面我们来看put方法
// 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) {...}
// 通过节点 hash 定位节点所在的桶位置，并检测桶中是否包含节点引用
if ((p = tab[i = (n - 1) & hash]) == null) {...}
else {
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) {...}
else {
// 遍历链表，并统计链表长度
for (int binCount = 0; ; ++binCount) {
// 未在单链表中找到要插入的节点，将新节点接在单链表的后面
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) {...}
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) {...}
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold) {...}
afterNodeInsertion(evict);
return null;
}
上面就是 LinkedHashMap 插入相关的源码，其中省略了部分非关键的代码。其中关键的是newNode 方法。LinkedHashMap 覆写了该方法。在这个方法中，LinkedHashMap 创建了 Entry，并通过 linkNodeLast 方法将 Entry 接在双向链表的尾部，实现了双向链表的建立。
//列表末尾的链接
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;
}
}
remove方法
与插入操作一样，LinkedHashMap 删除操作相关的代码也是直接用父类的实现。在删除节点时，父类的删除逻辑并不会修复 LinkedHashMap 所维护的双向链表，因此在删除及节点后，回调方法 afterNodeRemoval （上文已介绍）会被调用。
// HashMap 中实现
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
// 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 (p instanceof TreeNode) {...}
else {
// 遍历单链表，寻找要删除的节点，并赋值给 node 变量
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) {...}
// 将要删除的节点从单链表中移除
else if (node == p)
tab[index] = node.next;
else
p.next = node.next;
++modCount;
--size;
afterNodeRemoval(node); // 调用删除方法进行后续操作
return node;
}
}
return null;
}
在这里，主要做三件事：
- 根据 hash 定位到桶位置
- 遍历链表或调用红黑树相关的删除方法
- 从 LinkedHashMap 维护的双链表中移除要删除的节点
基于 LinkedHashMap 实现缓存
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);
}
}
// 移除最近最少被访问条件之一，通过覆盖此方法可实现不同策略的缓存
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
上面的源码的核心逻辑在一般情况下都不会被执行。做的事情比较简单，就是通过一些条件，判断是否移除最近最少被访问的节点。当我们基于 LinkedHashMap 实现缓存时，通过覆写removeEldestEntry方法可以实现自定义策略的 LRU 缓存。比如我们可以根据节点数量判断是否移除最近最少被访问的节点，或者根据节点的存活时间判断是否移除该节点等。
小结
在日常开发中，LinkedHashMap 的使用频率虽不及 HashMap，但它也个重要的实现。在 Java 集合框架中，HashMap、LinkedHashMap 和 TreeMap 三个映射类基于不同的数据结构，并实现了不同的功能。HashMap 底层基于拉链式的散列结构，并在 JDK 1.8 中引入红黑树优化过长链表的问题。基于这样结构，HashMap 可提供高效的增删改查操作。LinkedHashMap 在其之上，通过维护一条双向链表，实现了散列数据结构的有序遍历。TreeMap 底层基于红黑树实现，利用红黑树的性质，实现了键值对排序功能。
![Java小案例——随机数猜测随机数猜测[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)