LinkedHashMap继承HashMap，保证迭代的顺序, 怎么存入的会怎么取出来。
实现原理：
LinkedHashMap维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序通常就是将键插入到映射中的顺序（插入顺序）。 
LinkedHashMap中，覆盖了Entry内部类，在原来的Entry的实现上，增加了before和after，这就是双联链表的前引用和后引用，并增加了addBefore和remove等重要方法.
private static class Entry<K,V> extends HashMap.Entry<K,V> {// These fields comprise the doubly linked list used for iteration.Entry<K,V> before, after;Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {super(hash, key, value, next);}/*** Removes this entry from the linked list.*/private void remove() {before.after = after;after.before = before;}/*** Inserts this entry before the specified existing entry in the list.*/private void addBefore(Entry<K,V> existingEntry) {after = existingEntry;before = existingEntry.before;before.after = this;after.before = this;}}
在HashMap中，存储实现的流程是这样的： put() -> addEntry() -> createEntry()。put()中计算当前key的hash值所在的哈希表的索引位置，并在createEntry()中完成key-value节点在该索引位置的插入。
而在LinkedHashMap中，覆盖了addEntry() 和 createEntry()方法的实现，而没有覆盖put方法，因此这就证明了LinkedHashMap的存储规则是和HashMap一样的
我们来看看addEntry() 和 createEntry()方法
void addEntry(int hash, K key, V value, int bucketIndex) {// 调用父类的addEntry，增加一个Entry到HashMap中super.addEntry(hash, key, value, bucketIndex);//HashMap的addEntry()方法调用了createEntry()方法// removeEldestEntry方法默认返回false，不用考虑Entry<K,V> eldest = header.after;if (removeEldestEntry(eldest)) {removeEntryForKey(eldest.key);}}void createEntry(int hash, K key, V value, int bucketIndex) {HashMap.Entry<K,V> old = table[bucketIndex];// e就是新创建了Entry，会加入到table[bucketIndex]的表头Entry<K,V> e = new Entry<>(hash, key, value, old);table[bucketIndex] = e;// 把新创建的Entry，加入到双向链表中e.addBefore(header);size++;}
LinkedHashMap没有提供remove方法，所以调用的是HashMap的remove方法。HashMap的remove方法调用了removeEntryForKey(Object key), 这个方法中调用了 :
void recordRemoval(HashMap<K,V> m)
在HashMap.Entry中recordRemoval方法是空实现，但是LinkedHashMap.Entry对其进行了重写，如下：
void recordRemoval(HashMap<K,V> m) {
remove();
}
private void remove() {
before.after = after;
after.before = before;
}
所以，LinkedHashMap的remove操作。首先把它从table中删除，即断开table或者其他对象通过next对其引用，然后也要把它从双向链表中删除，断开其他对应通过after和before对其引用。
LRUCache与LinkedHashMap
https://leetcode-cn.com/problems/lru-cache/solution/lru-ce-lue-xiang-jie-he-shi-xian-by-labuladong/
A. LinkedHashMap基于LRU的设计：recordAccess重排
LinkedHashMap提供了多个构造方法，我们先看空参的构造方法。
public LinkedHashMap() {
// 调用HashMap的构造方法，其实就是初始化Entry[] table
super();
// 这里是指是否基于访问排序，默认为false
accessOrder = false;
}
/* 在HashMap的构造函数中，调用了init方法，而在HashMap中init方法是空实现，
* 但LinkedHashMap重写了该方法，所以在LinkedHashMap的构造方法里，调用了自身的init方法.
* init的重写实现如下：*/
@Override
void init() {
// 创建了一个hash=-1，key、value、next都为null的Entry
header = new Entry<>(-1, null, null, null);
// 让创建的Entry的before和after都指向自身，注意after不是之前提到的next
// 其实就是创建了一个只有头部节点的双向链表
header.before = header.after = header;
}
LinkedHashMap存储数据是有序的，而且分为两种：插入顺序和访问顺序。这里accessOrder设置为false，表示不是访问顺序而是插入顺序存储的，这也是默认值，表示LinkedHashMap中存储的顺序是按照调用put方法插入的顺序进行排序的。LinkedHashMap也提供了可以设置accessOrder的构造方法:
Map<String, String> linkedHashMap = new LinkedHashMap<>(16, 0.75f, true);
设置accessOrder为true即开启了LRU模式。
在HashMap的put方法中，调用了e.recordAccess(this)。这个方法跟访问顺序有关，而HashMap是无序的，所以在HashMap.Entry的recordAccess方法是空实现，但是LinkedHashMap是有序的,LinkedHashMap.Entry对recordAccess方法进行了重写。在LinkedHashMap中，只有accessOrder为true，即是访问顺序模式，才会put时对更新的Entry进行重新排序。
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
// 如果LinkedHashMap的accessOrder为true，则进行重排序
if (lm.accessOrder) {
lm.modCount++;
// 把更新的Entry从双向链表中移除
remove();
// 再把更新的Entry加入到双向链表的表尾
addBefore(lm.header);
}
}
LinkedHashMap有对get方法进行了重写，如下：
public V get(Object key) {
// 调用genEntry得到Entry
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
// 如果LinkedHashMap是访问顺序的，则get时，也需要重新排序
e.recordAccess(this);
return e.value;
}
B. LRU的实现：
class LRUCache extends LinkedHashMap<Integer, Integer>{
private int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75F, true);//设置LinkedHashMap中的accessOrder为true
this.capacity = capacity;
}
public int get(int key) {
return super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}
基于原理的实现：HashMap + DoubleLinkedList
public class LRUCache {
class DLinkedNode {
int key;
int value;
DLinkedNode prev;
DLinkedNode next;
}
private void addNode(DLinkedNode node) {
/**
* Always add the new node right after head.
*/
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(DLinkedNode node){
/**
* Remove an existing node from the linked list.
*/
DLinkedNode prev = node.prev;
DLinkedNode next = node.next;
prev.next = next;
next.prev = prev;
}
private void moveToHead(DLinkedNode node){
/**
* Move certain node in between to the head.
*/
removeNode(node);
addNode(node);
}
private DLinkedNode popTail() {
/**
* Pop the current tail.
*/
DLinkedNode res = tail.prev;
removeNode(res);
return res;
}
private Map<Integer, DLinkedNode> cache = new HashMap<>();
private int size;
private int capacity;
private DLinkedNode head, tail;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
head = new DLinkedNode();
// head.prev = null;
tail = new DLinkedNode();
// tail.next = null;
head.next = tail;
tail.prev = head;
}
public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) return -1;
// move the accessed node to the head;
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if(node == null) {
DLinkedNode newNode = new DLinkedNode();
newNode.key = key;
newNode.value = value;
cache.put(key, newNode);
addNode(newNode);
++size;
if(size > capacity) {
// pop the tail
DLinkedNode tail = popTail();
cache.remove(tail.key);
--size;
}
} else {
// update the value.
node.value = value;
moveToHead(node);
}
}
}
注意：不能使用LinkedList实现LRU。因为LinkedList的remove()时间复杂度是O(N)。删除前找到所需元素需要使用O(N).
若有收获，就点个赞吧
0 人点赞
