昨天面试被问到的缓存淘汰算法FIFO、LRU、LFU及Java实现

逃离我推掉我的手 2023-10-01 10:22 10阅读 0赞

#### 缓存淘汰算法 ####

在高并发、高性能的质量要求不断提高时，我们首先会想到的就是利用缓存予以应对。

第一次请求时把计算好的结果存放在缓存中，下次遇到同样的请求时，把之前保存在缓存中的数据直接拿来使用。

但是，缓存的空间一般都是有限，不可能把所有的结果全部保存下来。那么，当缓存空间全部被占满再有新的数据需要被保存，就要决定删除原来的哪些数据。如何做这样决定需要使用缓存淘汰算法。

常用的缓存淘汰算法有：FIFO、LRU、LFU，下面我们就逐一介绍一下。

#### FIFO ####

FIFO，First In First Out，先进先出算法。判断被存储的时间，离目前最远的数据优先被淘汰。简单地说，先存入缓存的数据，先被淘汰。

最早存入缓存的数据，其不再被使用的可能性比刚存入缓存的可能性大。建立一个FIFO队列，记录所有在缓存中的数据。当一条数据被存入缓存时，就把它插在队尾上。需要被淘汰的数据一直在队列头。这种算法只是在按线性顺序访问数据时才是理想的，否则效率不高。因为那些常被访问的数据，往往在缓存中也停留得最久，结果它们却因变“老”而不得不被淘汰出去。

FIFO算法用队列实现就可以了，这里就不做代码实现了。

#### LRU ####

LRU，Least Recently Used，最近最少使用算法。判断最近被使用的时间，目前最远的数据优先被淘汰。简单地说，LRU 的淘汰规则是基于访问时间。

如果一个数据在最近一段时间没有被使用到，那么可以认为在将来它被使用的可能性也很小。因此，当缓存空间满时，最久没有使用的数据最先被淘汰。

在Java中，其实LinkedHashMap已经实现了LRU缓存淘汰算法，需要在构造函数第三个参数传入true，表示按照时间顺序访问。可以直接继承LinkedHashMap来实现。

package one.more;
    
    import java.util.LinkedHashMap;
    import java.util.Map;
    
    public class LruCache<K, V> extends LinkedHashMap<K, V> {
        
    
        /**
         * 容量限制
         */
        private int capacity;
    
        LruCache(int capacity) {
        
            // 初始大小，0.75是装载因子，true是表示按照访问时间排序
            super(capacity, 0.75f, true);
            //缓存最大容量
            this.capacity = capacity;
        }
    
        /**
         * 重写removeEldestEntry方法，如果缓存满了，则把链表头部第一个节点和对应的数据删除。
         */
        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        
            return size() > capacity;
        }
    }

我写一个简单的程序测试一下：

package one.more;
    
    public class TestApp {
        
    
        public static void main(String[] args) {
        
            LruCache<String, String> cache = new LruCache(3);
            cache.put("keyA", "valueA");
            System.out.println("put keyA");
            System.out.println(cache);
            System.out.println("=========================");
    
            cache.put("keyB", "valueB");
            System.out.println("put keyB");
            System.out.println(cache);
            System.out.println("=========================");
    
            cache.put("keyC", "valueC");
            System.out.println("put keyC");
            System.out.println(cache);
            System.out.println("=========================");
    
            cache.get("keyA");
            System.out.println("get keyA");
            System.out.println(cache);
            System.out.println("=========================");
    
            cache.put("keyD", "valueD");
            System.out.println("put keyD");
            System.out.println(cache);
        }
    }

运行结果如下：

put keyA
    {keyA=valueA}
    =========================
    put keyB
    {keyA=valueA, keyB=valueB}
    =========================
    put keyC
    {keyA=valueA, keyB=valueB, keyC=valueC}
    =========================
    get keyA
    {keyB=valueB, keyC=valueC, keyA=valueA}
    =========================
    put keyD
    {keyC=valueC, keyA=valueA, keyD=valueD}

当然，这个不是面试官想要的，也不是我们想要的。我们可以使用双向链表和哈希表进行实现，哈希表用于存储对应的数据，双向链表用于数据被使用的时间先后顺序。

在访问数据时，如果数据已存在缓存中，则把该数据的对应节点移到链表尾部。如此操作，在链表头部的节点则是最近最少使用的数据。

当需要添加新的数据到缓存时，如果该数据已存在缓存中，则把该数据对应的节点移到链表尾部；如果不存在，则新建一个对应的节点，放到链表尾部；如果缓存满了，则把链表头部第一个节点和对应的数据删除。

package one.more;
    
    import java.util.HashMap;
    import java.util.Map;
    
    public class LruCache<K, V> {
        
    
        /**
         * 头结点
         */
        private Node head;
        /**
         * 尾结点
         */
        private Node tail;
        /**
         * 容量限制
         */
        private int capacity;
        /**
         * key和数据的映射
         */
        private Map<K, Node> map;
    
        LruCache(int capacity) {
        
            this.capacity = capacity;
            this.map = new HashMap<>();
        }
    
        public V put(K key, V value) {
        
            Node node = map.get(key);
            // 数据存在，将节点移动到队尾
            if (node != null) {
        
                V oldValue = node.value;
                //更新数据
                node.value = value;
                moveToTail(node);
                return oldValue;
            } else {
        
                Node newNode = new Node(key, value);
                // 数据不存在，判断链表是否满
                if (map.size() == capacity) {
        
                    // 如果满，则删除队首节点，更新哈希表
                    map.remove(removeHead().key);
                }
                // 放入队尾节点
                addToTail(newNode);
                map.put(key, newNode);
                return null;
            }
        }
    
        public V get(K key) {
        
            Node node = map.get(key);
            if (node != null) {
        
                moveToTail(node);
                return node.value;
            }
            return null;
        }
    
        @Override
        public String toString() {
        
            StringBuilder sb = new StringBuilder();
            sb.append("LruCache{");
            Node curr = this.head;
            while (curr != null) {
        
                if(curr != this.head){
        
                    sb.append(',').append(' ');
                }
                sb.append(curr.key);
                sb.append('=');
                sb.append(curr.value);
                curr = curr.next;
            }
            return sb.append('}').toString();
        }
    
        private void addToTail(Node newNode) {
        
            if (newNode == null) {
        
                return;
            }
            if (head == null) {
        
                head = newNode;
                tail = newNode;
            } else {
        
                //连接新节点
                tail.next = newNode;
                newNode.pre = tail;
                //更新尾节点指针为新节点
                tail = newNode;
            }
        }
    
        private void moveToTail(Node node) {
        
            if (tail == node) {
        
                return;
            }
            if (head == node) {
        
                head = node.next;
                head.pre = null;
            } else {
        
                //调整双向链表指针
                node.pre.next = node.next;
                node.next.pre = node.pre;
            }
            node.pre = tail;
            node.next = null;
            tail.next = node;
            tail = node;
        }
    
        private Node removeHead() {
        
            if (head == null) {
        
                return null;
            }
            Node res = head;
            if (head == tail) {
        
                head = null;
                tail = null;
            } else {
        
                head = res.next;
                head.pre = null;
                res.next = null;
            }
            return res;
        }
    
        class Node {
        
            K key;
            V value;
            Node pre;
            Node next;
    
            Node(K key, V value) {
        
                this.key = key;
                this.value = value;
            }
        }
    }

再次运行测试程序，结果如下：

put keyA
    LruCache{keyA=valueA}
    =========================
    put keyB
    LruCache{keyA=valueA, keyB=valueB}
    =========================
    put keyC
    LruCache{keyA=valueA, keyB=valueB, keyC=valueC}
    =========================
    get keyA
    LruCache{keyB=valueB, keyC=valueC, keyA=valueA}
    =========================
    put keyD
    LruCache{keyC=valueC, keyA=valueA, keyD=valueD}

#### LFU ####

LFU，Least Frequently Used，最不经常使用算法，在一段时间内，数据被使用次数最少的，优先被淘汰。简单地说，LFU 的淘汰规则是基于访问次数。

如果一个数据在最近一段时间很少被使用到，那么可以认为在将来它被使用的可能性也很小。因此，当空间满时，最小频率使用的数据最先被淘汰。

我们可以使用双哈希表进行实现，一个哈希表用于存储对应的数据，另一个哈希表用于存储数据被使用次数和对应的数据。

package one.more;
    
    import java.util.Comparator;
    import java.util.HashMap;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Map;
    import java.util.stream.Collectors;
    
    public class LfuCache<K, V> {
        
    
        /**
         * 容量限制
         */
        private int capacity;
    
        /**
         * 当前最小使用次数
         */
        private int minUsedCount;
    
        /**
         * key和数据的映射
         */
        private Map<K, Node> map;
        /**
         * 数据频率和对应数据组成的链表
         */
        private Map<Integer, List<Node>> usedCountMap;
    
        public LfuCache(int capacity) {
        
            this.capacity = capacity;
            this.minUsedCount = 1;
            this.map = new HashMap<>();
            this.usedCountMap = new HashMap<>();
        }
    
        public V get(K key) {
        
    
            Node node = map.get(key);
            if (node == null) {
        
                return null;
            }
            // 增加数据的访问频率
            addUsedCount(node);
            return node.value;
        }
    
        public V put(K key, V value) {
        
            Node node = map.get(key);
            if (node != null) {
        
                // 如果存在则增加该数据的访问频次
                V oldValue = node.value;
                node.value = value;
                addUsedCount(node);
                return oldValue;
            } else {
        
                // 数据不存在，判断链表是否满
                if (map.size() == capacity) {
        
                    // 如果满，则删除队首节点，更新哈希表
                    List<Node> list = usedCountMap.get(minUsedCount);
                    Node delNode = list.get(0);
                    list.remove(delNode);
                    map.remove(delNode.key);
                }
                // 新增数据并放到数据频率为1的数据链表中
                Node newNode = new Node(key, value);
                map.put(key, newNode);
                List<Node> list = usedCountMap.get(1);
                if (list == null) {
        
                    list = new LinkedList<>();
                    usedCountMap.put(1, list);
                }
    
                list.add(newNode);
                minUsedCount = 1;
                return null;
            }
        }
    
        @Override
        public String toString() {
        
            StringBuilder sb = new StringBuilder();
            sb.append("LfuCache{");
            List<Integer> usedCountList = this.usedCountMap.keySet().stream().collect(Collectors.toList());
            usedCountList.sort(Comparator.comparingInt(i -> i));
            int count = 0;
            for (int usedCount : usedCountList) {
        
                List<Node> list = this.usedCountMap.get(usedCount);
                if (list == null) {
        
                    continue;
                }
                for (Node node : list) {
        
                    if (count > 0) {
        
                        sb.append(',').append(' ');
                    }
                    sb.append(node.key);
                    sb.append('=');
                    sb.append(node.value);
                    sb.append("(UsedCount:");
                    sb.append(node.usedCount);
                    sb.append(')');
                    count++;
                }
            }
            return sb.append('}').toString();
        }
    
        private void addUsedCount(Node node) {
        
            List<Node> oldList = usedCountMap.get(node.usedCount);
            oldList.remove(node);
    
            // 更新最小数据频率
            if (minUsedCount == node.usedCount && oldList.isEmpty()) {
        
                minUsedCount++;
            }
    
            node.usedCount++;
            List<Node> set = usedCountMap.get(node.usedCount);
            if (set == null) {
        
                set = new LinkedList<>();
                usedCountMap.put(node.usedCount, set);
            }
            set.add(node);
        }
    
        class Node {
        
    
            K key;
            V value;
            int usedCount = 1;
    
            Node(K key, V value) {
        
                this.key = key;
                this.value = value;
            }
        }
    }

再次运行测试程序，结果如下：

put keyA
    LfuCache{keyA=valueA(UsedCount:1)}
    =========================
    put keyB
    LfuCache{keyA=valueA(UsedCount:1), keyB=valueB(UsedCount:1)}
    =========================
    put keyC
    LfuCache{keyA=valueA(UsedCount:1), keyB=valueB(UsedCount:1), keyC=valueC(UsedCount:1)}
    =========================
    get keyA
    LfuCache{keyB=valueB(UsedCount:1), keyC=valueC(UsedCount:1), keyA=valueA(UsedCount:2)}
    =========================
    put keyD
    LfuCache{keyC=valueC(UsedCount:1), keyD=valueD(UsedCount:1), keyA=valueA(UsedCount:2)}

#### 总结 ####

看到这里，你已经超越了大多数人！

*  FIFO，First In First Out，先进先出算法。判断被存储的时间，离目前最远的数据优先被淘汰，可以使用队列实现。
 *  LRU，Least Recently Used，最近最少使用算法。判断最近被使用的时间，目前最远的数据优先被淘汰，可以使用双向链表和哈希表实现。
 *  LFU，Least Frequently Used，最不经常使用算法，在一段时间内，数据被使用次数最少的，优先被淘汰，可以使用双哈希表实现。