简介：
HashMap是无序的，也就是说，迭代HashMap所得到的元素顺序并不是它们最初放置到HashMap的顺序。HashMap的这一缺点往往会造成诸多不便，因为在有些场景中，我们确需要用到一个可以保持插入顺序的Map。庆幸的是，JDK为我们解决了这个问题，它为HashMap提供了一个子类 —— LinkedHashMap。虽然LinkedHashMap增加了时间和空间上的开销，但是它通过维护一个额外的双向链表保证了迭代顺序。特别地，该迭代顺序可以是插入顺序，也可以是访问顺序。因此，根据链表中元素的顺序可以将LinkedHashMap分为：保持插入顺序的LinkedHashMap 和 保持访问顺序的LinkedHashMap，其中LinkedHashMap的默认实现是按插入顺序排序的。
示意图
LinkedHashMap 在 JDK 中的定义
1、类结构定义
LinkedHashMap继承于HashMap,实现Map接口
public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {
...
}
2、成员变量定义
与HashMap相比，LinkedHashMap增加了两个属性用于保证迭代顺序，分别是 双向链表头结点head 和 标志位accessOrder (值为true时，表示按照访问顺序迭代；值为false时，表示按照插入顺序迭代)。
/**
* 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;
private final boolean accessOrder; //true表示按照访问顺序迭代，false时表示按照插入顺序
3、成员方法定义
LinkedHashMap中并增加没有额外方法
图不全不新，用来大概理解
4、基本元素 Entry
LinkedHashMap中的Entry增加了两个指针 before 和 after，它们分别用于维护双向链接列表。
private static class Entry<K,V> extends HashMap.Entry<K,V> {
Entry<K,V> before, after;
Entry(int hash, K key, V value, HashMap.Entry<K,V> next) {
super(hash, key, value, next);
}
...
}
5.构造一个指定初始容量和指定负载因子的具有指定迭代顺序的LinkedHashMap
public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {
super(initialCapacity, loadFactor); // 调用HashMap对应的构造函数
this.accessOrder = accessOrder; // 迭代顺序的默认值
}
6.在LinkedHashMap中，它重写了reinitialize方法以便初始化双向列表
void reinitialize() {
super.reinitialize();
head = tail = null;
}
HashMap中reinitialize方法
void reinitialize() {
table = null;
entrySet = null;
keySet = null;
values = null;
modCount = 0;
threshold = 0;
size = 0;
}
LinkedHashMap 的快速存取
LinkedHashMap完全继承了HashMap的 put(Key,Value) 方法，只是对put(Key,Value)方法所调用的afterNodeAccess方法进行了重写；对于get(Key)方法而言，LinkedHashMap则直接对它进行了重写。
HashMap afterNodeAccess方法是空
3、LinkedHashMap 的读取实现 ：get(Object key)
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
afterNodeAccess(e);// move node to last将其移动到链表最后，LRU的原理
return e.value;
}
节点信息
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
...
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
LinkedHashMap 与 LRU
使用LinkedHashMap实现LRU的必要前提是将accessOrder标志位设为true以便开启按访问顺序排序的模式。我们可以看到，无论是put方法还是get方法，都会导致目标Entry成为最近访问的Entry，因此就把该Entry加入到了双向链表的末尾：通过调用afterNodeAccess方法来实现。这样，我们便把最近使用的Entry放入到了双向链表的后面。多次操作后，双向链表前面的Entry便是最近没有使用的，这样当节点个数满的时候，删除最前面的Entry(head后面的那个Entry)即可，因为它就是最近最少使用的Entry。
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<K,V>)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;
}
}
使用LinkedHashMap实现LRU算法
其实就是重写LinkedHashMap中的removeEldestEntry方法，当LRU中元素多余N个时，删除最旧的元素。
本来的removeEldestEntry方法一直返回false 代表不删除
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return false;
}
重写实现
import java.util.LinkedHashMap;
import java.util.Map;
public class LRU<K,V> extends LinkedHashMap<K,V> implements Map<K,V>{
//不知道为什么 我ctrl+O 弹不出来这个方法 只好手动复制一遍
@Override
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
if(size()>3)
return true;
return false;
}
public LRU(int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor, accessOrder);
}
public static void main(String[] args) {
LRU<Character,Integer> lru = new LRU<>(16,0.75f,true);
String s = "sqwefertgh";
for (int i=0;i<s.length();i++){
lru.put(s.charAt(i),i);
}
System.out.println("LRU中key为g的Entry的值为："+lru.get('g'));
System.out.println("LRU的大小： "+lru.size());
System.out.println("LRU里面的数据： "+lru);
/*LRU中key为g的Entry的值为：8
LRU的大小： 3
LRU里面的数据： {t=7, h=9, g=8}
*/
}
}
网友评论