java_LRU_0">java 基于冷热数据分离的思想设计LRU链表

1. LRUCache 伪代码

java">import java.util.HashMap;
import java.util.Map;

public class LRUCache {
    private final int capacity; // 缓存的最大容量
    private final Map<Integer, Node> map; // 用于快速查找节点的哈希表
    private final Node headHot, tailHot; // 热数据链表的头节点和尾节点
    private final Node headCold, tailCold; // 冷数据链表的头节点和尾节点
    private int hotSize, coldSize; // 热数据和冷数据的数量

    public LRUCache(int capacity) {
        this.capacity = capacity; // 初始化缓存容量
        this.map = new HashMap<>(); // 初始化哈希表
        this.headHot = new Node(0, 0); // 初始化热数据链表的头节点
        this.tailHot = new Node(0, 0); // 初始化热数据链表的尾节点
        this.headCold = new Node(0, 0); // 初始化冷数据链表的头节点
        this.tailCold = new Node(0, 0); // 初始化冷数据链表的尾节点
        headHot.next = tailHot; // 将头节点和尾节点连接起来
        tailHot.prev = headHot;
        headCold.next = tailCold; // 将头节点和尾节点连接起来
        tailCold.prev = headCold;
        this.hotSize = 0; // 初始化热数据数量为0
        this.coldSize = 0; // 初始化冷数据数量为0
    }

    public int get(int key) {
        Node node = map.get(key); // 从哈希表中查找节点
        if (node == null) return -1; // 如果节点不存在，返回-1
        if (node.isHot) {
            // 如果节点是热数据，将其移动到热数据链表头部
            removeNode(node);
            addToHeadHot(node);
        } else {
            // 如果节点是冷数据，将其移动到冷数据链表头部
            removeNode(node);
            addToHeadCold(node);
            // 如果冷数据链表的大小超过容量的一半，移除最久未使用的冷数据
            if (coldSize > capacity / 2) {
                Node lruCold = tailCold.prev;
                removeNode(lruCold);
                map.remove(lruCold.key);
                coldSize--;
                // 如果热数据链表的大小小于容量的一半，将最久未使用的冷数据提升为热数据
                if (hotSize < capacity / 2) {
                    addToHeadHot(lruCold);
                    lruCold.isHot = true;
                    hotSize++;
                }
            }
        }
        return node.value; // 返回节点的值
    }

    public void put(int key, int value) {
        if (capacity == 0) return; // 如果缓存容量为0，直接返回
        Node node = map.get(key); // 从哈希表中查找节点
        if (node != null) {
            // 如果节点存在，更新其值
            node.value = value;
            if (node.isHot) {
                // 如果节点是热数据，将其移动到热数据链表头部
                removeNode(node);
                addToHeadHot(node);
            } else {
                // 如果节点是冷数据，将其移动到冷数据链表头部
                removeNode(node);
                addToHeadCold(node);
                // 如果冷数据链表的大小超过容量的一半，移除最久未使用的冷数据
                if (coldSize > capacity / 2) {
                    Node lruCold = tailCold.prev;
                    removeNode(lruCold);
                    map.remove(lruCold.key);
                    coldSize--;
                    // 如果热数据链表的大小小于容量的一半，将最久未使用的冷数据提升为热数据
                    if (hotSize < capacity / 2) {
                        addToHeadHot(lruCold);
                        lruCold.isHot = true;
                        hotSize++;
                    }
                }
            }
        } else {
            // 如果节点不存在，创建新节点
            if (hotSize + coldSize >= capacity) {
                // 如果缓存已满，移除最久未使用的节点
                if (coldSize > capacity / 2) {
                    Node lruCold = tailCold.prev;
                    removeNode(lruCold);
                    map.remove(lruCold.key);
                    coldSize--;
                } else {
                    Node lruHot = tailHot.prev;
                    removeNode(lruHot);
                    map.remove(lruHot.key);
                    hotSize--;
                }
            }
            Node newNode = new Node(key, value); // 创建新节点
            addToHeadHot(newNode); // 将新节点插入到热数据链表头部
            map.put(key, newNode); // 将新节点添加到哈希表中
            hotSize++; // 更新热数据数量
        }
    }

    private void addToHeadHot(Node node) {
        node.isHot = true; // 设置节点为热数据
        node.prev = headHot; // 将节点插入到热数据链表头部
        node.next = headHot.next;
        headHot.next.prev = node;
        headHot.next = node;
        hotSize++; // 更新热数据数量
    }

    private void addToHeadCold(Node node) {
        node.isHot = false; // 设置节点为冷数据
        node.prev = headCold; // 将节点插入到冷数据链表头部
        node.next = headCold.next;
        headCold.next.prev = node;
        headCold.next = node;
        coldSize++; // 更新冷数据数量
    }

    private void removeNode(Node node) {
        if (node.isHot) {
            hotSize--; // 如果节点是热数据，更新热数据数量
        } else {
            coldSize--; // 如果节点是冷数据，更新冷数据数量
        }
        node.prev.next = node.next; // 从链表中移除节点
        node.next.prev = node.prev;
    }

    private static class Node {
        int key; // 节点的键
        int value; // 节点的值
        boolean isHot; // 节点是否为热数据
        Node prev; // 前驱节点
        Node next; // 后继节点

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

说明
数据结构:
使用双向链表来存储热数据和冷数据。
使用哈希表来快速查找节点。
操作:
get(int key): 如果节点存在且是热数据，则将其移动到热数据链表头部；如果是冷数据，则将其移动到冷数据链表头部，并根据冷数据链表的大小决定是否将其提升为热数据。
put(int key, int value): 如果节点存在，则更新其值并根据其状态移动到相应链表的头部；如果节点不存在，则创建新节点并插入到热数据链表头部，同时根据缓存容量决定是否需要移除最久未使用的节点。
冷热数据分离:
通过维护两个链表分别存储热数据和冷数据，可以有效地分离冷热数据。
当冷数据链表的大小超过缓存容量的一半时，会将最久未使用的冷数据移除，并根据热数据链表的大小决定是否将其提升为热数据。
这种设计可以提高缓存的命中率和访问速度，特别是在访问模式存在明显冷热数据分离的情况下。

2. LRU 的单元测试

java">import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;

import static org.junit.jupiter.api.Assertions.*;

public class LRUCacheTest {
    
    private LRUCache cache;

    @BeforeEach
    public void setUp() {
        cache = new LRUCache(3); // 初始化缓存容量为3
    }

    @Test
    public void testPutAndGet() {
        cache.put(1, 1);
        cache.put(2, 2);
        cache.put(3, 3);

        assertEquals(1, cache.get(1)); // 测试正常获取
        assertEquals(2, cache.get(2)); // 测试正常获取
        assertEquals(3, cache.get(3)); // 测试正常获取
    }

    @Test
    public void testEviction() {
        cache.put(1, 1);
        cache.put(2, 2);
        cache.put(3, 3);
        cache.put(4, 4); // 触发淘汰

        assertEquals(-1, cache.get(1)); // 测试淘汰最久未使用的元素
        assertEquals(2, cache.get(2)); // 测试正常获取
        assertEquals(3, cache.get(3)); // 测试正常获取
        assertEquals(4, cache.get(4)); // 测试正常获取
    }

    @Test
    public void testUpdate() {
        cache.put(1, 1);
        cache.put(2, 2);
        cache.put(1, 10); // 更新值

        assertEquals(10, cache.get(1)); // 测试更新后的值
        assertEquals(2, cache.get(2)); // 测试未更新的值
    }

    @Test
    public void testGetUpdatesOrder() {
        cache.put(1, 1);
        cache.put(2, 2);
        cache.put(3, 3);
        cache.get(1); // 访问1，变为最近使用

        cache.put(4, 4); // 触发淘汰

        assertEquals(1, cache.get(1)); // 测试正常获取
        assertEquals(-1, cache.get(2)); // 测试淘汰最久未使用的元素
        assertEquals(3, cache.get(3)); // 测试正常获取
        assertEquals(4, cache.get(4)); // 测试正常获取
    }

    @Test
    public void testCapacityZero() {
        LRUCache zeroCapacityCache = new LRUCache(0);
        zeroCapacityCache.put(1, 1);
        assertEquals(-1, zeroCapacityCache.get(1)); // 测试容量为0时无法存储元素
    }

    @Test
    public void testColdToHot() {
        cache.put(1, 1);
        cache.put(2, 2);
        cache.put(3, 3);
        cache.get(1); // 访问1，变为最近使用
        cache.get(2); // 访问2，变为最近使用
        cache.get(3); // 访问3，变为最近使用

        cache.put(4, 4); // 触发淘汰
        cache.put(5, 5); // 触发淘汰

        assertEquals(1, cache.get(1)); // 测试正常获取
        assertEquals(2, cache.get(2)); // 测试正常获取
        assertEquals(3, cache.get(3)); // 测试正常获取
        assertEquals(-1, cache.get(4)); // 测试淘汰最久未使用的元素
        assertEquals(5, cache.get(5)); // 测试正常获取
    }

    @Test
    public void testHotToCold() {
        cache.put(1, 1);
        cache.put(2, 2);
        cache.put(3, 3);
        cache.get(1); // 访问1，变为最近使用
        cache.get(2); // 访问2，变为最近使用
        cache.get(3); // 访问3，变为最近使用

        cache.put(4, 4); // 触发淘汰
        cache.get(1); // 访问1，变为最近使用
        cache.get(2); // 访问2，变为最近使用

        cache.put(5, 5); // 触发淘汰

        assertEquals(1, cache.get(1)); // 测试正常获取
        assertEquals(2, cache.get(2)); // 测试正常获取
        assertEquals(-1, cache.get(3)); // 测试淘汰最久未使用的元素
        assertEquals(4, cache.get(4)); // 测试正常获取
        assertEquals(5, cache.get(5)); // 测试正常获取
    }
}