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

有的时候博客内容会有变动,首发博客是最新的,其他博客地址可能会未同步,认准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是不可或缺的组成部分。

最后更新于