Leetcode 146. LRU 缓存。手撕lru? 面试官让手写lru？java版本lru-白红宇

Leetcode 146. LRU 缓存。手撕lru? 面试官让手写lru？java版本lru

阅读量：794 次

发布时间：2023-01-30

本文共 2828 字，大约阅读时间需要 9 分钟。

要设计并实现一个满足约束的LRUCache类，需仔细考虑其核心功能和性能要求。以下是优化后的详细步骤和实现思路：

设计思路

问题理解与需求分析：

需要实现一个脏旧（Least Recently Used）缓存池，支持高效的数据存取和管理。-.BASELINE性能指标为O(1)的平均复杂度，get和put操作需在常数时间内完成。-.特定功能包括：初始化LRUCache、获取或插入/更新键值，对超出容量时剔除最久未使用的键。

结构设计：

哈希表（HashMap）：用于O(1)平均时间复杂度的键值存取。

双向链表：记录键的访问顺序，帮助快速识别和删除最老键。

移位机制：每次访问将键移动到链表末尾，更新访问时间。

容量管理：当插入或替换键导致容量超限时，删除链表头部节点。

优化考虑：

维护一个链表来跟踪键的使用顺序，通过移位操作保持最先使用的键在链表头部。

使用双向链表结构避免需要O(n)时间逐个移至末尾的复杂度。

实现步骤

构造函数：

初始化容量，预留空间将存储键值对。

创建一个双向链表结构，记录键的顺序更新。

maintains a counter or采用启发式替换策略（基于键的访问次数）。

get方法：

使用哈希表查找键是否存在。

如果存在，更新访问时间和链表位置，返回值。

否则，返回-1。

put方法：

检查键是否存在，存在则更新值。

如果不存在，插入键，若超出容量，移到链表末尾并删除最老键。

否则，加入链表末尾，并移位，可能触发容量超限，导致链表头部节点被移除。

代码实现

import java.util.*;public class LRUCache {    // 主要的哈希表用于存储键值对    Map
   
     cache = new HashMap<>();    // 双向链表记录每个节点的访问顺序    DoubleLinkedHashSet
    
      order = new DoubleLinkedHashSet<>();    // 双向链表辅助类，内置指针结构    static class Node {        int key;        int value;        Node prev = null;        Node next = null;    }    // 初始化LRUCache    LRUCache(int capacity) {        this.capacity = capacity;        // 初始化链表的各种结构，只需要单个虚拟节点启动    }    // 获取数据    int get(int key) {        if (cache.containsKey(key)) {            Node node = cache.get(key);            // 移到链表的末尾，记录最近使用            order.remove(node);            order.add(node);            return node.value;        } else {            return -1;        }    }    // 插入或更新数据    void put(int key, int value) {        if (cache.containsKey(key)) {            Node oldNode = cache.get(key);            order.remove(oldNode);            // 更新节点的位置            Node newNode = new Node();            newNode.key = key;            newNode.value = value;            newNode.prev = oldNode.next;            newNode.next = oldNode;            // 插入到双向链表的最后            order.add(newNode);            cache.put(key, newNode);        } else {            // 检查是否已经超出容量            if (cache.size() >= capacity) {                // 移除最旧的节点                Node oldRemoved = orderppeelFirst();                // 删除哈希表中的对应值                cache.remove(((LRUCache.Node) oldRemoved).key);                // 同时处理链表节点                oldRemoved.prev.next = null;                oldRemoved = null;            }            Node newNode = new Node();            newNode.key = key;            newNode.value = value;            newNode.prev = null;            newNode.next = order.peekLast();            // 插入到链表末尾            order.add(newNode);            cache.put(key, newNode);        }    }    // 移除链表中最旧的节点    private Node orderppeelFirst() {        return order.iterator().next();    }}