精尽 JDK 源码解析 —— 集合（四）哈希表 LinkedHashMap

众所周知，HashMap 提供的访问，是无序的。而在一些业务场景下，我们希望能够提供有序访问的 HashMap 。那么此时，我们就有两种选择：

• TreeMap ：按照 key 的顺序。
• LinkedHashMap ：按照 key 的插入和访问的顺序。

LinkedHashMap ，在 HashMap 的基础之上，提供了顺序访问的特性。而这里的顺序，包括两种：

• 按照 key-value 的插入顺序进行访问。关于这一点，相信大多数人都知道。> 艿艿：如果不知道，那就赶紧知道。这不找抽么，哈哈哈。

• 按照 key-value 的访问顺序进行访问。通过这个特性，我们实现基于 LRU 算法的缓存。😈 相信这一点，可能还是有部分胖友不知道的噢，下文我们也会提供一个示例。> 艿艿：面试中，有些面试官会喜欢问你，如何实现一个 LRU 的缓存。

实际上，LinkedHashMap 可以理解成是 LinkedList + HashMap 的组合。为什么这么说呢？让我们带着这样的疑问，一起往下看。

LinkedHashMap 实现的接口、继承的类，如下图所示：类图

• 实现 Map 接口。
• 继承 HashMap 类。

😈 很简单，很粗暴。嘿嘿~

艿艿：因为 LinkedHashMap 继承自 HashMap 类，所以它的代码并不多，不到 500 行。

在开始看 LinkedHashMap 的属性之前，我们先来看在 《精尽 JDK 源码解析 —— 集合（三）哈希表 HashMap》 看到的 HashMap 的 Node 子类图：
Node 类图

在图中，我们可以看到 LinkedHashMap 实现了自定义的节点 Entry ，一个支持指向前后节点的 Node 子类。代码如下：

static class Entry extends HashMap.Node {

Entry before,
after;

Entry(int hash, K key, V value, Node next) {
super(hash, key, value, next);
}

}

• before 属性，指向前一个节点。after 属性，指向后一个节点。
• 通过 before + after 属性，我们就可以形成一个以 Entry 为节点的链表。😈 胖友，发挥下你的想象力。

既然 LinkedHashMap 是 LinkedList + HashMap 的组合，那么必然就会有头尾节点两兄弟。所以属性如下：

transient LinkedHashMap.Entry head;

transient LinkedHashMap.Entry tail;

final boolean accessOrder;

• 仔细看下每个属性的注释。
• head + tail 属性，形成 LinkedHashMap 的双向链表。而访问的顺序，就是 head => tail 的过程。
• accessOrder 属性，决定了 LinkedHashMap 的顺序。也就是说:
  • true 时，当 Entry 节点被访问时，放置到链表的结尾，被 tail 指向。
  • false 时，当 Entry 节点被添加时，放置到链表的结尾，被 tail 指向。如果插入的 key 对应的 Entry 节点已经存在，也会被放到结尾。

总结来说，就是如下一张图：

FROM 《Working of LinkedHashMap》
LinkedHashMap 结构图

LinkedHashMap 一共有 5 个构造方法，其中四个和 HashMap 相同，只是多初始化 accessOrder = false 。所以，默认使用插入顺序进行访问。

另外一个 #LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) 构造方法，允许自定义 accessOrder 属性。代码如下：

public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}

在插入 key-value 键值对时，例如说 #put(K key, V value) 方法，如果不存在对应的节点，则会调用 #newNode(int hash, K key, V value, Node<K,V> e) 方法，创建节点。

因为 LinkedHashMap 自定义了 Entry 节点，所以必然需要重写该方法。代码如下：

Node newNode(int hash, K key, V value, Node e) {

LinkedHashMap.Entry p =
new LinkedHashMap.Entry<>(hash, key, value, e);

linkNodeLast(p);

return p;
}

• <1> 处，创建 Entry 节点。虽然此处传入 e 作为 Entry.next 属性，指向下一个节点。但是实际上，#put(K key, V value) 方法中，传入的 e = null 。
• <2> 处，调用 #linkNodeLast(LinkedHashMap.Entry<K,V> p) 方法，添加到结尾。代码如下：
  private void linkNodeLast(LinkedHashMap.Entry p) {
  LinkedHashMap.Entry last = tail;
  tail = p;
  if (last == null)
  head = p;
  else {
  p.before = last;
  last.after = p;
  }
  }
  • 这样，符合越新的节点，放到链表的越后面。

在 HashMap 的读取、添加、删除时，分别提供了 #afterNodeAccess(Node<K,V> e)、#afterNodeInsertion(boolean evict)、#afterNodeRemoval(Node<K,V> e) 回调方法。这样，LinkedHashMap 可以通过它们实现自定义拓展逻辑。

6.1 afterNodeAccess

在 accessOrder 属性为 true 时，当 Entry 节点被访问时，放置到链表的结尾，被 tail 指向。所以 #afterNodeAccess(Node<K,V> e) 方法的代码如下：

void afterNodeAccess(Node e) {
LinkedHashMap.Entry last;

if (accessOrder && (last = tail) != e) {

LinkedHashMap.Entry p =
(LinkedHashMap.Entry)e, b = p.before, a = p.after;

p.after = null;

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.before = last;
last.after = p;
}

tail = p;

++modCount;
}
}

• 代码已经添加详细的注释，胖友认真看看噢。
• 链表的操作看起来比较繁琐，实际一共分成两步：1）第一步，将 p 从链表中移除；2）将 p 添加到链表的尾巴。

因为 HashMap 提供的 #get(Object key) 和 #getOrDefault(Object key, V defaultValue) 方法，并未调用 #afterNodeAccess(Node<K,V> e) 方法，这在按照读取顺序访问显然不行，所以 LinkedHashMap 重写这两方法的代码，如下：

public V get(Object key) {

Node e;
if ((e = getNode(hash(key), key)) == null)
return null;

if (accessOrder)
afterNodeAccess(e);
return e.value;
}

public V getOrDefault(Object key, V defaultValue) {

Node e;
if ((e = getNode(hash(key), key)) == null)
return defaultValue;

if (accessOrder)
afterNodeAccess(e);
return e.value;
}

6.2 afterNodeInsertion

在开始看 #afterNodeInsertion(boolean evict) 方法之前，我们先来看看如何基于 LinkedHashMap 实现 LRU 算法的缓存。代码如下：

class LRUCache extends LinkedHashMap {

private final int CACHE_SIZE;

public LRUCache(int cacheSize) {

super((int) Math.ceil(cacheSize / 0.75) + 1, 0.75f, true);
CACHE_SIZE = cacheSize;
}

@Override
protected boolean removeEldestEntry(Map.Entry eldest) {

return size()> CACHE_SIZE;
}

}

为什么能够这么实现呢？我们在 #afterNodeInsertion(boolean evict) 方法中来理解。代码如下：

void afterNodeInsertion(boolean evict) {
LinkedHashMap.Entry first;

if (evict && (first = head) != null && removeEldestEntry(first)) {

K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}

• <1> 处，调用 #removeEldestEntry(Map.Entry<K,V> eldest) 方法，判断是否移除最老节点。代码如下：
  protected boolean removeEldestEntry(Map.Entry eldest) {
  return false;
  }
  • 默认情况下，都不移除最老的节点。所以在上述的 LRU 缓存的示例，重写了该方法，判断 LinkedHashMap 是否超过缓存最大大小。如果是，则移除最老的节点。
• <2> 处，如果满足条件，则调用 #removeNode(...) 方法，移除最老的节点。

😈 这样，是不是很容易理解基于 LinkedHashMap 实现 LRU 算法的缓存。

6.3 afterNodeRemoval

在节点被移除时，LinkedHashMap 需要将节点也从链表中移除，所以重写 #afterNodeRemoval(Node<K,V> e) 方法，实现该逻辑。代码如下：

void afterNodeRemoval(Node e) {

LinkedHashMap.Entry p =
(LinkedHashMap.Entry)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;
}

因为 LinkedHashMap 需要满足按顺序访问，所以需要重写 HashMap 提供的好多方法，例如说本小节我们看到的几个。

#keysToArray(T[] a) 方法，转换出 key 数组顺序返回。代码如下：

@Override
final T[] keysToArray(T[] a) {
Object[] r = a;
int idx = 0;

for (LinkedHashMap.Entry e = head; e != null; e = e.after) {
r[idx++] = e.key;
}
return a;
}

• 要小心噢，必须保证 a 放得下 LinkedHashMap 所有的元素。

#valuesToArray(T[] a) 方法，转换出 value 数组顺序返回。代码如下：

@Override
final T[] valuesToArray(T[] a) {
Object[] r = a;
int idx = 0;

for (LinkedHashMap.Entry e = head; e != null; e = e.after) {
r[idx++] = e.value;
}
return a;
}

艿艿：看到此处，胖友基本可以结束本文落。

#keySet() 方法，获得 key Set 。代码如下：

public Set keySet() {

Set ks = keySet;

if (ks == null) {
ks = new LinkedKeySet();
keySet = ks;
}
return ks;
}

• 其中， LinkedKeySet 是 LinkedHashMap 自定义的 Set 实现类。代码如下：
  final class LinkedKeySet extends AbstractSet {
  public final int size() { return size;}
  public final void clear() { LinkedHashMap.this.clear(); }
  public final Iterator iterator() {
  return new LinkedKeyIterator();
  }
  public final boolean contains(Object o) { return containsKey(o); }
  public final boolean remove(Object key) {
  return removeNode(hash(key), key, null, false, true) != null;
  }
  public final Spliterator spliterator() {
  return Spliterators.spliterator(this, Spliterator.SIZED |
  Spliterator.ORDERED |
  Spliterator.DISTINCT);
  }
  public Object[] toArray() {
  return keysToArray(new Object[size]);
  }
  public T[] toArray(T[] a) {
  return keysToArray(prepareArray(a));
  }
  public final void forEach(Consumer<? super K> action) {
  if (action == null)
  throw new NullPointerException();
  int mc = modCount;
  for (LinkedHashMap.Entry e = head; e != null; e = e.after)
  action.accept(e.key);
  if (modCount != mc)
  throw new ConcurrentModificationException();
  }
  }
  • 其内部，调用的都是 LinkedHashMap 提供的方法。

#values() 方法，获得 value Collection 。代码如下：

public Collection values() {

Collection vs = values;

if (vs == null) {
vs = new LinkedValues();
values = vs;
}
return vs;
}

• 其中， LinkedValues 是 LinkedHashMap 自定义的 Collection 实现类。代码如下：
  final class LinkedValues extends AbstractCollection {
  public final int size() { return size;}
  public final void clear() { LinkedHashMap.this.clear(); }
  public final Iterator iterator() {
  return new LinkedValueIterator();
  }
  public final boolean contains(Object o) { return containsValue(o); }
  public final Spliterator spliterator() {
  return Spliterators.spliterator(this, Spliterator.SIZED |
  Spliterator.ORDERED);
  }
  public Object[] toArray() {
  return valuesToArray(new Object[size]);
  }
  public T[] toArray(T[] a) {
  return valuesToArray(prepareArray(a));
  }
  public final void forEach(Consumer<? super V> action) {
  if (action == null)
  throw new NullPointerException();
  int mc = modCount;
  for (LinkedHashMap.Entry e = head; e != null; e = e.after)
  action.accept(e.value);
  if (modCount != mc)
  throw new ConcurrentModificationException();
  }
  }
  • 其内部，调用的都是 LinkedHashMap 提供的方法。

#entrySet() 方法，获得 key-value Set 。代码如下：

public Set> entrySet() {
Set> es;

return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;
}

• 其中， LinkedEntrySet 是 LinkedHashMap 自定义的 Set 实现类。代码如下：
  final class LinkedEntrySet extends AbstractSet> {
  public final int size() { return size;}
  public final void clear() { LinkedHashMap.this.clear(); }
  public final Iterator> iterator() {
  return new LinkedEntryIterator();
  }
  public final boolean contains(Object o) {
  if (!(o instanceof Map.Entry))
  return false;
  Map.Entry e = (Map.Entry) o;
  Object key = e.getKey();
  Node candidate = getNode(hash(key), key);
  return candidate != null && candidate.equals(e);
  }
  public final boolean remove(Object o) {
  if (o instanceof Map.Entry) {
  Map.Entry e = (Map.Entry) o;
  Object key = e.getKey();
  Object value = e.getValue();
  return removeNode(hash(key), key, value, true, true) != null;
  }
  return false;
  }
  public final Spliterator> spliterator() {
  return Spliterators.spliterator(this, Spliterator.SIZED |
  Spliterator.ORDERED |
  Spliterator.DISTINCT);
  }
  public final void forEach(Consumer<? super Map.Entry> action) {
  if (action == null)
  throw new NullPointerException();
  int mc = modCount;
  for (LinkedHashMap.Entry e = head; e != null; e = e.after)
  action.accept(e);
  if (modCount != mc)
  throw new ConcurrentModificationException();
  }
  }
  • 其内部，调用的都是 LinkedHashMap 提供的方法。

在上面的代码中，艿艿实际标记了三处 <X> 标记，分别是 LinkedKeyIterator、LinkedValueIterator、LinkedEntryIterator ，用于迭代遍历 key、value、Entry 。而它们都继承了 LinkedHashIterator 抽象类，代码如下：

abstract class LinkedHashIterator {

LinkedHashMap.Entry next;

LinkedHashMap.Entry current;

int expectedModCount;

LinkedHashIterator() {
next = head;
expectedModCount = modCount;
current = null;
}

public final boolean hasNext() {
return next != null;
}

final LinkedHashMap.Entry nextNode() {
LinkedHashMap.Entry e = next;

if (modCount != expectedModCount)
throw new ConcurrentModificationException();

if (e == null)
throw new NoSuchElementException();

current = e;
next = e.after;
return e;
}

public final void remove() {

Node p = current;
if (p == null)
throw new IllegalStateException();

if (modCount != expectedModCount)
throw new ConcurrentModificationException();

current = null;

removeNode(p.hash, p.key, null, false, false);

expectedModCount = modCount;
}

}

final class LinkedKeyIterator extends LinkedHashIterator
implements Iterator {

public final K next() { return nextNode().getKey(); }
}

final class LinkedValueIterator extends LinkedHashIterator
implements Iterator {

public final V next() { return nextNode().value; }
}

final class LinkedEntryIterator extends LinkedHashIterator
implements Iterator> {

public final Map.Entry next() { return nextNode(); }
}

#clear() 方法，清空 LinkedHashMap 。代码如下：

public void clear() {

super.clear();

head = tail = null;
}

• 需要额外清空 head、tail 。

本小节，我们会罗列下其他 LinkedHashMap 重写的方法。当然，可以选择不看。

在序列化时，会调用到 #internalWriteEntries(java.io.ObjectOutputStream s) 方法，重写代码如下：

void internalWriteEntries(java.io.ObjectOutputStream s) throws IOException {

for (LinkedHashMap.Entry e = head; e != null; e = e.after) {

s.writeObject(e.key);

s.writeObject(e.value);
}
}

在反序列化时，会调用 #reinitialize() 方法，重写代码如下：

void reinitialize() {

super.reinitialize();

head = tail = null;
}

查找值时，会调用 #containsValue(Object value) 方法，重写代码如下：

public boolean containsValue(Object value) {

for (LinkedHashMap.Entry e = head; e != null; e = e.after) {
V v = e.value;

if (v == value || (value != null && value.equals(v)))
return true;
}
return false;
}

如下几个方法，是 LinkedHashMap 重写和红黑树相关的几个方法，胖友可以自己瞅瞅：

• #replacementNode(Node<K,V> p, Node<K,V> next)
• #newTreeNode(int hash, K key, V value, Node<K,V> next)
• #replacementTreeNode(Node<K,V> p, Node<K,V> next)
• #transferLinks(LinkedHashMap.Entry<K,V> src, LinkedHashMap.Entry<K,V> dst)

下面，我们来对 LinkedHashMap 做一个简单的小结：

• LinkedHashMap 是 HashMap 的子类，增加了顺序访问的特性。
  • 【默认】当 accessOrder = false 时，按照 key-value 的插入顺序进行访问。
  • 当 accessOrder = true 时，按照 key-value 的读取顺序进行访问。
• LinkedHashMap 的顺序特性，通过内部的双向链表实现，所以我们把它看成是 LinkedList + LinkedHashMap 的组合。
• LinkedHashMap 通过重写 HashMap 提供的回调方法，从而实现其对顺序的特性的处理。同时，因为 LinkedHashMap 的顺序特性，需要重写 #keysToArray(T[] a) 等遍历相关的方法。
• LinkedHashMap 可以方便实现 LRU 算法的缓存，
  http://svip.iocoder.cn/JDK/Collection-LinkedHashMap/