博客快捷键

按住 Shift 键查看可用快捷键

ShiftK

开启/关闭快捷键功能

ShiftA

打开/关闭中控台

ShiftD

深色/浅色显示模式

ShiftS

站内搜索

ShiftR

随机访问

ShiftH

返回首页

ShiftL

友链页面

ShiftP

关于本站

ShiftI

原版/本站右键菜单

松开 Shift 键或点击外部区域关闭

文章详情

互动

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

8125分钟2024-01-054江苏南京0

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

小朱

生活明朗，万物可爱

本文是原创文章，采用 CC BY-NC-SA 4.0 协议，完整转载请注明来自小朱

Java263 HashMap6 LRU缓存1 算法实现1 双向链表1

喜欢这篇文章的人也看了

随便逛逛

如何使用mybatis plus

mybatis pus中的常用注解

隐私政策

评论内容

0/500

昵称

邮箱

网址

滚动到此处加载评论...

安知鱼

来自安知鱼最新设计与科技的文章

查看全部

文章详情

互动

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

8125分钟2024-01-054江苏南京0

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

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

LRU 缓存机制的实现

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

使用 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 的实现

小朱

生活明朗，万物可爱

本文是原创文章，采用 CC BY-NC-SA 4.0 协议，完整转载请注明来自小朱

Java263 HashMap6 LRU缓存1 算法实现1 双向链表1

喜欢这篇文章的人也看了

随便逛逛

如何使用mybatis plus

mybatis pus中的常用注解

隐私政策

评论内容

0/500

昵称

邮箱

网址

滚动到此处加载评论...

安知鱼

来自安知鱼最新设计与科技的文章

查看全部

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

使用 HashMap 和双向链表实现 LRU