简介
LinkedHashMap可以看错成HashMap+LinkedList
LinkedHashMap内部维护了一个双向链表,能保证元素按插入的顺序访问,也能以访问顺序访问,可以实现LRU缓存策略
LinkedHashMap继承体系
属性
/**
* 双向链表头节点
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* 双向链表尾节点
*/
transient LinkedHashMap.Entry<K,V> tail;
/**
* 是否按访问顺序排序
*/
final boolean accessOrder;
内部类
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);
}
}
构造函数
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
public LinkedHashMap() {
super();
accessOrder = false;
}
public LinkedHashMap(Map<? extends K, ? extends V> m) {
super();
accessOrder = false;
putMapEntries(m, false);
}
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
afterNodeInsertion
在节点插入之后做些什么,在HashMap中的putVal()方法中被调用,可以看到HashMap中这个方法的实现为空。
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;
}
- evict,驱逐的意思。
- 如果evict为true,且头节点不为空,且确定移除最老的元素,那么就调用HashMap.removeNode()把头节点移除(这里的头节点是双向链表的头节点,而不是某个桶中的第一个元素);
- HashMap.removeNode()从HashMap中把这个节点移除之后,会调用afterNodeRemoval()方法;
- 默认removeEldestEntry()方法返回false,也就是不删除元素
afterNodeAccess
在节点访问之后被调用,主要在put()已经存在的元素或get()时被调用,如果accessOrder为true,调用这个方法把访问到的节点移动到双向链表的末尾。
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
// 如果accessOrder为true,并且访问的节点不是尾节点
if (accessOrder && (last = tail) != e) {
// 定义当前节点p
// 当前节点前一个节点b
// 当前节点后一个节点a
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// 把p节点从双向链表中移除
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;
}
// 尾节点等于p
tail = p;
++modCount;
}
}
- 如果accessOrder为true,并且访问的节点不是尾节点;
- 拿到当前节点,当前的上一节点和当前的下一节点;
- 当前的上一节点为空,那么这个节点是首节点,设置首节点为当前的下一节点;
- 当前的上一节点不为空,那么就设置上一节点的next为当前节点的下一个节点;
- 当前的下一节点为空的,那么这个节点是尾节点,设置当前节点的上一节点为尾节点;
- 当前的下一节点不为空,那么久设置下一节点的pre为当前节点的上一节点;
afterNodeRemoval
在节点被删除之后调用的方法。
void afterNodeRemoval(Node<K,V> e) { // unlink
// 当前节点p
// 上一节点b
// 下一节点a
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// 设置当前节点前后置空,协助GC
p.before = p.after = null;
// 删除的是首节点,设置当前下一节点为首节点
if (b == null)
head = a;
else
// 设置上一节点的next为下一节点
b.after = a;
// 删除的是尾节点,把上一节点设置为尾节点
if (a == null)
tail = b;
else
// 不是尾节点,设置上一节点的后一节点为尾节点
a.before = b;
}
get
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
- 如果查找到了元素,且accessOrder为true,则调用afterNodeAccess()方法把访问的节点移到双向链表的末尾。
总结
- LinkedHashMap继承自HashMap,具有HashMap的所有特性;
- LinkedHashMap内部维护了一个双向链表存储所有的元素;
- 如果accessOrder为false,则可以按插入元素的顺序遍历元素;
- 如果accessOrder为true,则可以按访问元素的顺序遍历元素;
- LinkedHashMap的实现非常精妙,很多方法都是在HashMap中留的钩子(Hook),直接实现这些Hook就可以实现对应的功能了,并不需要再重写put()等方法;
- 默认的LinkedHashMap并不会移除旧元素,如果需要移除旧元素,则需要重写removeEldestEntry()方法设定移除策略;
- LinkedHashMap可以用来实现LRU缓存淘汰策略;
基于LinkedHashMap的LRU
import java.util.LinkedHashMap;
import java.util.Map;
public class LRUTest {
public static void main(String[] args) {
// 创建一个只有5个元素的缓存
LRU<Integer, Integer> lru = new LRU<>(5, 0.75f);
lru.put(1, 1);
lru.put(2, 2);
lru.put(3, 3);
lru.put(4, 4);
lru.put(5, 5);
lru.put(6, 6);
lru.put(7, 7);
System.out.println(lru.get(4));
lru.put(6, 666);
// 输出: {3=3, 5=5, 7=7, 4=4, 6=666}
// 可以看到最旧的元素被删除了
// 且最近访问的4被移到了后面
System.out.println(lru);
}
}
class LRU<K, V> extends LinkedHashMap<K, V> {
// 保存缓存的容量
private int capacity;
public LRU(int capacity, float loadFactor) {
super(capacity, loadFactor, true);
this.capacity = capacity;
}
/**
* 重写removeEldestEntry()方法设置何时移除旧元素
* @param eldest
* @return
*/
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
// 当元素个数大于了缓存的容量, 就移除元素
return size() > this.capacity;
}
}