算法之LRU和LFU算法_lfusix

在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。

评价一个缓存算法好坏的标准主要有两个，一是命中率要高，二是算法要容易实现。当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存污染情况比较严重。LFU效率要优于LRU，且能够避免周期性或者偶发性的操作导致缓存命中率下降的问题。但LFU需要记录数据的历史访问记录，一旦数据访问模式改变，LFU需要更长时间来适用新的访问模式，即：LFU存在历史数据影响将来数据的“缓存污染”效用。FIFO虽然实现很简单，但是命中率很低，实际上也很少使用这种算法。

1、LRU

最近最少使用，淘汰最近不使用的页面
LRU表示最近最久未使用算法，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高”。即LRU算法是与每个页面最后使用的时间有关的。
1. 新数据插入到链表头部；
2. 每当缓存命中（即缓存数据被访问），则将数据移到链表头部；
3. 当链表满的时候，将链表尾部的数据丢弃。

以下为利用双向链表和HashMap实现LRU的代码,算法时间复杂度为O（1）（备注：其实也可以直接使用LinkedHashMap实现LRU）

import java.util.HashMap;
import java.util.Map.Entry;
import java.util.Set;

public class LRUCache<K, V> {
    //存储的单位元素
    class CacheNode{
        Object key;
        Object value;
        CacheNode pre;//用于构造双向链表
        CacheNode next;
        public CacheNode(Object key，Object value){
            this.key = key;
            this.value = value;
        }
        public CacheNode(){
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17