有的时候博客内容会有变动，首发博客是最新的，其他博客地址可能会未同步,认准https://blog.zysicyj.top

全网最细面试题手册，支持艾宾浩斯记忆法。这是一份最全面、最详细、最高质量的 java面试题，不建议你死记硬背，只要每天复习一遍，有个大概印象就行了。 https://store.amazingmemo.com/chapterDetail/1685324709017001`

LRU 缓存机制的实现

LRU（Least Recently Used）缓存机制是一种常见的页面置换算法，用于管理缓存中的数据。它会淘汰最长时间未被使用的数据，以便为新的数据腾出空间。要实现一个高效的LRU缓存，我们需要在O(1)时间复杂度内完成以下操作：

获取数据（get）
添加新数据（put）

使用 LinkedHashMap 实现 LRU

在Java中，可以通过LinkedHashMap来实现一个简单的LRU缓存。LinkedHashMap内部维护了一个双向链表来记录插入顺序或访问顺序，这使得它非常适合实现LRU缓存。

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

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

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

在这个实现中，我们重写了removeEldestEntry方法，当缓存大小超过容量时，它会移除最老的元素（最少使用的元素）。

使用 HashMap 和双向链表实现 LRU

为了实现O(1)的增加和删除操作，我们通常会使用HashMap结合双向链表。HashMap提供O(1)的查找速度，而双向链表可以在O(1)的时间内添加和删除节点。

数据结构定义

public class LRUCache {
    class DLinkedNode {
        int key;
        int value;
        DLinkedNode prev;
        DLinkedNode next;
    }

    private void addNode(DLinkedNode node) {
        // 添加节点的实现
    }

    private void removeNode(DLinkedNode node) {
        // 移除节点的实现
    }

    private void moveToHead(DLinkedNode node) {
        // 将节点移动到头部的实现
    }

    private DLinkedNode popTail() {
        // 移除尾部节点的实现
    }

    private Map<Integer, DLinkedNode> cache = new HashMap<>();
    private int size;
    private int capacity;
    private DLinkedNode head, tail;
}

方法实现

public LRUCache(int capacity) {
    this.size = 0;
    this.capacity = capacity;

    head = new DLinkedNode();
    tail = new DLinkedNode();

    head.next = tail;
    tail.prev = head;
}

public int get(int key) {
    DLinkedNode node = cache.get(key);
    if (node == null) return -1;

    // 移动到头部
    moveToHead(node);

    return node.value;
}

public void put(int key, int value) {
    DLinkedNode node = cache.get(key);

    if(node == null) {
        DLinkedNode newNode = new DLinkedNode();
        newNode.key = key;
        newNode.value = value;

        cache.put(key, newNode);
        addNode(newNode);

        ++size;

        if(size > capacity) {
            // 移除尾部节点
            DLinkedNode tail = popTail();
            cache.remove(tail.key);
            --size;
        }
    } else {
        // 更新值
        node.value = value;
        moveToHead(node);
    }
}

O(1) 增加和删除的实现

private void addNode(DLinkedNode node) {
    node.prev = head;
    node.next = head.next;

    head.next.prev = node;
    head.next = node;
}

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

    prev.next = next;
    next.prev = prev;
}

private void moveToHead(DLinkedNode node) {
    removeNode(node);
    addNode(node);
}

private DLinkedNode popTail() {
    DLinkedNode res = tail.prev;
    removeNode(res);
    return res;
}

不使用 HashMap 的实现

不使用HashMap的话，我们无法在O(1)时间内完成查找操作。如果使用其他数据结构（如数组或链表），查找操作的时间复杂度至少是O(n)，这将导致整个LRU缓存的效率下降。因此，在实现高效的LRU缓存时，HashMap是不可或缺的组成部分。

LRU怎么实现？怎么实现O(1)增加删除？不用Hashmap可以吗？

LRU 缓存机制的实现

使用 LinkedHashMap 实现 LRU

使用 HashMap 和双向链表实现 LRU

数据结构定义

方法实现

O(1) 增加和删除的实现

不使用 HashMap 的实现

喜欢这篇文章的人也看了

如何使用mybatis plus

mybatis pus中的常用注解

LRU怎么实现？怎么实现O(1)增加删除？不用Hashmap可以吗？

LRU 缓存机制的实现

使用 LinkedHashMap 实现 LRU

使用 HashMap 和 双向链表 实现 LRU

数据结构定义

方法实现

O(1) 增加和删除的实现

不使用 HashMap 的实现

喜欢这篇文章的人也看了

如何使用mybatis plus

mybatis pus中的常用注解

使用 HashMap 和双向链表实现 LRU