缓存算法（FIFO、LRU、LFU三种算法的区别）

发表于

FIFO算法

FIFO 算法是一种比较容易实现的算法。它的思想是先进先出（FIFO，队列），这是最简单、最公平的一种思想，即如果一个数据是最先进入的，那么可以认为在将来它被访问的可能性很小。空间满的时候，最先进入的数据会被最早置换（淘汰）掉。

FIFO 算法的描述：设计一种缓存结构，该结构在构造时确定大小，假设大小为 K，并有两个功能：

1.set(key,value)：将记录(key,value)插入该结构。当缓存满时，将最先进入缓存的数据置换掉。
2.get(key)：返回key对应的value值。

实现：维护一个FIFO队列，按照时间顺序将各数据（已分配页面）链接起来组成队列，并将置换指针指向队列的队首。再进行置换时，只需把置换指针所指的数据（页面）顺次换出，并把新加入的数据插到队尾即可。

缺点：判断一个页面置换算法优劣的指标就是缺页率，而FIFO算法的一个显著的缺点是，在某些特定的时刻，缺页率反而会随着分配页面的增加而增加，这称为Belady现象。产生Belady现象现象的原因是，FIFO置换算法与进程访问内存的动态特征是不相容的，被置换的内存页面往往是被频繁访问的，或者没有给进程分配足够的页面，因此FIFO算法会使一些页面频繁地被替换和重新申请内存，从而导致缺页率增加。因此，现在不再使用FIFO算法。

LRU算法

LRU（The Least Recently Used，最近最久未使用算法）是一种常见的缓存算法，在很多分布式缓存系统（如Redis, Memcached）中都有广泛使用。

LRU算法的思想是：如果一个数据在最近一段时间没有被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最久没有访问的数据最先被置换（淘汰）。

LRU算法的描述： 设计一种缓存结构，该结构在构造时确定大小，假设大小为 K，并有两个功能：

1.set(key,value)：将记录(key,value)插入该结构。当缓存满时，将最久未使用的数据置换掉。
2.get(key)：返回key对应的value值。

实现：最朴素的思想就是用数组+时间戳的方式，不过这样做效率较低。因此，我们可以用双向链表（LinkedList）+哈希表（HashMap）实现（链表用来表示位置，哈希表用来存储和查找），在Java里有对应的数据结构LinkedHashMap。

自己写双链表DoubleList(内部封装函数，Node）

lc146.LRU缓存机制

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

示例:

1
2
3
4
5
6
7
8
9
10
11
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得关键字 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得关键字 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

分析上面的操作过程，要让 put 和 get 方法的时间复杂度为 O(1)O(1)，我们可以总结出 cache 这个数据结构必要的条件：查找快，插入快，删除快，有顺序之分。

因为显然 cache 必须有顺序之分，以区分最近使用的和久未使用的数据；而且我们要在 cache 中查找键是否已存在；如果容量满了要删除最后一个数据；每次访问还要把数据插入到队头。

那么，什么数据结构同时符合上述条件呢？哈希表查找快，但是数据无固定顺序；链表有顺序之分，插入删除快，但是查找慢。所以结合一下，形成一种新的数据结构：哈希链表。

LRU 缓存算法的核心数据结构就是哈希链表，双向链表和哈希表的结合体。这个数据结构长这样：
LRU缓存模型

思想很简单，就是借助哈希表赋予了链表快速查找的特性嘛：可以快速查找某个 key 是否存在缓存（链表）中，同时可以快速删除、添加节点。回想刚才的例子，这种数据结构是不是完美解决了 LRU 缓存的需求？

也许读者会问，为什么要是双向链表，单链表行不行？另外，既然哈希表中已经存了 key，为什么链表中还要存键值对呢，只存值不就行了？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
import java.util.*;
/**
 * @ClassName LRUCache
 * @Description TODO
 * @Author 谢梓
 * @Date 2020/5/26 16:39
 **/
class Node{
    public Node next,pre;
    public int key,val;
    public Node(int k,int v){
        key=k;
        val=v;

    }
}

class DoubleList{
    private Node head,tail;
    private int size;

    public DoubleList(){
        head=new Node(0,0);
        tail=new Node(0,0);
        head.next = tail;
        tail.pre = head;
        size=0;
    }

    public void addFirst(Node x){
        x.next=head.next;
        x.pre=head;
        head.next.pre=x;
        head.next=x;
        size++;
    }

    public void remove(Node x){//x一定存在
        x.next.pre=x.pre;
        x.pre.next=x.next;
        size--;
    }

    public Node removeLast(){
        if(tail.pre==head) return null;
        Node last=tail.pre;
        remove(last);
        return  last;
    }

    public int size(){
        return size;
    }
}

class LRUCache{
    private HashMap<Integer,Node> map;
    private int capacity;
    private DoubleList LRUList;

    public LRUCache(int c){
        capacity=c;
        LRUList=new DoubleList();
        map=new HashMap<Integer,Node>();///
    }

    public int get(int key){//
        if(!map.containsKey(key)) return -1;
        int val = map.get(key).val;
        // 利用 put 方法把该数据提前
        put(key, val);
        // LRUList.remove(map.get(key));
        // LRUList.addFirst(map.get(key));
        // return map.get(key).val;
        return val;
    }

    public void put(int key,int val){
        Node add=new Node(key,val);
        if(map.containsKey(key)){
            LRUList.remove(map.get(key));
            LRUList.addFirst(add);
            map.put(key,add);
        }
        else{
            if(capacity==LRUList.size()){
                Node last=LRUList.removeLast();
                map.remove(last.key);
            }
            LRUList.addFirst(add);
            map.put(key,add);
        }
    }

    public static void main(String[] args) {
//        LRUCache cache=new LRUCache(2);
//        cache.put(1,1);
//        cache.put(2,2);
//        System.out.println(cache.get(2));
//        cache.put(3,3);
//        System.out.println(cache.get(1));
//        StringBuilder test=new StringBuilder("123");
        LinkedList<StringBuilder> link=new LinkedList<>();
        link.removeLast();
    }
}

LFU算法

LFU（Least Frequently Used ，最近最少使用算法）也是一种常见的缓存算法。

顾名思义，LFU算法的思想是：如果一个数据在最近一段时间很少被访问到，那么可以认为在将来它被访问的可能性也很小。因此，当空间满时，最小频率访问的数据最先被淘汰。

LFU 算法的描述：

设计一种缓存结构，该结构在构造时确定大小，假设大小为 K，并有两个功能：

1.set(key,value)：将记录(key,value)插入该结构。当缓存满时，将访问频率最低的数据置换掉。
2.get(key)：返回key对应的value值。

算法实现策略：考虑到 LFU 会淘汰访问频率最小的数据，我们需要一种合适的方法按大小顺序维护数据访问的频率。 LFU 算法本质上可以看做是一个 top K 问题(K = 1)，即选出频率最小的元素，因此我们很容易想到可以用二项堆来选择频率最小的元素，这样的实现比较高效。最终实现策略为小顶堆+哈希表。

出处：https://www.cnblogs.com/hongdada/p/10406902.html