1 LRU
LRU是Least Recently Used的缩写，即最近最少使用，是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰。
2 LinkedHashMap
LinkedHashMap = HashMap + 双向链表
LinkedHashMap的数据结构：
具有相同key的情况下：
3 实现LRU
/** * @desc: 手写 LRU Cache-近期最少使用算法 * @author: YanMingXin * @create: 2021/8/11-10:27 **/ public class LRUCache<K, V> { private final int MAX_CACHE_SIZE; private final float DEFAULT_LOAD_FACTOR = 0.75f; private LinkedHashMap<K, V> map; public LRUCache(int cacheSize) { MAX_CACHE_SIZE = cacheSize; //根据cacheSize和加载因子计算hashmap的capacity //+1确保当达到cacheSize上限时不会触发hashmap的扩容 int capacity = (int) Math.ceil(MAX_CACHE_SIZE / DEFAULT_LOAD_FACTOR) + 1; map = new LinkedHashMap(capacity, DEFAULT_LOAD_FACTOR, true) { @Override protected boolean removeEldestEntry(Map.Entry eldest) { return size() > MAX_CACHE_SIZE; } }; } public synchronized void put(K key, V value) { map.put(key, value); } public synchronized V get(K key) { return map.get(key); } public synchronized void remove(K key) { map.remove(key); } @Override public String toString() { StringBuilder sb = new StringBuilder(); for (Map.Entry entry : map.entrySet()) { sb.append(String.format("%s:%s ", entry.getKey(), entry.getValue())); } return sb.toString(); } } class TestLRUCache { public static void main(String[] args) { LRUCache<String, Object> cache = new LRUCache<>(3); cache.put("1", "A"); cache.put("2", "B"); cache.put("3", "C"); cache.put("4", "D"); cache.put("5", "E"); System.out.println(cache.toString()); } }
测试结果：
4 探究源码
首先看下LinkedHashMap是如何put元素的：
由此可见LinkedHashMap并没有将父类HashMap的put方法重写或重载，而是直接使用HashMap的put()方法，
但是在HashMap的putVal方法中看见了这样一段
接下来看下afterNodeInsertion方法
可见这三个方法都是为LinkedHashMap准备的，并且在LinkedHashMap中都进行了重写
我们看下这三个方法在LinkedHashMap的重写
/** 这个方法是当HashMap删除一个键值对时调用的，它会把在HashMap中删除的那个键值对一并从链表中删除，保证了哈希表和链表的一致性。 */ void afterNodeRemoval(Node<K,V> e) { // unlink LinkedHashMap.Entry<K,V> p = (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after; p.before = p.after = null; if (b == null) head = a; else b.after = a; if (a == null) tail = b; else a.before = b; } /** afterNodeInsertion方法是在哈希表中插入了一个新节点时调用的，它会把链表的头节点删除掉，删除的方式是通过调用HashMap的removeNode方法。想一想，通过afterNodeInsertion方法和afterNodeAccess方法，是不是就可以简单的实现一个基于最近最少使用（LRU）的淘汰策略了？当然，我们还要重写removeEldestEntry方法，因为它默认返回的是false。 */ void afterNodeInsertion(boolean evict) { // possibly remove eldest LinkedHashMap.Entry<K,V> first; if (evict && (first = head) != null && removeEldestEntry(first)) { K key = first.key; //删除头结点 removeNode(hash(key), key, null, false, true); } } /** 这段代码的意思简洁明了，就是把当前节点e移至链表的尾部。因为使用的是双向链表，所以在尾部插入可以以O（1）的时间复杂度来完成。并且只有当accessOrder设置为true时，才会执行这个操作。在HashMap的putVal方法中，就调用了这个方法。 */ 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; } }
