SakuraTears的博客

越努力越幸运

缓存淘汰算法（LFU、LRU、FIFO、ARC、MRU）

发表于 分类于 阅读次数： Valine：
本文字数： 40k 阅读时长 ≈ 36 分钟

前言

一般情况下，我们读取数据，无论从数据库还是磁盘，都是比较慢的，要加快数据读取可以使用缓存，将数据缓存下来。例如比较有名的工具Redis等。

无论如何缓存数据，随着数据量增大，内存容量是有一定限制的，因此我们只能缓存定量的数据。

对于我们来说，肯定要缓存经常使用或者未来很大概率被使用的数据，这样才有利于我们的业务。

因此对于定量的缓存，如果缓存量过大，势必要删除一部分缓存数据，这就涉及到了缓存的淘汰策略问题。

正文

常用的缓存淘汰算法一般有5种，FIFO、LRU、LFU、ARC、MRU。

如下图：

upload successful

最常使用的是LRU和LFU缓存淘汰算法。

接下来我们分别来看下这5种缓存淘汰算法。

由于每种算法都写了一些Java代码实现，对其进行整理后，我们需要实现以下两个方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public interface Cache<K,V> {
    /**
     * 从缓存获取数据
     * @param key
     * @return
     */
    V get(K key);

    /**
     * 向缓存放入数据
     * @param key
     * @param value
     */
    void set(K key,V value);
}

FIFO

FIFO(First In First Out) 先进先出淘汰算法，这种淘汰算法非常好理解，我们不关心缓存数据实际访问情况，如果缓存满了后，自动删除较早放入的缓存数据。

一般我们使用队列就可以实现这种淘汰算法。

优点：内存占用低、速度快、实现简单。

缺点：缓存命中率低、使用价值也不高。

这儿我提供了两种相关FIFO淘汰算法的实现，一种借助Java中的工具类LinkedList，一种是自己手写了一个先进先出（FIFO）队列。

FIFO相关接口

1
2
3
public interface IFIFOCache<K,V> extends Cache<K,V>{

}

实现方案一：借助LinkedList。

该方案 内存占用高，但借助HashMap，可以实现接近O(1)的查找效率。

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
public class FIFOCache<K,V> implements IFIFOCache<K,V> {


    /**
     * 容量
     */
    private int capacity;

    /**
     * linkedList可以遵循先进先出
     */
    private LinkedList<K> linkedList;

    /**
     * 用来存储value值
     */
    private Map<K,V> hashMap;


    public FIFOCache(int capacity) {
        if(capacity < 1){
            throw new RuntimeException("容量不能小于1");
        }
        this.capacity = capacity;
        linkedList = new LinkedList<>();
        hashMap = new HashMap<>(capacity);
    }

    @Override
    public V get(K key) {
        return hashMap.get(key);
    }

    @Override
    public void set(K key, V value) {

        //设置值时，判断K存不存在
        V v = hashMap.get(key);
        if(v == null){
            //没有的话新增即可
            hashMap.put(key,value);
            //添加到链表尾
            linkedList.add(key);
        }else{
            //存在更新即可
            hashMap.put(key,value);
        }

        //判断容量
        int size = linkedList.size();
        if(size > capacity){
            //删除头部元素
            K k = linkedList.poll();
            hashMap.remove(k);
        }
    }
}

实现方案二，手写一个先进先出队列，头部删除旧元素，尾部放入新元素。

该方案 内存占用低，但查找时需要遍历链表，时间复杂度较高。

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
107
108
109
110
111
112
113
114
115
116
117
118
119
public class FIFOCache1<K,V> implements IFIFOCache<K,V>{

    /**
     * 容量
     */
    private int capacity;

    private DoublePointLinkedList<K,V> linkedList;

    public FIFOCache1(int capacity) {
        if(capacity < 1){
            throw new RuntimeException("容量不能小于1");
        }
        this.capacity = capacity;
        linkedList = new DoublePointLinkedList<>();
    }

    @Override
    public V get(K key) {
        DoublePointLinkedList<K,V>.Node<K,V> node = linkedList.get(key);
        if(node == null){
            return null;
        }
        return node.value;
    }

    @Override
    public void set(K key, V value) {
        DoublePointLinkedList<K,V>.Node<K,V> node = linkedList.get(key);
        if(node != null){
            //更新一下值
            node.value = value;
        }else{
            //长度超过容量，删除头部元素
            if(linkedList.size >= capacity){
                linkedList.delHead();
            }
            //将新值添加到队尾
            linkedList.addTail(key,value);
        }

    }


    public class DoublePointLinkedList<K,V> {
        private int size;
        private Node<K,V> head;
        private Node<K,V> tail;

        private class Node<K,V> {
            private Node<K,V> next;
            private K key;
            private V value;

            public Node(K key,V value) {
                this.key = key;
                this.value = value;
            }
        }

        public DoublePointLinkedList() {
            this.size = 0;
            this.head = null;
            this.tail = null;
        }

        public V addHead(K key,V value) {
            Node<K,V> node = new Node<>(key,value);
            if (size == 0) {
                head = node;
                tail = node;
            } else {
                node.next = head;
                head = node;
            }
            size++;
            return value;
        }

        public V addTail(K key,V value) {
            Node<K,V> node = new Node<>(key,value);
            if (size == 0) {
                head = node;
                tail = node;
            } else {
                tail.next = node;
                tail = node;
            }
            size++;
            return value;
        }

        public Node<K,V> get(K key){
            Node<K,V> node = head;
            while (node!=null){
                if(node.key.equals(key)){
                    return node;
                }
                node = node.next;
            }
            return null;
        }

        public boolean delHead() {
            if (size == 0) {
                return false;
            }
            //只有一个元素
            if (size == 1 && head.next == null) {
                head = null;
                tail = null;
            } else {
                head = head.next;
            }
            size--;
            return true;
        }
    }
}

LRU

LRU(Least Recently used) 最近最少使用缓存淘汰算法，其淘汰最近一段时间最少被访问的缓存数据。

其核心思想是如果数据最近被访问过，那么将来被访问的几率也更高，其不关心数据的访问频次。

我们使用队列可以实现这种淘汰算法，对于访问的元素，移动到链表尾，这样链表头为较旧的元素，当容量满时，淘汰掉链表头元素即可。

优点：实现方式较简单，且缓存命中率也较高，占用内存也不高。

缺点：需要遍历链表查询，效率较低；该方式仅从时间维度考虑数据，未考虑数据访问频次，如果一个经常访问的热点数据近期没有被访问（偶发性），导致缓存将其删除，而后在访问时无法命中，导致LRU命中率下降。

借助Java里的工具类LinkedHashMap，我们可以方便的实现LRU。LinkedHashMap有个参数accessOrder，当设置为true时，被访问的元素（较新的）会被移动到链表尾。同时如果重写了removeEldestEntry方法，当达到条件时，LinkedHashMap便会删除链表头（较旧的）元素。

相关代码如下：

1
2
public interface ILRUCache<K,V> extends Cache<K,V>{
}

借助LinkedHashMap，我们可以实现查找接近O(1)的LRU。

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
public class LRUCache<K,V> implements ILRUCache<K,V> {

    private int capacity;

    private Map<K,V> linkedHashMap;

    public LRUCache(int capacity) {
        if(capacity < 1){
            throw new RuntimeException("容量不能小于1");
        }
        this.capacity = capacity;
        linkedHashMap = new TLinkedHashMap<>(capacity);
    }

    @Override
    public V get(K key) {
        return linkedHashMap.get(key);
    }

    @Override
    public void set(K key, V value) {
        linkedHashMap.put(key, value);
    }


    /**
     * 配置使用的LinkedHashMap
     * 删除旧元素的条件是长度超过容量
     * @param <K>
     * @param <V>
     */
    public class TLinkedHashMap<K,V> extends LinkedHashMap<K,V>{

        private int capacity;

        public TLinkedHashMap(int capacity) {
            super(capacity,0.75f,true);
            this.capacity = capacity;
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
            return size() > capacity;
        }
    }
}

LRU-K

LRU-K中的K代表次数，相比于普通的LRU（可以认为LRU-1），其主要为了解决上面提到的偶发性问题。

核心思想是将最近使用过1次的判断标准改为最近使用过K次。

优点：相比于LRU，对于偶发性数据LRU-K有更好的适应性，命中率也比普通LRU更高。
缺点：LRU-K需要额外记录历史缓存数据，内存消耗要比LRU要高。

我们通过两个LinkedHashMap来实现LRU-K。

其实现原理如下：

  1. 数据第一次被访问，加入到访问历史列表；
  2. 如果数据在访问历史列表里后没有达到K次访问，则按照一定规则（FIFO，LRU）淘汰；
  3. 当访问历史队列中的数据访问次数达到K次后，将数据索引从历史队列删除，将数据移到缓存队列中，并缓存此数据，缓存队列重新按照时间排序；
  4. 缓存数据队列中被再次访问后，重新排序；
  5. 需要淘汰数据时，淘汰缓存队列中排在末尾的数据，即淘汰“倒数第K次访问离现在最久”的数据。
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
public class LRU_KCache<K,V> implements ILRUCache<K,V>{

    //统计次数
    private int count;

    //缓存队列容量
    private int capacity;

    //辅助队列容量
    private int helpCapacity;

    //该队列用户缓存历史所有访问数据（删除数据方法：删除时间最早的元素）
    private Map<K,Cache<K,V>> helpLinkedHashMap;

    //缓存队列
    private Map<K,V> linkedHashMap;

    /**
     * 自定义一个构造方法，辅助队列容量默认为缓存队列的50倍
     * @param count
     * @param capacity
     */
    public LRU_KCache(int count, int capacity) {
        this(count,capacity,50*capacity);
    }

    public LRU_KCache(int count, int capacity, int helpCapacity) {
        if(capacity < 1 || helpCapacity < 1){
            throw new RuntimeException("容量不能小于1");
        }
        if(count < 1){
            throw new RuntimeException("次数不能小于1");
        }

        this.count = count;
        this.capacity = capacity;
        this.helpCapacity = helpCapacity;

        linkedHashMap = new TLinkedHashMap<>(capacity);
        //辅助队列，用于存储历史访问记录
        helpLinkedHashMap = new TLinkedHashMap<>(helpCapacity);
    }

    @Override
    public V get(K key) {

        //先从缓存队列里获取数据
        V v = linkedHashMap.get(key);

        //如果不存在，尝试从辅助队列里获取数据
        if(v == null){
            Cache<K,V> cache = helpLinkedHashMap.get(key);
            if(cache != null){
                //增加访问次数
                int temp = cache.addCount();
                v = cache.getValue();
                //达到指定次数后移至缓存队列
                if(temp >= count){
                    linkedHashMap.put(key,v);
                    helpLinkedHashMap.remove(key);
                }else{
                    //没达到指定次数，更新下辅助队列数据
                    helpLinkedHashMap.put(key,cache);
                }
            }
        }

        return v;
    }

    @Override
    public void set(K key, V value) {

        //保存操作，首先判断缓存队列里是否有数据
        V v = linkedHashMap.get(key);
        if(v != null){
            //更新最新值
            linkedHashMap.put(key,value);
        }else{
            //没有值的话去辅助队列获取
            Cache<K,V> cache = helpLinkedHashMap.get(key);
            if(cache != null){
                //增加访问次数
                int temp = cache.addCount();
                cache.setValue(value);
                //达到指定次数后移至缓存队列
                if(temp >= count){
                    linkedHashMap.put(key,value);
                    helpLinkedHashMap.remove(key);
                }else{
                    //没达到指定次数，更新下辅助队列数据
                    helpLinkedHashMap.put(key,cache);
                }
            }else{
                //没有数据，新增即可
                cache = new Cache<>(key,value);
                helpLinkedHashMap.put(key,cache);
            }
        }

    }


    /**
     * 缓存队列移除元素原则：
     * 队列达到指定长度，队列里存的都是访问k次（及以上）的元素
     * @param <K>
     * @param <V>
     */
    public class TLinkedHashMap<K,V> extends LinkedHashMap<K,V> {

        private int capacity;

        public TLinkedHashMap(int capacity) {
            super(capacity,0.75f,true);
            this.capacity = capacity;
        }

        @Override
        protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
            return size() > capacity;
        }
    }


    public class Cache<K,V>{
        private int count;
        private K key;
        private V value;

        public Cache(K key, V value) {
            this.key = key;
            this.value = value;
        }

        /**
         * 增加次数
         * @return
         */
        public int addCount(){
            count++;
            return count;
        }

        public V getValue() {
            return value;
        }

        public void setValue(V value) {
            this.value = value;
        }
    }
}

2Q

2Q(Two queues) 算法类似于LRU-2，不同点在于2Q将LRU-2算法中的访问历史队列改为一个FIFO缓存队列，即：2Q算法有两个缓存队列，一个是FIFO队列，一个是LRU队列。

其工作原理如下：

  1. 新访问的数据插入到FIFO队列；
  2. 如果数据在FIFO队列中一直没有被再次访问，则最终按照FIFO规则淘汰；
  3. 如果数据在FIFO队列中被再次访问，则将数据移到LRU队列；
  4. 如果数据在LRU队列再次被访问，则按照LRU规则进行；
  5. LRU队列淘汰旧的数据。

其相关代码如下：

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
public class TwoQueueCache<K,V> implements ILRUCache<K,V> {

    private int capacity;

    private FIFOCache<K,V> fifoQueue;

    private LRUCache<K,V> lruQueue;

    public TwoQueueCache(int capacity) {
        if(capacity < 1){
            throw new RuntimeException("容量不能小于1");
        }
        this.capacity = capacity;
        this.fifoQueue = new FIFOCache<>(50 * capacity);
        this.lruQueue = new LRUCache<>(capacity);
    }

    @Override
    public V get(K key) {

        //先判断lru是否有数据
        V v = lruQueue.get(key);
        if(v != null){
            return v;
        }
        //没有查询fifo队列是否有数据
        v = fifoQueue.get(key);
        if(v != null){
            //放入lru队列
            lruQueue.set(key,v);
            //fifo删除数据
            fifoQueue.remove(key);
        }
        //查不到返回null
        return null;
    }

    @Override
    public void set(K key, V value) {
        //先查询lru是否存在数据
        if(lruQueue.contains(key)){
            lruQueue.set(key,value);
            return;
        }
        //判断fifo队列是否存在
        V v = fifoQueue.get(key);
        if(v != null){
            //放入lru队列
            lruQueue.set(key,value);
            //fifo删除数据
            fifoQueue.remove(key);
            return;
        }
        //fifo队列不存在，直接放入
        fifoQueue.set(key,value);
    }
}

LFU

LFU(Least Frequently Used) 最近最不常用，其是基于数据的访问频次及访问时间来对缓存数据进行淘汰的算法。

相比于LRU，LFU对于偶发性数据具有更好的适应性，其淘汰数据依据两点：访问频次、访问时间。

其核心思想是如果数据过去被访问多次，那么将来被访问的频率也更高。

优点：命中率较高

缺点：实现较复杂，内存占用较高，需要记录数据的访问频次和最新时间，实现不好的话，时间复杂度也可能较高。

我们来看下相关代码：

1
2
public interface ILFUCache<K,V> extends Cache<K,V>{
}

实现方案一

借助HashMap来实现（删除访问次数较少并且更新时间较早的数据时需要遍历），删除元素时需要遍历缓存Map找到“最小”数据并删除，实现简单，不过效率低下。

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
public class LFUCache0<K,V> implements ILFUCache<K,V>{

    /**
     * 容量
     */
    private int capacity;

    /**
     * 缓存数据
     */
    private Map<K,CacheObject<V>> cacheMap;

    public LFUCache0(int capacity) {
        this.capacity = capacity;
        this.cacheMap = new HashMap<>(capacity);
    }


    /**
     * 根据k获取某个值
     * @param k
     * @return
     */
    @Override
    public V get(K k){
        //取不到返回null
        CacheObject<V> object = cacheMap.get(k);
        if(object == null){
            return null;
        }
        //取到更新次数及时间
        return object.getValue();
    }

    /**
     * 设置某个值
     * @param k
     * @param v
     */
    @Override
    public void set(K k,V v){
        //容量不能为0
        if(capacity == 0){
            return;
        }
        //先尝试获取缓存数据
        CacheObject<V> object = cacheMap.get(k);
        if(object == null){
            //放入前先检查容量，如果已满，删除访问次数较少并且更新时间较早的数据
            if(cacheMap.size() >= capacity){
                cacheMap.entrySet().stream().min(Comparator.comparing(Map.Entry::getValue)).ifPresent(e->{
                    cacheMap.remove(e.getKey());
                });
            }
            object = new CacheObject<>(v);
        }else{
            //有数据，直接进行更新
            object.setValue(v);
        }
        cacheMap.put(k,object);
    }


    /**
     * 数据缓存类
     * @param <V>
     */
    public class CacheObject<V> implements Comparable<CacheObject<V>> {

        /**
         * 数据值
         */
        private V value;

        /**
         * 最后更新时间
         */
        private long lastUpdateTime;

        /**
         * 访问次数
         */
        private int accessCount;


        public CacheObject(V value) {
            this.value = value;
            this.lastUpdateTime = System.nanoTime();
            this.accessCount++;
        }

        /**
         * 获取值
         * @return
         */
        public V getValue() {
            this.lastUpdateTime = System.nanoTime();
            this.accessCount++;
            return value;
        }

        /**
         * 更新值
         * @param value
         */
        public void setValue(V value) {
            this.value = value;
            this.lastUpdateTime = System.nanoTime();
            this.accessCount++;
        }

        @Override
        public int compareTo(CacheObject<V> o) {
            //比较次数大小
            int value = Integer.compare(this.accessCount,o.accessCount);
            //如果次数相同，比较时间大小
            return value == 0 ? Long.compare(this.lastUpdateTime,o.lastUpdateTime) : value;
        }
    }
}

实现方案二

借助TreeSet和HashMap来实现，TreeSet自动排序，删除操作O(1)复杂度；但额外引入了TreeSet，空间复杂度增加，同时每放入一个元素，需要重新排序。

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
public class LFUCache1<K,V> implements ILFUCache<K,V>{
    /**
     * 容量
     */
    private int capacity;

    /**
     * 缓存Map
     */
    private Map<K,CacheObject<K,V>> cacheMap;

    /**
     * 有序Set
     */
    private TreeSet<CacheObject<K,V>> treeSet;


    public LFUCache1(int capacity) {
        this.capacity = capacity;
        this.cacheMap = new HashMap<>(capacity);
        this.treeSet = new TreeSet<>(CacheObject<K,V>::compareTo);
    }

    /**
     * 获取某个元素
     * @param key
     * @return
     */
    @Override
    public V get(K key){
        CacheObject<K,V> cache = cacheMap.get(key);
        if(cache == null){
            return null;
        }
        //删除该对象
        treeSet.remove(cache);
        //拿到value（同时更新访问次数和时间）
        V value = cache.getValue();
        //添加该对象（treeSet会根据compare进行排序）
        treeSet.add(cache);
        cacheMap.put(key,cache);

        return value;
    }

    /**
     * 设置值
     * @param key
     * @param value
     */
    @Override
    public void set(K key,V value){
        if(capacity == 0){
            return;
        }
        CacheObject<K,V> cache = cacheMap.get(key);
        if(cache == null){
            if(cacheMap.size() >= capacity){
                //treeSet头部元素为最小元素（访问次数较少并且更新时间较早）
                //删除Map和treeSet中此条数据
                cacheMap.remove(treeSet.first().getKey());
                treeSet.pollFirst();
            }
            cache = new CacheObject<>(key,value);
        }else{
            treeSet.remove(cache);
            cache.setValue(value);
        }

        treeSet.add(cache);
        cacheMap.put(key,cache);
    }

    /**
     * 缓存类
     * @param <K>
     * @param <V>
     */
    public class CacheObject<K,V> implements Comparable<CacheObject<K,V>> {

        private K key;
        /**
         * 数据值
         */
        private V value;

        /**
         * 最后更新时间
         */
        private long lastUpdateTime;

        /**
         * 访问次数
         */
        private int accessCount;

        public K getKey() {
            return key;
        }

        public CacheObject(K key, V value) {
            this.key = key;
            setValue(value);
        }

        /**
         * 获取值
         * @return
         */
        public V getValue() {
            this.lastUpdateTime = System.nanoTime();
            this.accessCount++;
            return value;
        }

        /**
         * 更新值
         * @param value
         */
        public void setValue(V value) {
            this.value = value;
            this.lastUpdateTime = System.nanoTime();
            this.accessCount++;
        }

        @Override
        public int compareTo(CacheObject<K,V> o) {
            //比较次数大小
            int value = Integer.compare(this.accessCount,o.accessCount);
            //如果次数相同，比较时间大小
            return value == 0 ? Long.compare(this.lastUpdateTime,o.lastUpdateTime) : value;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            CacheObject<?, ?> that = (CacheObject<?, ?>) o;
            return lastUpdateTime == that.lastUpdateTime &&
                    accessCount == that.accessCount &&
                    Objects.equals(key, that.key) &&
                    Objects.equals(value, that.value);
        }

        @Override
        public int hashCode() {
            return Objects.hash(key, value, lastUpdateTime, accessCount);
        }
    }
}

下面我们提供两种时间复杂度接近O(1)的LFU代码示例。

实现方案三

借助LinkedHashMap、双向链表、HashMap来实现。

原理：

  1. 用一个双向链表来保存命中数；
  2. 命中数相同的放在一个双向链表的LinkedHashMap中，主要是利用了它的accessOrder属性来实现根据访问顺序来排序；
  3. HashMap集合来保存所有的元素，因为只要key的hash算法合理的理想情况下，put，get操作是O(1)；
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
public class LFUCache2<K,V> implements ILFUCache<K,V>{

    private static final Object PRESENT = new Object();

    /**
     * 容量
     */
    private final int capacity;

    /**
     * 缓存map
     */
    private final Map<K, CacheObject<K,V>> cacheMap;

    /**
     * 数据链表
     */
    private Node<K> countHead;

    /**
     * 构造函数
     * @param capacity
     */
    public LFUCache2(int capacity){
        if (capacity < 1) {
            throw new RuntimeException("参数错误，容量不能小于1");
        }
        this.capacity = capacity;

        cacheMap = new HashMap<>(capacity);
    }

    /**
     * 链表节点
     * @param <K>
     */
    public class Node<K> {

        /**
         * 次数
         */
        int count;

        /**
         * 下一个节点
         */
        Node<K> next;

        /**
         * 上一个节点
         */
        Node<K> prev;

        /**
         * 如果访问次数相同，会被存入linkMap中，最先被访问过的放在链表后面
         */
        LinkedHashMap<K,Object> linkMap;

        Node(Node<K> prev, int count, Node<K> next) {
            this.count = count;
            this.next = next;
            this.prev = prev;
        }
    }

    /**
     * 缓存对象
     * @param <K>
     * @param <V>
     */
    private class CacheObject<K,V> {
        V value;
        Node<K> node;
        CacheObject(V val, Node<K> node) {
            this.value = val;
            this.node = node;
        }
    }

    /**
     * 放入缓存
     * @param key
     * @param value
     */
    @Override
    public void set(K key, V value){

        // 容量不足时缓存删除
        removeCache(key);
        // 放入缓存
        putVal(key, value);
    }

    /**
     * 缓存删除
     * @param key
     */
    private void removeCache(K key){

        //如果有K,不需要判定容量问题
        if (cacheMap.containsKey(key)) {
            return;
        }

        Node<K> first;

        K removeKey = null;

        // 超过最大缓存容量
        while(cacheMap.size() >= capacity) {
            // 第一个节点
            if ((first=countHead) != null) {
                // 节点元素存在
                if (first.linkMap != null && !first.linkMap.isEmpty()) {
                    // 该节点只有一个元素的场合
                    if (first.linkMap.size() == 1) {
                        removeKey = (K) first.linkMap.keySet().toArray()[0];
                        countHead = first.next;
                        countHead.prev = null;
                        first = null;
                    } else {
                        Iterator<K> iterator = first.linkMap.keySet().iterator();
                        if (iterator.hasNext()) {
                            removeKey = iterator.next();
                            first.linkMap.remove(removeKey);
                        }
                    }
                    cacheMap.remove(removeKey);
                    // 节点元素不存在
                } else {
                    countHead = first.next;
                }
            }
        }
    }

    /**
     * 放入缓存
     * @param key
     * @param val
     */
    private void putVal(K key, V val) {

        Node<K> be = null;
        // 新加入缓存的场合
        if (!cacheMap.containsKey(key)) {

            LinkedHashMap<K,Object> newLinkMap = new LinkedHashMap<>(capacity, 0.75f, true);
            // 有缓存一次的场合
            if (countHead != null && countHead.count == 1){

                if (countHead.linkMap == null) {
                    countHead.linkMap = newLinkMap;
                }
                countHead.linkMap.put(key,PRESENT);
                be = countHead;

            } else {
                Node<K> first = countHead;
                Node<K> node = new Node<>(null, 1, countHead == null ? null : first);
                newLinkMap.put(key,PRESENT);
                node.linkMap = newLinkMap;
                be = node;
                // 缓存不为空，即存在大于1的缓存，把1放在前面
                if (countHead != null) {
                    first.prev = node;
                }
                countHead = node;
            }

        } else {
            moveCount(key);
        }
        cacheMap.put(key, new CacheObject<>(val, be));
    }

    /**
     * 从缓存中取得数据，同时随着访问次数的增加，移动元素
     * @param key
     * @return
     */
    @Override
    public V get(K key) {

        if (!cacheMap.containsKey(key)) {
            return null;
        }
        moveCount(key);
        return cacheMap.get(key).value;
    }

    /**
     * 随着访问次数增加来移动元素
     * @param key
     */
    private void moveCount(K key) {

        Node<K> currentNode = cacheMap.get(key).node;
        currentNode.linkMap.remove(key);
        int currentCount = currentNode.count;
        int nextCount = currentCount + 1;
        LinkedHashMap<K,Object> newLinkMap = new LinkedHashMap<>(capacity, 0.75f, true);

        Node<K> after = currentNode.next;
        Node<K> before = currentNode.prev;
        if (currentNode.linkMap.size() == 0) {
            currentNode = null;
        } else {
            before = currentNode;
        }

        // 下一个节点没有的场合,新增一个+1的节点放到最后
        if (after == null) {
            Node<K> node = new Node<>(before, nextCount, null);
            newLinkMap.put(key, PRESENT);
            node.linkMap = newLinkMap;
            cacheMap.get(key).node = node;
            before.next = node;
            // 下一个正好是+1次数的节点，直接追加
        } else if (after.count == nextCount) {
            after.linkMap.put(key, PRESENT);
            before.next = after;
            after.prev = before;
            cacheMap.get(key).node = after;
            // 下一个节点的次数>+1次数，新建+1节点，再连接前后节点
        } else if (after.count > nextCount) {
            Node<K> node = new Node<>(before, nextCount, after);
            newLinkMap.put(key, PRESENT);
            node.linkMap = newLinkMap;
            cacheMap.get(key).node = node;
            before.next = node;
            after.prev  = node;
        }
    }
}

实现方案四

只借助HashMap和双向链表实现O(1)的LFU。

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
public class LFUCache3<K,V> implements ILFUCache<K,V>{


    private Map<K, Node<K,V>> map;

    private int capacity;

    private Map<Integer, DoubleLinkedList<K,V>> countMap;
    /**
     * 最小频次
     */
    private int min;

    /**
     * 链表节点
     * @param <K>
     * @param <V>
     */
    public class Node<K,V> {
        K key;
        V value;
        int count;
        Node<K,V> prev;
        Node<K,V> next;

        Node(){

        }
        Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.count = 1;
        }
    }

    public LFUCache3(int capacity) {
        if(capacity < 1){
            throw new RuntimeException("参数错误，容量不能小于1");
        }
        this.capacity = capacity;
        this.map = new HashMap<>(capacity);
        this.countMap = new HashMap<>();
        this.min = Integer.MAX_VALUE;
    }

    @Override
    public V get(K key) {
        if (!map.containsKey(key)) {
            return null;
        }
        Node<K,V> node = map.get(key);
        if (node == null) {
            return null;
        }
        handle(node, false);
        return node.value;
    }


    /**
     * 关键函数，当put/set操作发生后调用此函数，分为新增结点以及对现有结点操作
     * 1、新增结点：直接接到对于频次的双向链表头部
     * 2、已存在结点：从老结点所在频次对应的双向链表中删除此结点后，再将其加入到频次+1对应的双向链表的头部
     * @param node 结点
     * @param isNew 是否是新增结点
     */
    private void handle(Node<K,V> node, boolean isNew) {
        int count = node.count;
        //维护全局最小频次
        min = Math.min(count, min);
        //如果有这个次数的Map
        if (countMap.containsKey(node.count)) {
            //拿到旧链表
            DoubleLinkedList<K,V> oldList = countMap.get(node.count);
            if (!isNew) {
                //不是新增的话，由于访问次数变化，需要在链表下删除该节点
                node.count++;
                oldList.delNode(node);
                // 如果
                // 1、当前结点不为新增结点
                // 2、当前结点频次==全局最小频次
                // 3、且删除该结点后，对应频次双向链表为空，
                // 则全局最小频次+1
                if (count == min && oldList.size == 0) {
                    countMap.remove(min);
                    min++;
                }
            }
        }
        //没有需要新增一个
        if (!countMap.containsKey(node.count)) {
            countMap.put(node.count, new DoubleLinkedList<>());
        }
        DoubleLinkedList<K,V> newList = countMap.get(node.count);
        newList.addHead(node);
    }


    @Override
    public void set(K key, V val) {
        Node<K,V> node;
        if (map.containsKey(key)) {
            node = map.get(key);
            node.value = val;
            handle(node, false);
        } else {
            node = new Node<>(key, val);
            //容量超出，则删除全局最小频次对应双向链表中的尾部结点
            if (map.size() >= capacity) {
                DoubleLinkedList<K,V> oldList = countMap.get(min);
                Node<K,V> tail = oldList.delTail();
                map.remove(tail.key);
            }
            map.put(key, node);
            handle(node, true);
        }

    }

    /**
     * 双向链表
     * @param <K>
     * @param <V>
     */
    public class DoubleLinkedList<K,V> {
        int size;
        Node<K,V> head;
        Node<K,V> tail;

        public DoubleLinkedList() {
            this.size = 0;
            this.head = new Node<>();
            this.tail = new Node<>();
            this.head.next = tail;
            this.tail.prev = head;
        }

        void addHead(Node<K,V> node) {
            node.next = head.next;
            head.next.prev = node;
            node.prev = head;
            head.next = node;
            size++;
        }


        void delNode(Node<K,V> node) {
            Node<K,V> prev = node.prev;
            Node<K,V> next = node.next;
            prev.next = next;
            next.prev = prev;
            size--;
        }


        Node<K,V> delTail() {
            Node<K,V> node = this.tail.prev;
            node.prev.next = this.tail;
            this.tail.prev = node.prev;
            node.prev = null;
            node.next = null;
            size--;
            return node;
        }

    }
}

MRU

MRU(Most recently used) 最近最常使用，这种缓存淘汰算法使用的较少，其淘汰最近常用的项目。一般用于处理一个条目越久，越容易被访问的情况。

核心原理：一条数据很久没有被访问，则它将来被访问的概率可能会很高。

可以看到它和LRU是正好相反的。

优点：对于一些特定的场景，可能会有很好的效果。
缺点：适用范围比较窄。

其相关代码如下，这儿使用双向链表来实现：

1
2
public interface IMRUCache<K,V> extends Cache<K,V>{
}

这中方案查询会遍历双向链表，时间复杂度较高，如果实现接近O(1)的MRU可以借助HashMap，当然空间复杂度会变高，与LRU类似，这儿不再过多介绍。

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
public class MRUCache<K,V> implements IMRUCache<K,V>{


    //缓存队列容量
    private int capacity;

    //缓存队列
    private DoubleWayLinkedList<K,V> linkedList;


    public MRUCache(int capacity) {
        if(capacity < 1){
            throw new RuntimeException("容量不能小于1");
        }
        this.capacity = capacity;
        //accessOrder为true的话，最近访问的都会在底部，我们达到容量后直接删除底部元素即可
        //由于linkedHashMap不支持public的删除底端元素，因此我们手动写一个双端队列，添加、访问数据后会进行排序，将最新访问的数据移动到尾部
        linkedList = new DoubleWayLinkedList<>(true);
    }

    @Override
    public V get(K key) {
        return linkedList.get(key);
    }

    @Override
    public void set(K key, V value) {
        //首先判断容量是否达到
        int size = linkedList.getSize();
        if(size >= capacity){
            //删除最新元素(尾部为最新元素)
            linkedList.delTail();
        }
        //添加元素
        linkedList.add(key,value);
    }

    /**
     * 双向链表，旧的元素在头部，新的元素在尾部
     */
    public class DoubleWayLinkedList<K,V> {

        private int size;

        private Node<K,V> head;

        private Node<K,V> tail;

        private boolean accessOrder;

        private class Node<K,V> {
            private K key;
            private V value;
            private Node<K,V> left;
            private Node<K,V> right;

            public Node(K key, V value) {
                this.key = key;
                this.value = value;
            }
        }

        public DoubleWayLinkedList() {
            this.size = 0;
            this.accessOrder = false;
            this.head = null;
            this.tail = null;
        }

        public DoubleWayLinkedList(boolean accessOrder) {
            this.accessOrder = accessOrder;
            this.size = 0;
            this.head = null;
            this.tail = null;
        }

        public V get(K key){
            Node<K,V> node = getNode(key);
            if(node ==null){
                return null;
            }
            if(accessOrder){
                //排序，将刚访问的放到尾部
                afterNodeAccess(node);
            }
            return node.value;
        }


        public V add(K key,V value){
            //先判断元素key存不存在
            Node<K,V> node = getNode(key);
            if(node == null){
                //新增数据直接添加到链表尾部
                return addTail(key,value);
            }else{
                //存在数据的话，直接更新数据，并移动到链表尾部
                node.value = value;
                afterNodeAccess(node);
                return value;
            }

        }

        private Node<K,V> getNode(K key){
            Node<K,V> node = head;
            while (node!=null){
                if(node.key.equals(key)){
                    return node;
                }
                node = node.right;
            }
            return null;
        }

        private void afterNodeAccess(Node<K,V> e) { // move node to last
            Node<K,V> last;
            if (accessOrder && (last = tail) != e) {
                Node<K,V> p = e, b = p.left, a = p.right;
                p.right = null;
                if (b == null) {
                    head = a;
                }else {
                    b.right = a;
                }
                if (a != null) {
                    a.left = b;
                }else {
                    last = b;
                }
                if (last == null) {
                    head = p;
                }else {
                    p.left = last;
                    last.right = p;
                }
                tail = p;
            }
        }

        private V addHead(K key,V value) {
            Node<K,V> node = new Node<>(key,value);
            if (size == 0) {
                head = node;
                tail = node;
            } else {
                head.left = node;
                node.right = head;
                head = node;
            }
            size++;
            return value;
        }

        private V addTail(K key,V value) {
            Node<K,V> node = new Node<>(key,value);
            if (size == 0) {
                head = node;
                tail = node;
            } else {
                node.left = tail;
                tail.right = node;
                tail = node;
            }
            size++;
            return value;
        }

        private boolean delHead() {
            if (size == 0) {
                return false;
            }
            head = head.right;
            //只有一个节点，此时head.right=null，赋值head=null
            if (head != null) {
                head.left = null;
            }
            size--;
            return true;

        }

        public boolean delTail() {
            if (size == 0) {
                return false;
            }
            tail = tail.left;
            if (tail != null) {
                tail.right = null;
            }
            size--;
            return true;
        }

        public int getSize(){
            return size;
        }
    }
}

ARC

ARC(Adaptive Replacement Cache) 自适应缓存替换，这种缓存淘汰策略结合了 LRU 和 LFU 的特点。

ARC 的精髓就是根据被淘汰数据的访问情况，而增加对应 LRU 还是 LFU 链表的大小。

ARC 包含了四个链表。 LRU 和 LRU Ghost ， LFU 和 LFU Ghost， Ghost 链表为对应淘汰的数据记录链表，不记录数据，只记录 ID 等信息。

当数据 A 加入 LRU 后，如果 A 再次被访问，则同时被放到 LFU 链表中。所以 LFU 链表的缓存为 LRU 链表的多次访问的数据。

当 LRU 链表淘汰了 B，那么 B 的信息则进入到 LRU Ghost 链表。如果 B 在之后再次被访问，则增加 LRU 链表的大小，同时缩减 LFU 链表的大小。LFU 链表同理。

所以，这是一个根据最近未使用和最少频率使用动态调整的算法。

优点：这种算法具有很高的命中率，且可以根据数据使用方式动态调整LRU或LFU内存大小。

缺点：实现较复杂，且内存占用较高。

我们用代码来实现一个ARC。

根据上面的LRU和LFU代码示例，由于Java自带的LinkedHashMap不能方便的操作内部旧元素。因此对于ARC内部使用的LRU，我们需要自写一个。而LFU可以采用上面的LFUCache3，但仍有一些方法需要补充。

因此我提供了两个时间复杂度接近O(1)的LRU和LFU用来实现ARC。

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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
public class ARC_LRUCache<K,V> implements ILRUCache<K,V> {

    private int capacity;

    private TLinkedHashMap<K,V> linkedHashMap;

    public ARC_LRUCache(int capacity) {
        if(capacity < 1){
            throw new RuntimeException("容量不能小于1");
        }
        this.capacity = capacity;
        linkedHashMap = new TLinkedHashMap<>(capacity,true);
    }

    @Override
    public V get(K key) {
        return linkedHashMap.get(key);
    }

    @Override
    public void set(K key, V value) {
        linkedHashMap.add(key, value);
    }

    public int size(){
        return linkedHashMap.size();
    }

    public boolean contains(K key){
        return linkedHashMap.contains(key);
    }

    public void remove(K key){
        linkedHashMap.remove(key);
    }

    public K removeEldest(){
        return linkedHashMap.removeEldest();
    }

    /**
     * 双向链表，旧的元素在头部，新的元素在尾部
     * 由于原来使用Java自带的LinkedHashMap没法方便的操作旧元素，仿照LinkedHashMap自写一个即可
     */
    public class TLinkedHashMap<K,V> {
        private int size;
        private int capacity;
        private Node<K,V> head;
        private Node<K,V> tail;
        private Map<K,Node<K,V>> hashMap;
        private boolean accessOrder;

        private class Node<K,V> {
            private K key;
            private V value;
            private Node<K,V> left;
            private Node<K,V> right;

            public Node(K key,V value) {
                this.key = key;
                this.value = value;
            }
        }

        public TLinkedHashMap(int capacity,boolean accessOrder) {
            this(capacity,0.75f,accessOrder);
        }

        public TLinkedHashMap(int capacity,float loadFactor,boolean accessOrder) {
            this.accessOrder = accessOrder;
            this.size = 0;
            this.head = null;
            this.tail = null;
            this.capacity = capacity;
            this.hashMap = new HashMap<>(capacity,loadFactor);
        }

        public V get(K key){
            Node<K,V> node = hashMap.get(key);
            if(node == null){
                return null;
            }
            if(accessOrder){
                //排序，将刚访问的放到尾部
                afterNodeAccess(node);
            }
            return node.value;
        }


        public V add(K key,V value){
            //先判断元素key存不存在
            Node<K,V> node = hashMap.get(key);
            if(node == null){
                node = new Node<>(key,value);
                //新增数据直接添加到链表尾部
                hashMap.put(key,node);
                addTail(node);
                //判断容量是否超出，超出移除老元素
                if(size > capacity){
                    removeEldest();
                }
                return value;
            }else{
                //存在数据的话，直接更新数据，并移动到链表尾部
                node.value = value;
                hashMap.put(key,node);
                afterNodeAccess(node);
                return value;
            }
        }

        public K removeEldest(){
            Node<K,V> node = delHead();
            if(node != null){
                hashMap.remove(node.key);
                return node.key;
            }
            return null;
        }

        /**
         * 元素被访问，将其移动到链表尾部
         * @param e
         */
        private void afterNodeAccess(Node<K,V> e) {
            Node<K,V> last;
            if (accessOrder && (last = tail) != e) {
                Node<K,V> p = e, b = p.left, a = p.right;
                p.right = null;
                if (b == null) {
                    head = a;
                }else {
                    b.right = a;
                }
                if (a != null) {
                    a.left = b;
                }else {
                    last = b;
                }
                if (last == null) {
                    head = p;
                }else {
                    p.left = last;
                    last.right = p;
                }
                tail = p;
            }
        }

        private void addTail(Node<K,V> node) {
            if (size == 0) {
                head = node;
                tail = node;
            } else {
                node.left = tail;
                tail.right = node;
                tail = node;
            }
            size++;
        }

        private Node<K,V> delHead() {
            if (size == 0) {
                return null;
            }
            Node<K,V> temp = head;
            head = head.right;
            //只有一个节点，此时head.right=null，赋值head=null
            if (head != null) {
                head.left = null;
            }
            size--;
            return temp;
        }

        private void delNode(Node<K,V> node) {
            Node<K,V> prev = node.left;
            Node<K,V> next = node.right;
            if(prev != null){
                prev.right = next;
            }
            if(next != null){
                next.left = prev;
            }
            size--;
        }

        public int size(){
            return size;
        }

        public boolean contains(K key){
            return hashMap.containsKey(key);
        }

        public void remove(K key){
            Node<K,V> node = hashMap.get(key);
            if(node != null){
                delNode(node);
                hashMap.remove(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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
public class ARC_LFUCache<K,V> implements ILFUCache<K,V>{
    private Map<K, Node<K,V>> map;

    private int capacity;

    private Map<Integer, DoubleLinkedList<K,V>> countMap;
    private int min;

    public class Node<K,V> {
        K key;
        V value;
        int count;
        Node<K,V> prev;
        Node<K,V> next;

        Node(){

        }
        Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.count = 1;
        }
    }

    public ARC_LFUCache(int capacity) {
        if(capacity < 1){
            throw new RuntimeException("参数错误，容量不能小于1");
        }
        this.capacity = capacity;
        this.map = new HashMap<>(capacity);
        this.countMap = new HashMap<>();
        this.min = Integer.MAX_VALUE;
    }

    @Override
    public V get(K key) {
        if (!map.containsKey(key)) {
            return null;
        }
        Node<K,V> node = map.get(key);
        if (node == null) {
            return null;
        }
        handle(node, false);
        return node.value;
    }

    /**
     * 查询lfu中是否包含指定key值
     * @param key
     * @return
     */
    public boolean contains(K key){
        if (!map.containsKey(key)) {
            return false;
        }
        Node<K,V> node = map.get(key);
        if (node == null) {
            return false;
        }
        return true;
    }

    public int size(){
        return map.size();
    }

    public void remove(K key){
        if (!map.containsKey(key)) {
            return;
        }
        Node<K,V> node = map.get(key);
        if(countMap.containsKey(node.count)){
            //拿到双向链表
            DoubleLinkedList<K,V> oldList = countMap.get(node.count);
            //删除
            oldList.delNode(node);
            //判断是否全局最小值
            if(node.count == min && oldList.size == 0){
                countMap.remove(min);
                min = countMap.keySet().stream().min(Integer::compareTo).orElse(0);
            }
        }
        map.remove(key);
    }


    public K removeEldest(){
        //拿到全局最小频次数据，删除尾节点（时间较旧的数据）
        DoubleLinkedList<K,V> oldList = countMap.get(min);
        if(oldList == null){
            return null;
        }
        Node<K,V> tail = oldList.delTail();
        K key = tail.key;
        map.remove(key);
        //删除后，需要判断最小频次是否变化
        if(tail.count == min && oldList.size == 0){
            countMap.remove(min);
            min = countMap.keySet().stream().min(Integer::compareTo).orElse(0);
        }
        return key;
    }

    private void handle(Node<K,V> node, boolean isNew) {
        int count = node.count;
        //维护全局最小频次
        min = Math.min(count, min);
        //如果有这个次数的Map
        if (countMap.containsKey(node.count)) {
            //拿到旧链表
            DoubleLinkedList<K,V> oldList = countMap.get(node.count);
            if (!isNew) {
                //不是新增的话，由于访问次数变化，需要在链表下删除该节点
                node.count++;
                oldList.delNode(node);
                // 如果
                // 1、当前结点不为新增结点
                // 2、当前结点频次==全局最小频次
                // 3、且删除该结点后，对应频次双向链表为空，
                // 则全局最小频次+1
                if (count == min && oldList.size == 0) {
                    countMap.remove(min);
                    min++;
                }
            }
        }
        //没有需要新增一个
        if (!countMap.containsKey(node.count)) {
            countMap.put(node.count, new DoubleLinkedList<>());
        }
        DoubleLinkedList<K,V> newList = countMap.get(node.count);
        newList.addHead(node);
    }


    @Override
    public void set(K key, V val) {
        Node<K,V> node;
        if (map.containsKey(key)) {
            node = map.get(key);
            node.value = val;
            handle(node, false);
        } else {
            node = new Node<>(key, val);
            //容量超出，则删除全局最小频次对应双向链表中的尾部结点
            if (map.size() >= capacity) {
                DoubleLinkedList<K,V> oldList = countMap.get(min);
                Node<K,V> tail = oldList.delTail();
                map.remove(tail.key);
            }
            map.put(key, node);
            handle(node, true);
        }

    }
    public class DoubleLinkedList<K,V> {
        int size;
        Node<K,V> head;
        Node<K,V> tail;

        public DoubleLinkedList() {
            this.size = 0;
            this.head = new Node<>();
            this.tail = new Node<>();
            this.head.next = tail;
            this.tail.prev = head;
        }

        void addHead(Node<K,V> node) {
            node.next = head.next;
            head.next.prev = node;
            node.prev = head;
            head.next = node;
            size++;
        }

        void delNode(Node<K,V> node) {
            Node<K,V> prev = node.prev;
            Node<K,V> next = node.next;
            prev.next = next;
            next.prev = prev;
            size--;
        }


        Node<K,V> delTail() {
            Node<K,V> node = this.tail.prev;
            node.prev.next = this.tail;
            this.tail.prev = node.prev;
            node.prev = null;
            node.next = null;
            size--;
            return node;
        }

    }
}

我们使用上面的LRU和LFU来构建ARC。

1
2
public interface IARCCache<K,V> extends Cache<K,V>{
}
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
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
public class ARCCache<K,V> implements IARCCache<K,V>{

    /**
     * 容量
     */
    private int capacity;

    private static final Object PRESENT = new Object();

    //自适应值
    private int p;

    private ARC_LRUCache<K,V> lruCache;
    private ARC_LRUCache<K,Object> lruCacheGhost;
    private ARC_LFUCache<K,V> lfuCache;
    private ARC_LFUCache<K,Object> lfuCacheGhost;


    public ARCCache(int capacity) {
        if(capacity < 1){
            throw new RuntimeException("容量不能小于1");
        }
        this.capacity = capacity;

        //LRU和LFU的淘汰我们在当前类进行控制
        //LRU、LFU、LRUGhost、LFUGhost最大只能达到capacity，
        // 我们初始化为capacity+1，这样原来的内部淘汰策略就不会触发（因为淘汰时要加入ghost，我们手动控制）
        lruCache = new ARC_LRUCache<>(capacity+1);
        lruCacheGhost = new ARC_LRUCache<>(capacity+1);
        lfuCache = new ARC_LFUCache<>(capacity+1);
        lfuCacheGhost = new ARC_LFUCache<>(capacity+1);
        p = 0;
    }

    @Override
    public V get(K key) {
        //从lru获取数据，如果存在，lru移除并将其放入LFU
        V v = lruCache.get(key);
        if(v !=null){
            lruCache.remove(key);
            lfuCache.set(key,v);
            return v;
        }
        //尝试从lfu获取数据，存在直接返回数据
        v = lfuCache.get(key);
        if(v != null){
            return v;
        }

        //都不存在，直接返回null
        return null;
    }

    @Override
    public void set(K key, V value) {

        //检查lru是否有该值，有的话移除并放入lfu
        if(lruCache.contains(key)){
            lruCache.remove(key);
            lfuCache.set(key,value);
            return;
        }

        //检查lfu是否已经有该key
        if(lfuCache.contains(key)){
            //存在更新并返回
            lfuCache.set(key, value);
            return;
        }

        //都不存在
        //查询lru ghost情况
        if(lruCacheGhost.contains(key)){
            //lru过小，需要增大p值
            //根据 lruGhost和lfuGhost比例来计算p值，delta默认1
            //如果 lfuGhost数据量 > lruGhost 数据量，说明lfu淘汰数据数据较快（命中率低），lru淘汰数据较慢（命中率高）
            //此时 delta = lfuGhostSize / lruGhostSize 大于1，也就是快速增大lru，以适应当前数据情况
            int delta = 1;
            int lruGhostSize = lruCacheGhost.size();
            int lfuGhostSize = lfuCacheGhost.size();
            if(lfuGhostSize > lruGhostSize){
                delta = lfuGhostSize / lruGhostSize;
            }
            if(p+delta >= capacity){
                p = capacity;
            }else{
                p += delta;
            }

            //lru和lfu容量不能超出范围
            if(lruCache.size() + lfuCache.size() >= capacity){
                //超出之后需要根据p值对lru和lfu进行调整
                replace(false);
            }
            //在lruGhost中删除
            lruCacheGhost.remove(key);
            //将数据放入lfu
            lfuCache.set(key,value);
            return;
        }

        //如果在lfuGhost中
        if(lfuCacheGhost.contains(key)){
            //lfu 过小，需要减小p值
            //根据lruGhost和lfuGhost来计算p值，delta默认1
            //如果lruGhost数据量 > lfuGhost数据量，说明lru淘汰数据比较快（命中率低），lfu淘汰数据慢（命中率高）
            //此时 delta = lruGhostSize / lfuGhostSize 大于1，也就是快速增大lfu，以适应当前情况
            int delta = 1;
            int lruGhostSize = lruCacheGhost.size();
            int lfuGhostSize = lfuCacheGhost.size();
            if(lruGhostSize > lfuGhostSize){
                delta = lruGhostSize / lfuGhostSize;
            }

            if(delta >= p){
                p = 0;
            }else{
                p -= delta;
            }

            //lru和lfu容量不能超出范围
            if(lruCache.size() + lfuCache.size() >= capacity){
                //超出之后需要根据p值对lru和lfu进行调整
                replace(true);
            }
            //在lfuGhost中删除
            lfuCacheGhost.remove(key);
            //添加至lfu
            lfuCache.set(key,value);
            return;
        }

        //lru和lfu总容量不能超过capacity
        if(lruCache.size() + lfuCache.size() >= capacity){
            replace(false);
        }

        // lruGhost 容量不能超过 capacity - p
        if(lruCacheGhost.size() > capacity - p){
            lruCacheGhost.removeEldest();
        }

        //lfuGhost容量不能超过 p
        if(lfuCacheGhost.size() > p){
            lfuCacheGhost.removeEldest();
        }

        //添加到lru
        lruCache.set(key,value);
    }

    /**
     * 用于根据P的当前学习值自适应地从lru或lfu中淘汰数据,
     * @param lfuGhostContainsKey
     */
    public void replace(boolean lfuGhostContainsKey){
        int lruSize = lruCache.size();
        if(lruSize > 0 && (lruSize > p || (lruSize == p && lfuGhostContainsKey))){
            //lru移除旧元素
            K key = lruCache.removeEldest();
            if(key != null){
                lruCacheGhost.set(key,PRESENT);
            }
        }else{
            //lfu移除旧元素
            K key = lfuCache.removeEldest();
            if(key != null){
                lfuCacheGhost.set(key,PRESENT);
            }
        }

    }
}

总结

本篇文章我们了解了一些常见的缓存淘汰算法，对其工作原理也有了简单认知，其实每一种算法都有自己的特色，但是真正在使用过程中，或多或少都会进行对应的优化。比如 Redis 会同时使用 LRU 和 LFU ，同时 LFU 为了体现时间维度特征而会主动将计数器减少等策略。

有兴趣的同学可以看下这篇关于Redis淘汰策略的文章 Redis淘汰策略 。




-------------文章结束啦 ~\(≧▽≦)/~ 感谢您的阅读-------------

您的支持就是我创作的动力！

欢迎关注我的其它发布渠道