LRU 缓存机制

题目要求

设计一个数据结构，它能够满足最近最少使用（LRU）缓存的要求。这个数据结构应该支持以下操作：

1. LRUCache(int capacity)：通过给定的正整数容量capacity初始化 LRU 缓存。
2. int get(int key)：如果缓存中存在键key，则返回其对应的值；如果不存在，则返回-1。
3. void put(int key, int value)：如果键key已经存在，则更新其对应的值value；如果不存在，则将键值对key-value插入缓存。如果插入新的键值对导致缓存项的数量超过了capacity，则需要按照 LRU 策略移除最久未使用的键值对。

这两个函数get和put的平均时间复杂度必须是 O(1)。

解题思路

为了满足题目要求，我们需要使用一种能够快速插入、删除和更新元素的数据结构，同时还要能够快速访问到每个元素。考虑到这些需求，我们可以使用哈希表和双向链表的组合来实现 LRU 缓存。

哈希表

哈希表支持平均时间复杂度为 O(1)的元素查找，这使得我们能够快速判断一个元素是否存在于缓存中，以及快速访问到该元素。

双向链表

双向链表支持 O(1)时间复杂度的元素添加、删除操作。通过维护一个双向链表，我们可以保证插入的元素总是在链表的头部，而每次访问元素时，我们可以将其移动到链表头部，这样就能保证链表尾部始终是最久未使用的元素。

LRU 缓存的实现

1. 初始化：创建一个哈希表和一个双向链表。哈希表用于存储键和其在双向链表中对应节点的地址，双向链表中的每个节点包含键值对。

2. 获取元素 (get操作)：

   • 如果键存在于哈希表中，则返回对应节点的值，并将该节点移动到双向链表的头部。
   • 如果键不存在，返回-1。

3. 插入/更新元素 (put操作)：

   • 如果键已存在于哈希表中，更新对应节点的值，并将该节点移动到双向链表的头部。
   • 如果键不存在：
     • 如果当前缓存未满，直接在双向链表头部插入新节点，并在哈希表中添加键和地址的映射。
     • 如果当前缓存已满，删除双向链表尾部节点，并移除哈希表中对应的映射，然后在双向链表头部插入新节点，并在哈希表中添加键和地址的映射。

通过以上步骤，我们可以确保get和put操作都能在 O(1)的时间复杂度内完成，满足 LRU 缓存的要求。

Golang 版本

package main

import (
	"container/list"
)

type LRUCache struct {
	capacity int
	cache    map[int]*list.Element
	list     *list.List
}

type Pair struct {
	key   int
	value int
}

func Constructor(capacity int) LRUCache {
	return LRUCache{
		capacity: capacity,
		cache:    make(map[int]*list.Element),
		list:     list.New(),
	}
}

func (this *LRUCache) Get(key int) int {
	if element, found := this.cache[key]; found {
		this.list.MoveToFront(element)
		return element.Value.(Pair).value
	}
	return -1
}

func (this *LRUCache) Put(key int, value int) {
	if element, found := this.cache[key]; found {
		this.list.MoveToFront(element)
		element.Value = Pair{key, value}
	} else {
		if this.list.Len() == this.capacity {
			oldest := this.list.Back()
			delete(this.cache, oldest.Value.(Pair).key)
			this.list.Remove(oldest)
		}
		this.cache[key] = this.list.PushFront(Pair{key, value})
	}
}

func main() {
	// Example of usage:
	// cache := Constructor(2)
	// cache.Put(1, 1)
	// cache.Put(2, 2)
	// fmt.Println(cache.Get(1)) // returns 1
	// cache.Put(3, 3)           // evicts key 2
	// fmt.Println(cache.Get(2)) // returns -1 (not found)
	// cache.Put(4, 4)           // evicts key 1
	// fmt.Println(cache.Get(1)) // returns -1 (not found)
	// fmt.Println(cache.Get(3)) // returns 3
	// fmt.Println(cache.Get(4)) // returns 4
}

这段代码定义了一个LRUCache结构体，它包含一个整数型的capacity表示缓存的容量，一个映射cache用于存储键和对应链表节点的指针，以及一个list表示双向链表。Pair结构体用于存储键值对。

Constructor函数用于初始化一个LRUCache实例。Get和Put方法分别用于获取和添加键值对到缓存中，同时维护 LRU 顺序。如果缓存已满，Put方法会移除最久未使用的元素。

在main函数中，你可以按照注释中的示例来使用这个 LRUCache 类。

C++版本

#include <unordered_map>
#include <list>
#include <utility>

class LRUCache {
public:
    LRUCache(int capacity) : _capacity(capacity) {}

    int get(int key) {
        auto it = _cache.find(key);
        if (it == _cache.end()) {
            return -1;
        }
        // Move the accessed item to the front of the list (head)
        _items.splice(_items.begin(), _items, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = _cache.find(key);
        if (it != _cache.end()) {
            // Update the value
            it->second->second = value;
            // Move the updated item to the front of the list (head)
            _items.splice(_items.begin(), _items, it->second);
            return;
        }

        if (_cache.size() == _capacity) {
            // Remove the least recently used item
            auto last = _items.end();
            last--;
            _cache.erase(last->first);
            _items.pop_back();
        }

        // Insert the new item at the front of the list (head)
        _items.push_front(std::make_pair(key, value));
        _cache[key] = _items.begin();
    }

private:
    int _capacity;
    std::list<std::pair<int, int>> _items; // Pair of key and value
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> _cache; // Map to store key and iterator to the list node
};

int main() {
    // Example of usage:
    // LRUCache cache(2);
    // cache.put(1, 1);
    // cache.put(2, 2);
    // std::cout << cache.get(1) << std::endl; // returns 1
    // cache.put(3, 3); // evicts key 2
    // std::cout << cache.get(2) << std::endl; // returns -1 (not found)
    // cache.put(4, 4); // evicts key 1
    // std::cout << cache.get(1) << std::endl; // returns -1 (not found)
    // std::cout << cache.get(3) << std::endl; // returns 3
    // std::cout << cache.get(4) << std::endl; // returns 4
    return 0;
}

这段 C++代码实现了一个 LRUCache 类，它使用一个std::list来存储键值对，并使用一个std::unordered_map来快速定位这些键值对在列表中的位置。get方法用于获取键对应的值，如果键存在于缓存中，则将其移动到列表的前端。put方法用于插入或更新键值对，如果键已存在，则更新其值并移动到列表前端；如果键不存在，则插入新的键值对到前端，如果此时缓存已满，则会移除最后端的键值对。这样可以确保最近最少使用的元素总是在列表的尾部，从而实现 LRU 缓存淘汰策略。

Python 版本

from collections import OrderedDict

class LRUCache:

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

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        else:
            self.cache.move_to_end(key)  # Move the key to the end to show that it was recently used
            return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)  # Move the key to the end to show that it was recently used
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)  # Pop the first item (least recently used)

# Example of usage:
# cache = LRUCache(2)
# cache.put(1, 1)
# cache.put(2, 2)
# print(cache.get(1))       # returns 1
# cache.put(3, 3)           # evicts key 2
# print(cache.get(2))       # returns -1 (not found)
# cache.put(4, 4)           # evicts key 1
# print(cache.get(1))       # returns -1 (not found)
# print(cache.get(3))       # returns 3
# print(cache.get(4))       # returns 4

这段 Python 代码使用了collections.OrderedDict来实现 LRU 缓存。OrderedDict记住了元素插入的顺序，因此可以用来实现 LRU（最近最少使用）缓存。当一个元素被访问时，它会被移动到OrderedDict的末尾，表示这个元素是最近被使用过的。当缓存超出容量时，OrderedDict的第一个元素（即最久未使用的元素）会被移除。

Java 版本

import java.util.HashMap;

public class LRUCache {

    private HashMap<Integer, Node> map;
    private DoubleList cache;
    private int capacity;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        int val = map.get(key).val;
        // 利用 put 方法把该数据提前
        put(key, val);
        return val;
    }

    public void put(int key, int value) {
        // 先把新节点 x 做出来
        Node x = new Node(key, value);

        if (map.containsKey(key)) {
            // 删除旧的节点，新的插到头部
            cache.remove(map.get(key));
            cache.addFirst(x);
            // 更新 map 中对应的数据
            map.put(key, x);
        } else {
            if (capacity == cache.size()) {
                // 删除链表最后一个数据
                Node last = cache.removeLast();
                map.remove(last.key);
            }
            // 直接添加到头部
            cache.addFirst(x);
            map.put(key, x);
        }
    }

    private class Node {
        public int key, val;
        public Node next, prev;
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }

    private class DoubleList {
        private Node head, tail; // 头尾虚节点
        private int size; // 链表元素数

        public DoubleList() {
            // 初始化双向链表的数据
            head = new Node(0, 0);
            tail = new Node(0, 0);
            head.next = tail;
            tail.prev = head;
            size = 0;
        }

        // 在链表头部添加节点 x，时间 O(1)
        public void addFirst(Node x) {
            x.next = head.next;
            x.prev = head;
            head.next.prev = x;
            head.next = x;
            size++;
        }

        // 删除链表中的 x 节点（x 一定存在）
        // 由于是双链表且给的是目标 Node 节点，时间 O(1)
        public void remove(Node x) {
            x.prev.next = x.next;
            x.next.prev = x.prev;
            size--;
        }

        // 删除链表中最后一个节点，并返回该节点，时间 O(1)
        public Node removeLast() {
            if (tail.prev == head)
                return null;
            Node last = tail.prev;
            remove(last);
            return last;
        }

        // 返回链表长度，时间 O(1)
        public int size() { return size; }
    }
}

// Example of usage:
// LRUCache cache = new LRUCache(2);
// cache.put(1, 1);
// cache.put(2, 2);
// System.out.println(cache.get(1));       // returns 1
// cache.put(3, 3);                        // evicts key 2
// System.out.println(cache.get(2));       // returns -1 (not found)
// cache.put(4, 4);                        // evicts key 1
// System.out.println(cache.get(1));       // returns -1 (not found)
// System.out.println(cache.get(3));       // returns 3
// System.out.println(cache.get(4));       // returns 4

这段 Java 代码实现了一个 LRUCache 类，它包含一个内部的 Node 类来表示双向链表的节点，以及一个内部的 DoubleList 类来表示双向链表。LRUCache 使用一个 HashMap 来存储键和对应节点的映射，以及一个 DoubleList 来实现 O(1)时间复杂度的节点添加和删除。当访问或添加一个元素时，如果元素已存在，它会被移动到双向链表的头部；如果元素不存在，它会被添加到头部，如果此时缓存已满，则会从链表尾部移除最久未使用的元素。

Rust 版本

use std::collections::HashMap;

struct LRUCache {
    capacity: usize,
    cache: HashMap<i32, Box<DLinkedNode>>,
    head: Box<DLinkedNode>,
    tail: Box<DLinkedNode>,
    size: usize,
}

struct DLinkedNode {
    key: i32,
    value: i32,
    prev: Option<i32>,
    next: Option<i32>,
}

impl DLinkedNode {
    fn new(key: i32, value: i32) -> Self {
        DLinkedNode {
            key,
            value,
            prev: None,
            next: None,
        }
    }
}

impl LRUCache {
    fn new(capacity: usize) -> Self {
        let head = Box::new(DLinkedNode::new(-1, -1));
        let tail = Box::new(DLinkedNode::new(-1, -1));
        let mut lru = LRUCache {
            capacity,
            cache: HashMap::with_capacity(capacity),
            head,
            tail,
            size: 0,
        };
        lru.head.next = Some(lru.tail.key);
        lru.tail.prev = Some(lru.head.key);
        lru
    }

    fn get(&mut self, key: i32) -> i32 {
        match self.cache.get_mut(&key) {
            Some(node) => {
                self.move_to_head(node);
                node.value
            },
            None => -1,
        }
    }

    fn put(&mut self, key: i32, value: i32) {
        match self.cache.get_mut(&key) {
            Some(node) => {
                node.value = value;
                self.move_to_head(node);
            },
            None => {
                let mut node = Box::new(DLinkedNode::new(key, value));
                self.cache.insert(key, node);
                self.add_node(&mut node);
                self.size += 1;
                if self.size > self.capacity {
                    let tail = self.pop_tail();
                    self.cache.remove(&tail.key);
                    self.size -= 1;
                }
            },
        }
    }

    fn add_node(&mut self, node: &mut Box<DLinkedNode>) {
        node.prev = Some(self.head.key);
        node.next = self.head.next;

        if let Some(next_key) = self.head.next {
            if let Some(next_node) = self.cache.get_mut(&next_key) {
                next_node.prev = Some(node.key);
            }
        }

        self.head.next = Some(node.key);
    }

    fn remove_node(&mut self, node: &Box<DLinkedNode>) {
        if let Some(prev_key) = node.prev {
            if let Some(prev_node) = self.cache.get_mut(&prev_key) {
                prev_node.next = node.next;
            }
        }

        if let Some(next_key) = node.next {
            if let Some(next_node) = self.cache.get_mut(&next_key) {
                next_node.prev = node.prev;
            }
        }
    }

    fn move_to_head(&mut self, node: &mut Box<DLinkedNode>) {
        self.remove_node(node);
        self.add_node(node);
    }

    fn pop_tail(&mut self) -> Box<DLinkedNode> {
        let tail_key = self.tail.prev.unwrap();
        let mut tail_node = self.cache.remove(&tail_key).unwrap();
        self.remove_node(&tail_node);
        tail_node
    }
}

fn main() {
    let mut cache = LRUCache::new(2);
    cache.put(1, 1);
    cache.put(2, 2);
    println!("{}", cache.get(1)); // returns 1
    cache.put(3, 3); // evicts key 2
    println!("{}", cache.get(2)); // returns -1 (not found)
    cache.put(4, 4); // evicts key 1
    println!("{}", cache.get(1)); // returns -1 (not found)
    println!("{}", cache.get(3)); // returns 3
    println!("{}", cache.get(4)); // returns 4
}

这段 Rust 代码实现了一个 LRUCache 结构体，它包含一个 HashMap 来存储键和对应的双向链表节点，以及两个哨兵节点 head 和 tail 来标记双向链表的边界。LRUCache 支持 get 和 put 操作，它们都能在 O(1)时间复杂度内完成。当一个节点被访问或添加时，它会被移动到双向链表的头部。如果在添加一个新节点时超出了容量，它会从链表的尾部移除最不常用的节点。

总结

上面给出了使用哈希表和双向链表实现 LRU 缓存的代码。这种实现方式能够满足 LRU 缓存的要求，包括在 O(1)时间复杂度内完成 get 和 put 操作，并且能够按照 LRU 策略移除最久未使用的键值对。

具体实现包括以下几个关键点：

1. 使用哈希表存储键值对，以支持 O(1)时间复杂度的元素查找和访问。
2. 使用双向链表来维护键值对的顺序，确保最近访问的元素总是在链表头部，而最久未使用的元素总是在链表尾部。
3. 在 get 操作中，如果元素存在，则将其移动到链表头部；在 put 操作中，如果元素存在则更新其值并移动到链表头部，如果不存在则插入新的键值对并检查是否需要移除最久未使用的元素。

这种实现方式能够高效地满足 LRU 缓存的要求，并且在实际应用中被广泛使用。