高效缓存管理：Java 实现 LRU 淘汰算法

今天药忘吃喽~ 2024-03-23 12:17 81阅读 0赞

## 1、LRU 简介 ##

LRU，全称 Least Recently Used，是一种缓存淘汰策略。在缓存中存储数据时，如果缓存满了，就需要淘汰一些数据来腾出空间。LRU算法认为最近使用频率较低的数据应该被淘汰，以此来保留热点数据，提高缓存命中率。

LRU 算法的实现方式通常是通过维护一个双向链表和一个哈希表。哈希表中存储数据的键值和对应节点在双向链表中的位置，链表的头部是最近使用的节点，尾部是最久未使用的节点。当有新的数据被访问时，先在哈希表中查找是否已存在该节点，如果存在则将节点移动到链表头部，如果不存在则新建一个节点并添加到链表头部，同时在哈希表中添加键值对。当缓存满时，将链表尾部的节点移除，同时在哈希表中删除对应的键值对。

LRU 算法的优点是实现简单，易于理解和维护，适用于多种场景，比如缓存、数据库等。缺点是在特定的场景下性能可能不如其他淘汰策略，比如 LFU 算法等。此外，LRU 算法在处理热点数据集合时可能会出现“抖动”，即数据在热点和非热点之间频繁移动，导致缓存命中率下降。针对这个问题，一些改进的 LRU 算法，比如 2Q 算法、ARC 算法等，被提出。

## 2、常见的缓存淘汰算法 ##

常见的缓存淘汰算法有以下几种：

*  先进先出（FIFO）：按照缓存中数据进入的顺序，先进先出的淘汰数据。
 *  最近最少使用（LRU）：根据缓存中数据的使用时间，最近最少使用的数据被淘汰。即最近一段时间内没有被访问的数据先被淘汰。
 *  最不经常使用（LFU）：根据缓存中数据的使用次数，使用次数最少的数据被淘汰。
 *  时间轮算法（TTL）：根据缓存中数据的存活时间（time-to-live，TTL），在数据过期后淘汰。
 *  随机算法：随机淘汰一些数据。

以上算法各有优缺点，应根据实际情况选择合适的淘汰策略。例如，FIFO算法容易实现，但是不够智能，会将一些较重要的数据误淘汰；而LRU算法智能化程度更高，但是实现复杂度相对较高。

## 3、Java 实现 LRU ##

### 3.1、定义一个双向链表节点类 ###

/**
     * <h1>定义一个双向链表节点类</h1>
     * 包含一个 key 和一个 value 属性，用于存储键值对。
     * */
    public class ListNode {
        
        public Integer key;
        
        public Object value;
    
        public ListNode prev;
    
        public ListNode next;
    
        // 构造方法
        public ListNode(int key, Object value) {
        
            this.key = key;
            this.value = value;
            this.prev = null;
            this.next = null;
        }
    }

### 3.2、定义一个双向链表类 ###

import java.util.HashMap;
    import java.util.Map;
    
    /**
     * <h1>定义一个双向链表类</h1>
     * 包含一个头节点和一个尾节点，用于存储双向链表中的数据。
     * */
    public class LRUCache {
        
        // 定义缓存容量
        private final int capacity;
        // 定义一个 HashMap 用于快速定位元素
        private final Map<Integer, ListNode> cache;
        // 定义头结点和尾节点
        private ListNode head, tail;
    
        /**
         * <h2>构造方法</h2>
         * */
        public LRUCache(int capacity) {
        
            // 初始化容量
            this.capacity = capacity;
            cache = new HashMap<>(capacity);
    
            // 初始化头结点和尾节点，并让它们相互指向
            this.head = new ListNode(-1, -1);
            this.tail = new ListNode(-1, -1);
            this.head.next = tail;
            this.tail.prev = head;
        }
    
        /**
         * <h2>将指定结点移到头结点之后</h2>
         * */
        private void moveNodeToHead(ListNode node) {
        
            // 如果 node 本来就是头结点，直接返回
            if (node == head.next) {
        
                return;
            }
            // 如果 node 不是尾节点，将 node 从双向链表中删除
            if (node.next != null && node.prev != null) {
        
                node.prev.next = node.next;
                node.next.prev = node.prev;
            }
            // 将node插入到头结点之后
            node.prev = head;
            node.next = head.next;
            head.next.prev = node;
            head.next = node;
        }
    
        /**
         * <h2>获取 key 对应的 value</h2>
         * */
        public Object getValue(int key) {
        
            // 如果 map 中没有该 key，返回-1
            if (!cache.containsKey(key)) {
        
                return -1;
            }
            // 将对应结点移到头结点之后，并返回对应 value
            ListNode node = cache.get(key);
            moveNodeToHead(node);
            return node.value;
        }
    
        /**
         * <h2>添加元素</h2>
         * */
        public void putValue(Integer key, Object value) {
        
            // 如果 key 已经存在，将对应结点移到头结点之后，更新 value
            if (cache.containsKey(key)) {
        
                ListNode node = cache.get(key);
                moveNodeToHead(node);
                node.value = value;
            }
            // 如果 key 不存在，新建一个结点，添加到头结点之后，并将其加入到 map 中
            else {
        
                ListNode newNode = new ListNode(key, value);
                cache.put(key, newNode);
                newNode.next = head.next;
                newNode.prev = head;
                head.next.prev = newNode;
                head.next = newNode;
                // 如果容量已经达到上限，将尾节点之前的结点删除
                if (cache.size() > capacity) {
        
                    ListNode lastNode = tail.prev;
                    cache.remove(lastNode.key);
                    lastNode.prev.next = tail;
                    tail.prev = lastNode.prev;
                }
            }
        }
    
        /**
         * <h2>打印 LRU 缓存信息</h2>
         * */
        public String printLog() {
        
            String result = "";
            ListNode node = this.head.next;
            while( node.next != null ) {
        
                result += node.key + " = " + node.value;
                if( node.next.key != -1) {
        
                    result += ", ";
                }
                node = node.next;
            }
            return result;
        }
    }

### 3.3、定义一个单元测试类 ###

/**
     * <h1>定义一个单元测试类</h1>
     * */
    public class LRUTest {
        
    
        public static void main(String[] args) {
        
            LRUCache lruCache = new LRUCache(5);
    
            System.out.println("初始状态：" + lruCache.printLog());
    
            lruCache.putValue(1, "V1");
            System.out.println("新增键 1：" + lruCache.printLog());
    
            lruCache.putValue(2, "V2");
            System.out.println("新增键 2：" +lruCache.printLog());
    
            lruCache.putValue(3, "V3");
            System.out.println("新增键 3：" +lruCache.printLog());
    
            lruCache.getValue(1);
            System.out.println("查询键 1：" +lruCache.printLog() + "，注意：链表数据位置变化");
    
            lruCache.putValue(4, "V4");
            System.out.println("新增键 4：" +lruCache.printLog());
    
            lruCache.putValue(5, "V5");
            System.out.println("新增键 5：" +lruCache.printLog());
    
            lruCache.getValue(4);
            System.out.println("查询键 4：" +lruCache.printLog() + "，注意：链表数据位置变化");
    
            lruCache.putValue(6, "V6");
            System.out.println("新增键 6：" +lruCache.printLog());
    
            System.out.println("最终状态：" + lruCache.printLog());
        }
    }

单元测试输出结果

初始状态：
    新增键 1：1 = V1
    新增键 2：2 = V2, 1 = V1
    新增键 3：3 = V3, 2 = V2, 1 = V1
    查询键 1：1 = V1, 3 = V3, 2 = V2，注意：链表数据位置变化
    新增键 4：4 = V4, 1 = V1, 3 = V3, 2 = V2
    新增键 5：5 = V5, 4 = V4, 1 = V1, 3 = V3, 2 = V2
    查询键 4：4 = V4, 5 = V5, 1 = V1, 3 = V3, 2 = V2，注意：链表数据位置变化
    新增键 6：6 = V6, 4 = V4, 5 = V5, 1 = V1, 3 = V3
    最终状态：6 = V6, 4 = V4, 5 = V5, 1 = V1, 3 = V3

这个实现使用了一个双向链表和一个 HashMap 来实现 LRU 缓存。HashMap 用于快速查找节点，双向链表用于维护节点顺序，从而实现 LRU 策略。

在这个实现中，LRUCache 类型的缓存具有固定的容量，当缓存达到容量限制时，最近最少使用的节点会被移除。使用 getValue 方法获取节点时，如果节点存在，它将被移动到链表的头部以表示它是最近使用的节点。使用 putValue 方法添加节点时，如果节点已存在，则它的值将被更新并移动到链表的头部。如果节点不存在，则将新节点添加到链表的头部。如果添加后缓存超出了容量限制，则最后一个节点将被删除。

这就是 LRU 算法的基本思想：缓存中数据的使用是不断变化的，而缓存大小是有限的，因此需要通过一定的淘汰策略来保证缓存中数据的有效性和及时性。

总的来说，LRU 算法是一种比较简单、高效的缓存淘汰策略，它能够快速判断出最近最少使用的数据，并及时淘汰，从而保证了缓存中数据的有效性和及时性。在实际开发中，我们可以根据具体的场景和需求，结合不同的数据结构和算法来实现 LRU 算法。

#### 本文教程到此结束，祝愿小伙伴们在编程之旅中能够愉快地探索、学习、成长！ ####