0146. LRU 缓存【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 哈希表 + 双向链表
• 3. 🔗 引用

1. 📝 题目描述

• leetcode

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value。如果插入操作导致关键字数量超过 capacity，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

---

提示：

• 1 <= capacity <= 3000
• 0 <= key <= 10000
• 0 <= value <= 10^5
• 最多调用 2 * 10^5 次 get 和 put

2. 🎯 s.1 - 哈希表 + 双向链表

c

// 双向链表节点
typedef struct DLinkedNode {
    int key, val;
    struct DLinkedNode* prev;
    struct DLinkedNode* next;
} DLinkedNode;

// 哈希表条目
typedef struct HashEntry {
    int key;
    DLinkedNode* node;
    struct HashEntry* next; // 链地址法解冲突
} HashEntry;

#define HASH_SIZE 1024

typedef struct {
    int capacity;
    int size;
    DLinkedNode* head; // 哨兵头
    DLinkedNode* tail; // 哨兵尾
    HashEntry* table[HASH_SIZE];
} LRUCache;

int hashKey(int key) {
    return ((key % HASH_SIZE) + HASH_SIZE) % HASH_SIZE;
}

DLinkedNode* hashGet(LRUCache* cache, int key) {
    int h = hashKey(key);
    HashEntry* e = cache->table[h];
    while (e) {
        if (e->key == key) return e->node;
        e = e->next;
    }
    return NULL;
}

void hashPut(LRUCache* cache, int key, DLinkedNode* node) {
    int h = hashKey(key);
    HashEntry* e = (HashEntry*)malloc(sizeof(HashEntry));
    e->key = key;
    e->node = node;
    e->next = cache->table[h];
    cache->table[h] = e;
}

void hashRemove(LRUCache* cache, int key) {
    int h = hashKey(key);
    HashEntry* e = cache->table[h];
    HashEntry* prev = NULL;
    while (e) {
        if (e->key == key) {
            if (prev) prev->next = e->next;
            else cache->table[h] = e->next;
            free(e);
            return;
        }
        prev = e;
        e = e->next;
    }
}

void removeNode(DLinkedNode* node) {
    node->prev->next = node->next;
    node->next->prev = node->prev;
}

void addToHead(LRUCache* cache, DLinkedNode* node) {
    node->prev = cache->head;
    node->next = cache->head->next;
    cache->head->next->prev = node;
    cache->head->next = node;
}

LRUCache* lRUCacheCreate(int capacity) {
    LRUCache* cache = (LRUCache*)calloc(1, sizeof(LRUCache));
    cache->capacity = capacity;
    cache->head = (DLinkedNode*)malloc(sizeof(DLinkedNode));
    cache->tail = (DLinkedNode*)malloc(sizeof(DLinkedNode));
    cache->head->next = cache->tail;
    cache->tail->prev = cache->head;
    return cache;
}

int lRUCacheGet(LRUCache* obj, int key) {
    DLinkedNode* node = hashGet(obj, key);
    if (!node) return -1;
    removeNode(node);
    addToHead(obj, node);
    return node->val;
}

void lRUCachePut(LRUCache* obj, int key, int value) {
    DLinkedNode* node = hashGet(obj, key);
    if (node) {
        node->val = value;
        removeNode(node);
        addToHead(obj, node);
    } else {
        node = (DLinkedNode*)malloc(sizeof(DLinkedNode));
        node->key = key;
        node->val = value;
        hashPut(obj, key, node);
        addToHead(obj, node);
        obj->size++;
        if (obj->size > obj->capacity) {
            DLinkedNode* tail = obj->tail->prev;
            removeNode(tail);
            hashRemove(obj, tail->key);
            free(tail);
            obj->size--;
        }
    }
}

void lRUCacheFree(LRUCache* obj) {
    DLinkedNode* cur = obj->head;
    while (cur) {
        DLinkedNode* next = cur->next;
        free(cur);
        cur = next;
    }
    for (int i = 0; i < HASH_SIZE; i++) {
        HashEntry* e = obj->table[i];
        while (e) {
            HashEntry* next = e->next;
            free(e);
            e = next;
        }
    }
    free(obj);
}

js

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
  this.capacity = capacity
  this.map = new Map()
}

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
  if (!this.map.has(key)) return -1
  const val = this.map.get(key)
  // 删除后重新插入，保证最近使用的在最后
  this.map.delete(key)
  this.map.set(key, val)
  return val
}

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
  if (this.map.has(key)) {
    this.map.delete(key)
  }
  this.map.set(key, value)
  if (this.map.size > this.capacity) {
    // 删除最早插入的（Map 迭代顺序即插入顺序）
    const firstKey = this.map.keys().next().value
    this.map.delete(firstKey)
  }
}

py

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

• 时间复杂度：$O(1)$，get 和 put 操作均为常数时间
• 空间复杂度：$O(capacity)$，哈希表和双向链表最多存储 capacity 个元素

算法思路：

• 哈希表实现 $O(1)$ 查找，双向链表实现 $O(1)$ 的插入和删除
• 每次访问或更新时，将节点移到链表头部
• 容量满时删除链表尾部的节点（最久未使用）
• JS 版本利用 Map 的插入顺序特性简化实现，Python 版本使用 OrderedDict

3. 🔗 引用

• LRU (最近最少使用) 缓存
  • 百度百科