Java实现LRU缓存淘汰算法的方法

什么是LRU缓存淘汰算法？

LRU（Least Recently Used）是一种基于时间局部性原理的缓存置换策略，常用于CPU缓存、数据库缓存等场景。它的核心思想是：对于长期未被使用的缓存数据，它们被淘汰的概率更大。

在实际应用中，我们通常将缓存数据存储在一个链表中，每当我们访问缓存数据时，就将该数据移动到链表的头部，这样在链表尾部的数据就是“最近最少使用”的数据，可以被优先淘汰。

如何实现LRU算法？

以下是一个基于双向链表结构实现的LRU算法示例：

1. 首先我们需要定义一个缓存结构体，其中包含缓存大小、当前使用量、头结点和尾结点：

class LRUCache {
    int size;
    int capacity;
    Map<Integer, Node> map;
    Node head, tail;

    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        map = new HashMap<>();
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.prev = head;
    }
}

1. 我们还需要定义一个Node结构体，用于存储双向链表中的数据，每个Node包含一个key和value，以及prev和next两个指针。

class Node {
    int key;
    int value;
    Node prev;
    Node next;

    public Node() {
    }

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

1. 接下来，我们定义一些辅助方法，用于将某个Node移动到链表头部、删除尾部节点并添加新节点。

private void addToHead(Node node) {
    node.prev = head;
    node.next = head.next;
    head.next.prev = node;
    head.next = node;
}

private void removeNode(Node node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
}

private Node removeTail() {
    Node node = tail.prev;
    removeNode(node);
    return node;
}

1. 最后，我们实现get和put方法，用于获取和添加缓存数据，其中get方法需要将访问的Node移动到链表头部，put方法需要判断缓存是否已满，并将新节点添加到链表头部。

public int get(int key) {
    Node node = map.get(key);
    if (node == null) {
        return -1;
    }
    removeNode(node);
    addToHead(node);
    return node.value;
}

public void put(int key, int value) {
    Node node = map.get(key);
    if (node == null) {
        node = new Node(key, value);
        map.put(key, node);
        addToHead(node);
        size++;
        if (size > capacity) {
            Node tail = removeTail();
            map.remove(tail.key);
            size--;
        }
    } else {
        node.value = value;
        removeNode(node);
        addToHead(node);
    }
}

示例说明

示例1

在本示例中，我们将使用LRU算法实现一个最近访问的页面列表。当用户访问一个页面时，需要将该页面添加到列表开头；当页面列表超过5条时，将淘汰最近最少访问的页面。

public class PageList {
    private static final int PAGE_LIMIT = 5;
    private LRUCache cache;

    public PageList() {
        cache = new LRUCache(PAGE_LIMIT);
    }

    // 用户访问页面时被调用的方法
    public void visitPage(int page) {
        String msg = "用户访问了页面 " + page;
        System.out.println(msg);
        cache.put(page, true);
        System.out.println("最近访问的页面： " + cache.map.keySet());
    }
}

我们可以通过如下测试代码来验证程序的正确性：

public static void main(String[] args) {
    PageList pageList = new PageList();
    pageList.visitPage(1);
    pageList.visitPage(2);
    pageList.visitPage(3);
    pageList.visitPage(4);
    pageList.visitPage(5);
    pageList.visitPage(6);
    pageList.visitPage(4);
}

输出结果为：

用户访问了页面 1
最近访问的页面： [1]
用户访问了页面 2
最近访问的页面： [2, 1]
用户访问了页面 3
最近访问的页面： [3, 2, 1]
用户访问了页面 4
最近访问的页面： [4, 3, 2, 1]
用户访问了页面 5
最近访问的页面： [5, 4, 3, 2, 1]
用户访问了页面 6
最近访问的页面： [6, 5, 4, 3, 2]
用户访问了页面 4
最近访问的页面： [4, 6, 5, 3, 2]

可以看出，当访问页面超过5个时，最早访问的页面被淘汰了。

示例2

在本示例中，我们将使用LRU算法实现一个简单的缓存，用于存储用户信息。当用户第一次访问缓存时，从数据库中读取数据并添加到缓存中，以后的访问都直接从缓存中读取。

public class UserCache {
    private static final int USER_LIMIT = 50;
    private LRUCache cache;

    public UserCache() {
        cache = new LRUCache(USER_LIMIT);
    }

    // 获取用户信息的方法
    public User getUser(int userId) {
        User user = cache.get(userId);
        if (user == null) {
            String sql = "SELECT * FROM user WHERE id = " + userId;
            ResultSet rs = executeQuery(sql);
            if (rs.next()) {
                user = new User(rs.getInt("id"), rs.getString("name"), rs.getInt("age"));
                cache.put(userId, user);
            }
        }
        return user;
    }

    // 执行查询的方法
    private ResultSet executeQuery(String sql) {
        // ...
    }
}

我们可以通过如下测试代码来验证程序的正确性：

public static void main(String[] args) {
    UserCache userCache = new UserCache();
    User user1 = userCache.getUser(1);
    User user2 = userCache.getUser(2);
    User user3 = userCache.getUser(3);
    User user4 = userCache.getUser(1);
    User user5 = userCache.getUser(4);
}

输出结果为：

SELECT * FROM user WHERE id = 1
SELECT * FROM user WHERE id = 2
SELECT * FROM user WHERE id = 3
SELECT * FROM user WHERE id = 4

可以看出，第一次读取用户信息时需要从数据库中读取，但是对于重复读取的用户信息，直接从缓存中读取。