java如何实现一个LRU(最近最少使用)缓存? 要求:设计一个LRU缓存,支持get和put操作。当缓存满时,需要淘汰最近最少使用的元素。要求使用双向链表+哈希表的数据结构来实现,并保证get和put操作的时间复杂度为O(1)。

简介: java如何实现一个LRU(最近最少使用)缓存?要求:设计一个LRU缓存,支持get和put操作。当缓存满时,需要淘汰最近最少使用的元素。要求使用双向链表+哈希表的数据结构来实现,并保证get和put操作的时间复杂度为O(1)。

要实现一个LRU缓存,可以使用双向链表和哈希表。双向链表用于存储缓存中的元素,按照访问顺序进行排序;哈希表用于快速查找元素在双向链表中的位置。

以下是Java代码实现:

import java.util.HashMap;

public class LRUCache {
   
    private int capacity;
    private HashMap<Integer, Node> map;
    private Node head;
    private Node tail;

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

    public int get(int key) {
   
        if (map.containsKey(key)) {
   
            Node node = map.get(key);
            remove(node);
            add(node);
            return node.value;
        }
        return -1;
    }

    public void put(int key, int value) {
   
        if (map.containsKey(key)) {
   
            Node node = map.get(key);
            node.value = value;
            remove(node);
            add(node);
        } else {
   
            if (map.size() >= capacity) {
   
                map.remove(tail.prev.key);
                remove(tail.prev);
            }
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            add(newNode);
        }
    }

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

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

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

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

在这个实现中,LRUCache类包含一个容量为capacity的哈希表map,以及两个指向双向链表头部和尾部的节点headtailget方法首先检查哈希表中是否存在指定的键,如果存在,则将对应的节点移动到双向链表的头部,并返回其值;否则返回-1。put方法首先检查哈希表中是否已存在指定的键,如果存在,则更新对应的节点的值,并将其移动到双向链表的头部;如果不存在,则创建一个新的节点,将其添加到哈希表和双向链表的头部。当添加新节点时,需要检查当前缓存的大小是否已达到容量上限,如果达到上限,则需要从双向链表的尾部移除最近最少使用的元素(即哈希表中对应的键),并从哈希表中删除该键。

相关文章
|
4天前
|
缓存 安全 算法
Java面试题:如何通过JVM参数调整GC行为以优化应用性能?如何使用synchronized和volatile关键字解决并发问题?如何使用ConcurrentHashMap实现线程安全的缓存?
Java面试题:如何通过JVM参数调整GC行为以优化应用性能?如何使用synchronized和volatile关键字解决并发问题?如何使用ConcurrentHashMap实现线程安全的缓存?
8 0
|
5天前
【数据结构OJ题】移除链表元素
力扣题目——移除链表元素
10 2
【数据结构OJ题】移除链表元素
|
5天前
【数据结构OJ题】链表中倒数第k个结点
牛客题目——链表中倒数第k个结点
9 1
【数据结构OJ题】链表中倒数第k个结点
|
7天前
|
缓存 NoSQL API
分享大厂对于缓存操作的封装
作者shigen分享了关于Redis缓存的封装,以避免常见问题如穿透、击穿、雪崩。封装包括四个文件:CacheEnum、CacheLoader、CacheService和CacheServiceImpl。CacheEnum用于统一管理缓存名和过期时间,CacheService定义缓存操作接口,CacheServiceImpl是实现类,使用Semaphore解决缓存击穿问题。
11 1
分享大厂对于缓存操作的封装
|
2天前
【数据结构OJ题】链表分割
牛客题目——链表分割
3 0
【数据结构OJ题】链表分割
|
3天前
【数据结构OJ题】链表的回文结构
牛客题目——链表的回文结构
5 0
【数据结构OJ题】链表的回文结构
|
5天前
【数据结构OJ题】链表的中间结点
力扣题目——链表的中间结点
9 0
【数据结构OJ题】链表的中间结点
|
9天前
|
缓存 NoSQL Java
实现Java应用的智能缓存管理策略
实现Java应用的智能缓存管理策略
|
9天前
|
存储 缓存 NoSQL
Java中的内存数据库与缓存技术
Java中的内存数据库与缓存技术
|
13天前
|
存储 缓存 Java
Java中缓存实现的最佳实践
Java中缓存实现的最佳实践