LinkedHashMap原理详解—从LRU缓存机制说起

写在前面

从一道Leetcode标题说起
起首，来看一下Leetcode里面的一道经典标题：146.LRU缓存机制，标题形貌如下：

请你计划并实现一个满足 LRU (最近最少使用) 缓存 束缚的数据结构。
实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
  
• int get(int key) 假如关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
  
• void put(int key, int value) 假如关键字 key 已经存在，则变动其数据值 value ；假如不存在，则向缓存中插入该组 key-value 。假如插入操作导致关键字数量凌驾 capacity ，则应该 逐出 最久未使用的关键字。
  

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

LRU 的全称是 Least Recently Used，也就是说我们认为最近使用过的数据应该是是「有用的」，好久都没用过的数据应该是无用的，内存满了就优先删那些好久没用过的数据。
分析

要让 LRU 的 put 和 get 方法的时间复杂度为 O(1)，可以总结出 LRU 这个数据结构必要的条件：

• 显然  LRU  中的元素必须有时序，以区分最近使用的和久未使用的数据，当容量满了之后要删除最久未使用的那个元素腾位置。
  
• 要在  LRU 中快速找某个 key 是否已存在并得到对应的 val；
  
• 每次访问  LRU  中的某个 key，必要将这个元素变为最近使用的，也就是说  LRU  要支持在恣意位置快速插入和删除元素。
  

那么，什么数据结构同时符合上述条件呢？哈希表查找快，但是数据无固定顺序；链表有顺序之分，插入删除快，但是查找慢。所以结合一下，形成一种新的数据结构：哈希链表 LinkedHashMap。
LRU 缓存算法的核心数据结构就是哈希链表，双向链表和哈希表的结合体。这个数据结构长这样：

借助这个结构，逐一分析上面的 3 个条件：

• 假如我们每次默认从链表尾部添加元素，那么显然越靠尾部的元素就是最近使用的，越靠头部的元素就是最久未使用的。
  
• 对于某一个 key，我们可以通过哈希表快速定位到链表中的节点，从而取得对应 val。
  
• 链表显然是支持在恣意位置快速插入和删除的，改改指针就行。只不过传统的链表无法按照索引快速访问某一个位置的元素，而这里借助哈希表，可以通过 key 快速映射到恣意一个链表节点，然后举行插入和删除。
  

put方法流程图：

代码实现

1. class LRUCache {
2.     int cap;
3.     LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();
4.     public LRUCache(int capacity) {
5.         this.cap = capacity;
6.     }
7.    
8.     public int get(int key) {
9.         if (!cache.containsKey(key)) {
10.             return -1;
11.         }
12.         // 将 key 变为最近使用
13.         makeRecently(key);
14.         return cache.get(key);
15.     }
16.    
17.     public void put(int key, int val) {
18.         if (cache.containsKey(key)) {
19.             // 修改 key 的值
20.             cache.put(key, val);
21.             // 将 key 变为最近使用
22.             makeRecently(key);
23.             return;
24.         }
25.         
26.         if (cache.size() >= this.cap) {
27.             // 链表头部就是最久未使用的 key
28.             int oldestKey = cache.keySet().iterator().next();
29.             cache.remove(oldestKey);
30.         }
31.         // 将新的 key 添加链表尾部
32.         cache.put(key, val);
33.     }
34.    
35.     private void makeRecently(int key) {
36.         int val = cache.get(key);
37.         // 删除 key，重新插入到队尾
38.         cache.remove(key);
39.         cache.put(key, val);
40.     }
41. }

复制代码

LinkedHashMap介绍

LinkedHashSet和LinkedHashMap实在也是一回事。LinkedHashSet和LinkedHashMap在Java里也有着雷同的实现，前者仅仅是对后者做了一层包装，也就是说LinkedHashSet里面有一个LinkedHashMap(适配器模式)。
LinkedHashMap实现了Map接口，即允许放入key为null的元素，也允许插入value为null的元素。从名字上可以看出该容器是linked list和HashMap的混合体，也就是说它同时满足HashMap和linked list的某些特性。可将LinkedHashMap看作采用linked list增强的HashMap。

事实上LinkedHashMap是HashMap的直接子类，二者唯一的区别是LinkedHashMap在HashMap的基础上，采用双向链表(doubly-linked list)的情势将全部entry连接起来，这样的好处：

• 可以保证元素的迭代顺序跟插入顺序雷同。跟HashMap相比，多了header指向双向链表的头部(是一个哑元)，该双向链表的迭代顺序就是entry的插入顺序。
  
• 迭代LinkedHashMap时不必要像HashMap那样遍历整个table，而只必要直接遍历header指向的双向链表即可，也就是说LinkedHashMap的迭代时间就只跟entry的个数相关，而跟table的大小无关。
  

有两个参数可以影响LinkedHashMap的性能：初始容量(inital capacity)和负载系数(load factor)。初始容量指定了初始table的大小，负载系数用来指定自动扩容的临界值。当entry的数量凌驾capacity*load_factor时，容器将自动扩容并重新哈希。对于插入元素较多的场景，将初始容量设大可以淘汰重新哈希的次数。这点与HashMap是一样的
方法分析

get()

get(Object key)方法根据指定的key值返回对应的value。该方法跟HashMap.get()方法的流程几乎完全一样
put()

put(K key, V value)方法是将指定的key, value对添加到map里。该方法起首会对map做一次查找，看是否包含该元组，假如已经包含则直接返回，查找过程类似于get()方法；假如没有找到，则会通过addEntry(int hash, K key, V value, int bucketIndex)方法插入新的entry。
注意，这里的插入有两重含义:

• 从table的角度看，新的entry必要插入到对应的bucket里，当有哈希冲突时，采用头插法将新的entry插入到冲突链表的头部。
  
• 从header的角度看，新的entry必要插入到双向链表的尾部。
  

addEntry()代码如下:

1. // LinkedHashMap.addEntry()
2. void addEntry(int hash, K key, V value, int bucketIndex) {
3.     if ((size >= threshold) && (null != table[bucketIndex])) {
4.         resize(2 * table.length);// 自动扩容，并重新哈希
5.         hash = (null != key) ? hash(key) : 0;
6.         bucketIndex = hash & (table.length-1);// hash%table.length
7.     }
8.     // 1.在冲突链表头部插入新的entry
9.     HashMap.Entry<K,V> old = table[bucketIndex];
10.     Entry<K,V> e = new Entry<>(hash, key, value, old);
11.     table[bucketIndex] = e;
12.     // 2.在双向链表的尾部插入新的entry
13.     e.addBefore(header);
14.     size++;
15. }

复制代码

上述代码中用到了addBefore()方法将新entry e插入到双向链表头引用header的前面，这样e就成为双向链表中的最后一个元素。addBefore()的代码如下:

1. // LinkedHashMap.Entry.addBefor()，将this插入到existingEntry的前面
2. private void addBefore(Entry<K,V> existingEntry) {
3.     after  = existingEntry;
4.     before = existingEntry.before;
5.     before.after = this;
6.     after.before = this;
7. }

复制代码

remove()

remove(Object key)的作用是删除key值对应的entry，该方法的具体逻辑是在removeEntryForKey(Object key)里实现的。removeEntryForKey()方法会起首找到key值对应的entry，然后删除该entry(修改链表的相应引用)。查找过程跟get()方法类似。
注意，这里的删除也有两重含义:

• 从table的角度看，必要将该entry从对应的bucket里删除，假如对应的冲突链表不空，必要修改冲突链表的相应引用。
  
• 从header的角度来看，必要将该entry从双向链表中删除，同时修改链表中前面以及后面元素的相应引用。
  

removeEntryForKey()对应的代码如下:

1. // LinkedHashMap.removeEntryForKey()，删除key值对应的entry
2. final Entry<K,V> removeEntryForKey(Object key) {
3.     ......
4.     int hash = (key == null) ? 0 : hash(key);
5.     int i = indexFor(hash, table.length);// hash&(table.length-1)
6.     Entry<K,V> prev = table[i];// 得到冲突链表
7.     Entry<K,V> e = prev;
8.     while (e != null) {// 遍历冲突链表
9.         Entry<K,V> next = e.next;
10.         Object k;
11.         if (e.hash == hash &&
12.             ((k = e.key) == key || (key != null && key.equals(k)))) {// 找到要删除的entry
13.             modCount++; size--;
14.             // 1. 将e从对应bucket的冲突链表中删除
15.             if (prev == e) table[i] = next;
16.             else prev.next = next;
17.             // 2. 将e从双向链表中删除
18.             e.before.after = e.after;
19.             e.after.before = e.before;
20.             return e;
21.         }
22.         prev = e; e = next;
23.     }
24.     return e;
25. }

复制代码

LinkedHashSet

LinkedHashSet是对LinkedHashMap的简单包装，对LinkedHashSet的函数调用都会转换成符合的LinkedHashMap方法，因此LinkedHashSet的实现非常简单

1. public class LinkedHashSet<E>
2.     extends HashSet<E>
3.     implements Set<E>, Cloneable, java.io.Serializable {
4.     ......
5.     // LinkedHashSet里面有一个LinkedHashMap
6.     public LinkedHashSet(int initialCapacity, float loadFactor) {
7.         map = new LinkedHashMap<>(initialCapacity, loadFactor);
8.     }
9.     ......
10.     public boolean add(E e) {//简单的方法转换
11.         return map.put(e, PRESENT)==null;
12.     }
13.     ......
14. }

复制代码

关于作者

来自一线程序员Seven的探索与实践，持续学习迭代中~
本文已收录于我的个人博客：https://www.seven97.top
公众号：seven97，接待关注~

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。