LinkedHashMap
LinkedHashMap 能解决什么问题？什么时候使用 LinkedHashMap?
1）LinkedHashMap 按照键值对的插入顺序进行遍历，LinkedHashMap 底层通过一个双向链表来维护 Entry 的顺序，重新插入已经存在的键，不会影响迭代顺序。
2）LinkedHashMap 的 collection 视图迭代器所需时间与映射的大小成正比，而 HashMap 迭代所需的时间与其容量成正比。
3）LinkedHashMap 返回的迭代器都是快速失败的，如果从结构上对其进行修改，除非使用迭代器自身的 remove 方法，否则迭代器将抛出 ConcurrentModificationException 异常。
4）LinkedHashMap 的遍历只跟元素个数有关，和其容量无关。
如何使用 LinkedHashMap?
1）需要维护对象间的映射关系，并且需要保证迭代顺序时，可以使用 LinkedHashMap。
2）LinkedHashMap 可以用于实现简单的 LRU 缓存。
使用 LinkedHashMap 有什么风险？
1）LinkedHashMap 需要使用额外的链表来保存元素顺序，且容量必须为 2 的幂，存在一定的内存浪费。
2）LinkedHashMap 插入时需要维护链表中元素的顺序，其插入速度比 HashMap 慢。
LinkedHashMap 核心操作的实现原理？
/**
* HashMap.Node subclass for normal LinkedHashMap entries.
*/
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);
}
}
/**
* 双向链表的头节点
*/
transient LinkedHashMap.Entry<K,V> head;
/**
* 双向链表的尾节点
*/
transient LinkedHashMap.Entry<K,V> tail;
/**
* 访问顺序
* 1）true，按照访问顺序遍历，每次访问节点都会将该节点移动到双向链表的尾部，最后遍历
* 2）false，按照插入顺序遍历
*/
final boolean accessOrder;
/**
* 创建一个容量为 16、加载因子为 0.75、
* 按照插入顺序进行元素遍历的 LinkedHashMap 实例
*/
public LinkedHashMap() {
super();
accessOrder = false;
}
/**
* 创建一个容量为 initialCapacity、加载因子为 0.75、
* 按照插入顺序进行元素遍历的 LinkedHashMap 实例
*/
public LinkedHashMap(int initialCapacity) {
super(initialCapacity);
accessOrder = false;
}
/**
* 创建一个容量为 initialCapacity、加载因子为 loadFactor、
* 按照插入顺序进行元素遍历的 LinkedHashMap 实例
*/
public LinkedHashMap(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor);
accessOrder = false;
}
/**
* 创建一个容量为 initialCapacity、加载因子为 loadFactor、
* 按照指定顺序进行元素遍历的 LinkedHashMap 实例
*/
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
@Override
public V get(Object key) {
Node<K,V> e;
// 指定的键不存在，则返回 null
if ((e = getNode(HashMap.hash(key), key)) == null) {
return null;
}
// 如果是按照访问顺序进行遍历
if (accessOrder) {
afterNodeAccess(e);
}
return e.value;
}
@Override
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
// 按照访问顺序遍历，并且当前节点不是双向链表尾节点
if (accessOrder && (last = tail) != e) {
/**
* 读取目标节点的前置节点和后置节点
* b 表示 before，目标节点的前置节点
* a 表示 after，目标节点的后置节点
*/
final LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
// 后置节点置为 null，因为目标节点将作为新的尾节点
p.after = null;
/**
* 1）p -> tail
* 2）head -> p ->tail
*/
// 1）前置节点为 null，
if (b == null) {
// 头节点更新为目标节点的后置节点
head = a;
// 2）前置节点不为 null
} else {
// 前置节点的后置节点更新为目标节点的后置节点
b.after = a;
}
// 2）后置节点不为 null
if (a != null) {
// 更新后置节点的前置节点为目标节点的前置节点
a.before = b;
/**
* tail 节点不是目标节点，那么目标节点应该在 tail 节点之前，
* 那么它必然存在后置节点，理论上不会进入该分支
*/
} else {
last = b;
}
/**
* tail 节点不是目标节点，那么目标节点应该在 tail 节点之前，
* 那么它必然存在后置节点，理论上不会进入该分支
*/
if (last == null) {
head = p;
} else {
// 目标节点的前置节点设置为旧的 tail
p.before = last;
// 旧 tail 的后置节点设置为 目标节点
last.after = p;
}
// 目标节点设置为新的 tail
tail = p;
++modCount;
}
}
/**
* 如果键不存在，则返回默认值
*/
@Override
public V getOrDefault(Object key, V defaultValue) {
Node<K,V> e;
if ((e = getNode(HashMap.hash(key), key)) == null) {
return defaultValue;
}
if (accessOrder) {
afterNodeAccess(e);
}
return e.value;
}
- 插入值时维护链表并回调 LinkedHashMap 的 afterNodeInsertion 方法
@Override
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
final LinkedHashMap.Entry<K,V> p =
new LinkedHashMap.Entry<>(hash, key, value, e);
linkNodeLast(p);
return p;
}
@Override
TreeNode<K,V> newTreeNode(int hash, K key, V value, Node<K,V> next) {
final TreeNode<K,V> p = new TreeNode<>(hash, key, value, next);
linkNodeLast(p);
return p;
}
// 创建新节点之后，LinkedHashMap 默认会将其链接到双向链表的尾部
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
// 读取尾节点
final LinkedHashMap.Entry<K,V> last = tail;
// 更新尾节点为新增节点
tail = p;
// 1）LinkedHashMap 原来为空
if (last == null) {
// 则设置头节点为新增节点
head = p;
} else {
// 新增节点的前置节点设置为旧尾节点
p.before = last;
// 旧尾节点的后置节点设置为新增节点
last.after = p;
}
}
@Override
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
/**
* 1）HashMap 回调时 evict=true
* 2）如果头结点不为 null，即 LinkedHashMap 不为空
* 3）如果 removeEldestEntry 返回 true，则移除头节点
*/
if (evict && (first = head) != null && removeEldestEntry(first)) {
final K key = first.key;
removeNode(HashMap.hash(key), key, null, false, true);
}
}
- 基于 LinkedHashMap 构建简单的 LRU 缓存
class SimpleLruCache<K,V> extends LinkedHashMap<K, V>{
private static final long serialVersionUID = -1966639797375758411L;
/**
* 默认的初始容量
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 默认的加载因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 最大元素总个数
*/
private final int maxCount;
public SimpleLruCache(int maxCount) {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR, maxCount);
}
public SimpleLruCache(int initialCapacity, float loadFactor, int maxCount) {
// 1）按照访问顺序遍历
super(initialCapacity, loadFactor,true);
this.maxCount = maxCount;
}
public SimpleLruCache(int initialCapacity, int maxCount) {
this(initialCapacity,DEFAULT_LOAD_FACTOR , maxCount);
}
/**
* 指定条件下返回 true
*/
@Override
protected boolean removeEldestEntry(java.util.Map.Entry<K, V> head) {
return maxCount < size();
}
}
@Test
public void lruCache() {
final SimpleLruCache<Integer,String> cache = new SimpleLruCache<>(2);
cache.put(1, "a");
cache.put(2, "b");
cache.put(3, "c");
Assert.assertEquals(2, cache.size());
cache.get(2);
cache.put(4, "d");
Assert.assertNull(cache.get(3));
Assert.assertNotNull(cache.get(2));
}