一、LinkedHashMap
HashMap 是无序的，
TreeMap 可以按照 key 进行排序，那有木有 Map 是可以维护插入顺序的呢？那就是 LinkedHashMap。
LinkedHashMap 本身是继承 HashMap 的，并自己维持了一个双向链表，所以它拥有 HashMap 的所有特性，在此基础上还提供了两大特性：
- 1、按照插入顺序进行访问
默认情况下get取值取的是插入顺序（put的newNode中插入节点采用链表的尾插法）。
可通过构造打开开关，这时get取的就是访问后的顺序（打开开关后，每次访问元素，afterNodeAccess会将元素放链表尾部）
- 2、实现了LRU算法
可通过重写removeEldestEntry实现,从链表首部开始删除满足数量的元素。当put/get时afterNodeInsertion内部就会调用removeEldestEntry来删除链表头部元素。removeEldestEntry的返回值就是控制是否删除元素。
2021060421094928.png
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>
{
// 链表头
transient LinkedHashMap.Entry<K,V> head;
// 链表尾
transient LinkedHashMap.Entry<K,V> tail;
// 链表节点，这个节点继承了HashMap的链表节点，并在HashMap原有的节点功能上扩展了
//了功能，即为每个节点添加头尾指针。
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,ket,value,next);
}
}
// 控制两种访问模式的字段，默认是 false
// true 按照访问顺序，会把经常访问的 key 放到链表尾部
// false 按照插入顺序提供访问
final boolean accessOrder;
}
看源码会发现，我们用 LinkedHashMap 的 get/put 方法，其实都是调用到 HashMap 的 get/put 方法，那么 LinkedHashMap 是如何实现自己独特的特性呢？
其实答案在 HashMap 的三个空方法：
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
这三个方法是在 HashMap get/put/remove 时会调用的方法，LinkedHashMap 重写了这些方法，然后会在这些方法里面进行排序。
所以，LinkedHashMap 实现的重点有两个：
- 扩展 HashMap.Entry 使其拥有链表结构
- 重写 HashMap 里面三个方法
二、面试必问
1、LinkedHashMap是个什么东西？
LinkedHashMap继承于HashMap，因此LinkedHashMap底层也是基于链表，如果JDK1.8以上就是链表+红黑树。与HashMap的不同之处在于LinkedHashMap多维护了一个具有键值对的双向链表，而这个双向链表就定义了迭代顺序，和访问顺序。
2、在使用上有啥特点
1、最大的特点就是提供了LRU算法的功能，通过重写removeEldestEntry就可实现。
2、LinkedHashMap的容量是可控的。
3、LinkedHashMap是有插入顺序的。
（1）默认情况下
public class LinkedHashMapActivity extends AppCompatActivity {
LinkedHashMap<Integer, Integer> linkedHashMap;
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_linked_hash_map);
linkedHashMap = new LinkedHashMap<Integer, Integer>(2);
linkedHashMap.put(1, 1);
linkedHashMap.put(2, 2);
linkedHashMap.put(3, 3);
for (Map.Entry<Integer, Integer> a : linkedHashMap.entrySet()) {
Log.e("TAG", "key->" + a.getKey() + "");
Log.e("TAG", "value->" + a.getValue() + "");
}
}
}
-------------------------
log：
TAG: key->1
TAG: value->1
TAG: key->2
TAG: value->2
TAG: key->3
TAG: value->3
这里初始化时我们设置的初始容量是2，但是put了三个数据，实际打印的结果也是3条数据，因此初始化的2并不代表LinkedHashMap的最大容量。
（2）重写情况下
public class LinkedHashMapActivity extends AppCompatActivity {
LinkedHashMap<Integer, Integer> linkedHashMap;
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
setContentView(R.layout.activity_linked_hash_map);
linkedHashMap = new LinkedHashMap<Integer, Integer>(2) {
@Override
protected boolean removeEldestEntry(Entry eldest) {
return linkedHashMap.size() > 2;
}
};
linkedHashMap.put(1, 1);
linkedHashMap.put(2, 2);
linkedHashMap.put(3, 3);
for (Map.Entry<Integer, Integer> a : linkedHashMap.entrySet()) {
Log.e("TAG", "key->" + a.getKey() + "");
Log.e("TAG", "value->" + a.getValue() + "");
}
}
}
-----------------------------
log：
TAG: key->2
TAG: value->2
TAG: key->3
TAG: value->3
和第一个例子相比，在LinkedHashMap实例化的过程中，重写了removeEldestEntry()方法，并根据当前linkedHashMap.size()和设置容量的判断结果返回数据，明明put了3条数据，打印却只打印了最后put的2条，这一结果证实了2点。（还是最先添加的被移除了）
3、LinkedHashMap访问有序是怎么体现的呢？是直接调用get()方法就会自动排序么？
linkedHashMap = new LinkedHashMap<Integer, Integer>(2,0.75f,true)
1、get时排序功能默认关闭的，默认为插入顺序。
2、通过构造的第三个参数(accessOrder)可以开启
4、LinkedHashMap的双向链表对象都包含什么属性？
//1、LinkedHashMap的Entry链表。继承于 HashMap.Node，获得普通链表的能力。
//2、内部属性 before, after;维护双向链表
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);
}
}
//3、HashMap#Node链表（这段代码是HashMap中的）
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key; //元素的key
V value; //值value
Node<K,V> next; //下一个节点
...省略若干代码
}
// 4、HashMap#TreeNode 红黑树节点（这段代码是HashMap中的 这里主要了解下继承关系）
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
TreeNode(int hash, K key, V val, Node<K,V> next) {
super(hash, key, val, next);
}
....
}
20210604213656800.png
1、LinkedHashMap.Entry就是LinkedHashMap中的每一个键值对对象，其中通过before, after两个属性维护了当前键值对的一前一后两个对象
观看继承关系图可以发现HashMap#TreeNode继承了LinkedHashMap#Entry。LinkedHashMap#Entry又继承了了HashMap的Node。饶了一圈为啥HashMap#TreeNode不直接继承自己的Node节点？
分析发现LinkedHashMap.Entry有组成双向链表的能力，继承了它（就继承了头尾节点属性）就获得了这个能力，但是TreeNode 就多了两个用不到的引用 (LinkedHashMapEntry<K,V> before, after;)；同时内存占用也会比较大，这么做是为啥？
答：官方是这样解释的，HashMap#TreeNode内存占用是HashMap#Node内存占用的2倍左右，但是TreeNode是在HashMap数组中的Node节点足够多的时候才会被使用。（jdk1.8中当一个桶中的元素超过8就会转化为红黑树，小于6又会恢复为链表）如果hash算法不是很差的话TreeNode使用的几率是比较低的，因此浪费那一点空间换取了组成双向链表的能力是值得的。如果直接继承Node节点，由于Node 节点使用频繁，这样空间浪费的就太多了。
5、LinkedHashMap对象是怎么维护每一个双向链表对象的?
// LinkedHashMap 的节点,节点内部使用before、after 保存前后节点指针。
//具体的维护过程在LinkedHashMap.put方法
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);
}
}
发现LinkedHashMap 未重写put方法，，，，那么直接看HashMap的put即可。
//HashMap的put()方法，同时也是LinkedHashMap的put方法
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//直接看关键部分的代码，看我注释的部分
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
//1、调用了newNode()方法，这里用到了一个面向对象里多态的特性，
//而LinkedHashMap重写了newNode()方法
//如果是LindedHashMap对象调用，触发的是LinkedHashMap重写的newNode()
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//有重复的key，则用待插入值进行覆盖，返回旧值。
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//2、HashMap中该方法没做任何操作，LinkedHashMap进行了重写实现，并调用。
//该方法主要将当前节点移动到双向链表尾部.
afterNodeAccess(e);
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
//3、每次put新元素都会调用（如果是更新已有元素则不调用，因为没有新增元素，不会导致size+1）
//但是HashMap中该方法没做任何操作, LinkedHashMap进行了重写实现.
//主要用于移除最早的元素，后续详细解析
afterNodeInsertion(evict);
return null;
}
//HashMap内的newNode
Node<K,V> newNode(int hash, K key, V value, Node<K,V> next) {
return new Node<>(hash, key, value, next);
}
//LinkedHashMap重写的newNode
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
//构造带双向链表属性的对象。
LinkedHashMapEntry<K,V> p =
new LinkedHashMapEntry<K,V>(hash, key, value, e);
//双向链表维护
linkNodeLast(p);
return p;
}
private void linkNodeLast(LinkedHashMapEntry<K,V> p) {
//首先获取当前链表的最后一个元素
LinkedHashMapEntry<K,V> last = tail;
//当前插入的元素定义为最后一个元素
tail = p;
if (last == null)
//如果之前的最后元素是null，说明之前的链表就是空的，
//所以当前的元素是一个元素。
head = p;
else {
//如果之前的链表不是null
//put前的最后一个元素设置为当前put元素的前一个。
p.before = last;
//当前put元素设置为put前最后一个元素的下一个
last.after = p;
}
}
总结：
1、先创建新的元素，通过hash计算位置并存放。（与HashMap一致）
2、每次newNode创建元素时都会在newNode中调用linkNodeLast()将新元素插入LinkedHashMap的双向链尾部。
3、每次put新元素均通过LinkedHashMap中重写的afterNodeInsertion()判断是否删除头节点元素。
（1）HashMap#afterNodeInsertion
这个方法在HashMap中是空实现，LinkedHashMap重写了此方法，并默认关闭此方法功能。
//1、这个方法是在HashMap的代码里调用的，在put方法中调用的时候参数evict传的是true
void afterNodeInsertion(boolean evict) {
LinkedHashMapEntry<K,V> first;
//2、evict是true，(first = head)=true,而removeEldestEntry()方法默认返回的是false，因此if内的逻辑默认是不执行的。
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
//3、移除链表头部的元素
removeNode(hash(key), key, null, false, true);
}
}
//4、HashMap中的removeNode方法，主要用于删除某一个元素
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index;
...省略若干代码
}
通过以上代码发现，其实每次调用afterNodeInsertion()方法，只是内部的if判断中removeEldestEntry()默认返回false ，因此移除链表头部元素的逻辑没能执行，但是可通过重写removeEldestEntry()方法手动返回true，这样可以做到每添加一个元素都移除头部的元素。
(2)LinkedHashMap#afterNodeAccess
1、如果put的key已存在则用新值覆盖并调用LinkedHashMap重写的afterNodeAccess()将新值移动到链表尾部。
2、在afterNodeAccess()函数中，会修改modCount变量,迭代LinkedHashMap时，如果同时查询访问数据，也会导致fail-fast，因为迭代的顺序已经改变。
6、LinkedHashMap为什么调用get()就会触发排序？
//HashMap#get方法
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
//LinkedHashMap重写的get方法
public V get(Object key) {
Node<K,V> e;
//getNode()调用是HashMap.getNode()
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
//哈哈哈，看到这我一下子就明白他怎么做的排序了。
afterNodeAccess(e);
return e.value;
}
LinkedHashMap每次调用get方法，在结果返回前就触发了afterNodeAccess()，而afterNodeAccess()作用就是将当前元素移动到尾节点。
7、LinkedHashMap调用remove()后链表怎么维护?
如果是我们自己实现这个逻辑需要怎么操作？比如现在调用remove()，删了了链表中间的一个元素，应该怎么维护？
- 首先我们通过当前元素前后的元素获取前后节点，然后让前后节点做关联，但是需要注意首位节点。
- 如果LinkedHashMap重写了remove()则在重写的方法里实现逻辑，如果调用的是HashMap.remove()则需要有和afterNodeAccess()类似的after…()方法进行重写实现，且after…()方法需在remove()方法中调用。
源码验证猜想：
HashMap#remove
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
...
++modCount;
--size;
//维护双向链表的afterNodeRemoval方法，在HashMap中该方法是空方法。
afterNodeRemoval(node);
return node;
}
}
return null;
}
//LinkedHashMap重写的afterNodeRemoval()方法。
// 其实就是双向链表的删除操作
void afterNodeRemoval(Node<K,V> e) {
//1、记录当前节点前后节点
LinkedHashMapEntry<K,V> p = (LinkedHashMapEntry<K,V>)e,
b = p.before,
a = p.after;
//2、删除元素的前后节点引用置空
p.before = p.after = null;
//3、具体的判断处理。
if (b == null)
//判断1：
//如果当前元素的前节点是null，则证明当前元素原来是头节点。
//因此删除当前元素后，当前元素的后节点就变成了头节点。
head = a;
else
//判断2：
//如果前节点不为null，则前节点的after引用后节点。
b.after = a;
if (a == null)
//判断3：
//如果当前元素的后节点为null，则说明当前元素为尾节点，
//删除当前元素后，尾节点变成当前元素的前节点。
tail = b;
else
//尾节点不为null，尾节点的前节点引用删除元素的前节点。
a.before = b;
}
20210606104435844.png
总结：
LinkedHashMap.remove()
----->调用HashMap.remove()
---->调用HashMap.removeNode()。
---->调用afterNodeRemoval(),
LinkedHashMap中重写了afterNodeRemoval()，因此最终的维护链表逻辑是在LinkedHashMap.afterNodeRemoval()中。
8、LinkedHashMap 相对HashMap在一些方法做了性能改善点
（1）containsValue方法对比
//LinkedHashMap.containsValue()
public boolean containsValue(Object value) {
//循环查找所有键值对的中和value重复的数据
for (LinkedHashMapEntry<K,V> e = head; e != null; e = e.after) {
V v = e.value;
if (v == value || (value != null && value.equals(v)))
return true;
}
return false;
}
//HashMap.containsValue()
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
if ((tab = table) != null && size > 0) {
//双重for循环查找数据
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}
- LinkedHashMap针对的是链表循环，循环的是所有有效的数据
- 而HashMap中，是双重for循环，先循环桶，后循环每个桶的数据，双重for循环这一点效率就偏低，其次HashMap循环的是所有的桶，但并不是所有桶都有数据。
LinkedHashMap.LinkedHashIterator.nextNode()相对HashMap.HashIterator.nextNode()大幅度提升了性能。原理同上
三、Lru算法实现
1、链表实现法
使用一个双向链表：
- （1）新数据插入到链表头部;
- （2）每当缓存命中（即缓存数据被访问），则将数据移到链表头部;
- （3）当链表满的时候，将链表尾部的数据丢弃
LinkedHashMap底部是双向链表+HashMap的数据结构。正好满足条件，因此LinkedHashMap实现了Lru算法。具体是我们需要重写removeEldestEntry 来控制是否开启。开启后每当数据命中后数据就会被移动到链表尾部，同时也会根据size大小判断是否需要删除头部的最少使用的元素。
安卓中的lruCache正是基于LinkedHashMap进行的封装。
2、数组实现法
给每一个数据项标记一个访问时间戳，每次插入新数据项的时候，先把数组中存在的数据项的时间戳自增，并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为0。当数组空间已满时，将时间戳最大的数据项淘汰
3、Lru算法缺点&改善
缺点: 如果一个不是经常使用的数据，偶尔或者周期性的被使用，那么该数据会被加到LRU链表头部,而这种不经常使用的数据，放在链表头部，占用了空间;一直等到LRU淘汰完，才会被剔除链表; 如果这种数据一次性过多，那么链表数据都是这种无用的数据，从而会导致缓存命中率低下，影响系统性能;
改善：
针对LRU算法的问题，LRU-K算法，不仅记录最近被使用时间，还需要使用一个历史记录表，记录使用次数; 使用次数很低的，直接不加入LRU链表; 提高缓存命中率;
网友评论