便宜的广州网站建设服务,网站 禁止ping,人工智能需要学哪些课程,如何知道网站是用什么语言做的含义
最近最少使用算法#xff08;LRU#xff09;是一种缓存替换算法#xff0c;用于在缓存空间有限的情况下#xff0c;选择最少使用的数据项进行替换。该算法的核心思想是基于时间局部性原理#xff0c;即刚被访问的数据在未来也很有可能被再次访问。
实现
LRU算法的…含义
最近最少使用算法LRU是一种缓存替换算法用于在缓存空间有限的情况下选择最少使用的数据项进行替换。该算法的核心思想是基于时间局部性原理即刚被访问的数据在未来也很有可能被再次访问。
实现
LRU算法的实现可以通过一个双向链表和一个哈希表来完成。双向链表用于按照访问顺序维护缓存中的数据项哈希表用于存储数据项的引用以便快速定位和访问。 如果缓存未满则直接将新的数据项插入链表头部。 如果缓存已满则将链表尾部的数据项移除并将新的数据项插入链表头部。 实现链表 新数据插入到链表头部 每当缓存命中即缓存数据被访问则将数据移到链表头部 当链表满的时候将链表尾部的数据丢弃。
特点
存在问题
当存在热点数据时LRU的效率很好但偶发性的、周期性的批量操作会导致LRU命中率急剧下降缓存污染情况比较严重。
复杂度 : 实现简单。
代价 :命中时需要遍历链表找到命中的数据块索引然后需要将数据移到头部。即LRU算法的实现需要维护一个适当的数据结构所以在实际应用中可能会有一定的开销。
代码实现LRU
注意事项 需要保证多线程下数据的一致性 方法1、使用synchronized 字段保证线程同步 方法2、 使用Lock 它是一个接口用于支持更灵活的线程同步
import java.util.ArrayList;
import java.util.Collection;
import java.util.LinkedHashMap;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
import java.util.Map;/*** 类说明利用LinkedHashMap实现简单的缓存 必须实现removeEldestEntry方法具体参见JDK文档** param K* param V* author dennis*/
public class LRULinkedHashMapK, V extends LinkedHashMapK, V {private final int maxCapacity;private static final float DEFAULT_LOAD_FACTOR 0.75f;private final Lock lock new ReentrantLock();public LRULinkedHashMap(int maxCapacity) {super(maxCapacity, DEFAULT_LOAD_FACTOR, true);this.maxCapacity maxCapacity;}Overrideprotected boolean removeEldestEntry(java.util.Map.EntryK, V eldest) {return size() maxCapacity;}Overridepublic boolean containsKey(Object key) {try {lock.lock();return super.containsKey(key);} finally {lock.unlock();}}Overridepublic V get(Object key) {try {lock.lock();return super.get(key);} finally {lock.unlock();}}Overridepublic V put(K key, V value) {try {lock.lock();return super.put(key, value);} finally {lock.unlock();}}public int size() {try {lock.lock();return super.size();} finally {lock.unlock();}}public void clear() {try {lock.lock();super.clear();} finally {lock.unlock();}}public CollectionMap.EntryK, V getAll() {try {lock.lock();return new ArrayListMap.EntryK, V(super.entrySet());} finally {lock.unlock();}}
}
测试代码 测试结果见备注已经抛弃了test1 而替换为了最近一次使用过的test3
Test
public void a1() {LRULinkedHashMap lruLinkedHashMap new LRULinkedHashMap(3);lruLinkedHashMap.put(test,1235314);lruLinkedHashMap.put(test1,1235314);lruLinkedHashMap.get(test);lruLinkedHashMap.put(test2,1235314);System.out.println(lruLinkedHashMap.getAll()); // [test11235314, test1235314, test21235314]lruLinkedHashMap.put(test3,1235314);System.out.println(lruLinkedHashMap.getAll()); // [test1235314, test21235314, test31235314]
}
