java实现LRU 缓存
如果碰到这种题⽬先不要慌张，现在脑海⾥回忆⼀遍 LRU 的基本概念：LRU（Least Recently Used，最近最少使⽤）是⼀种缓存算法，其核⼼思想是将最近最少使⽤的缓存项移除，以便为更常 ⽤的缓存项腾出空间。
适⽤场景：
- 频繁访问：LRU 算法适⽤于那些有频繁访问的数据，⽐如缓存、⻚⾯置换等场景。
- 有局部性：当访问模式具有局部性，即近期访问的数据更可能在未来被再次访问时，LRU 算法 能够有较好的表现。
- 数据访问分布均匀：如果数据的访问分布较为均匀，没有出现热点数据或周期性访问模式， LRU 算法的命中率较⾼。
- 缓存容ᰁ适中：LRU 算法适⽤于缓存容ᰁ适中的场景，过⼤的缓存可能导致淘汰开销增⼤，⽽过⼩的缓存则可能导致频繁缓存失效。
在 Java 中，可以使⽤ LinkedHashMap 来实现 LRU 缓存。使⽤LinkedHashMap实现 LRU 缓存可 以极⼤地简化代码，因为LinkedHashMap已经内置了按照访问顺序排序的功能。所以使⽤LinkedHashMap 确实可以避免⼿动实现双向链表和节点的逻辑。
为了使⽤ LinkedHashMap 来实现 LRU 缓存，在创建 LinkedHashMap 对象时设置它的访问顺序为 true，这样元素将按照访问顺序进⾏排序。然后，我们可以重写它的 removeEldestEntry ⽅法来控制 是否移除最⽼的数据。
import java.util.LinkedHashMap;
import java.util.Map;
public class LRUCache<K,V> extends LinkedHashMap<K, V> {private int capacity;public LRUCache(int capacity){super(capacity,0.75f, true);this.capacity = capacity;}public void setValue(K key, V value){super.put(key, value);}public V getValue(K key){return super.getOrDefault(key,null);}@Overrideprotected boolean removeEldestEntry(Map.Entry<K, V> eldest) {return size() > capacity;}public static void main(String[] args) {LRUCache<Integer, String> lruCache = new LRUCache<>(4);lruCache.setValue(1, "a");lruCache.setValue(2, "b");lruCache.setValue(3, "c");lruCache.setValue(4, "d");System.out.println(lruCache.getValue(1));lruCache.put(5, "e");System.out.println(lruCache.getValue(2));}
}
加深巩固:
leecode: 146. LRU 缓存 - 力扣（LeetCode）
题解:
class LRUCache extends LinkedHashMap<Integer,Integer>{private int capacity;public LRUCache(int capacity) {super(capacity,0.75f,true); // 开启accessOrder属性,访问元素后将访问的元素放到链表末端this.capacity = capacity;}public int get(int key) {return super.getOrDefault(key, -1); // 如果存在,将会放到链表末端表示它是最近使用的。}public void put(int key, int value) {super.put(key,value);}// 判断size超过容量时返回true，告知LinkedHashMap移除最老的缓存项(即链表的第一个元素)@Overridepublic boolean removeEldestEntry(Map.Entry<Integer,Integer> eldest) {return size() > capacity; }
}/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj = new LRUCache(capacity);* int param_1 = obj.get(key);* obj.put(key,value);*/