面试题：Rust HashMap缓存系统的内存管理与设计权衡

高效内存利用与快速响应机制设计思路

内存分块管理：将缓存空间按一定规则分成多个小块，不同大小的数据可以分配到合适的块中，减少内存碎片。
懒惰删除：对于过期或被淘汰的数据，不立即释放内存，而是标记为无效，在后续合适时机统一回收，减少频繁内存释放带来的开销。
使用内存池：预先分配一定大小的内存池，缓存操作优先从内存池中获取内存，避免频繁系统调用分配内存。

结合HashMap实现LRU缓存淘汰策略设计

数据结构设计：
- 使用HashMap来存储缓存数据，HashMap的key为缓存数据的标识，value为实际数据以及数据的访问时间戳等相关信息。
- 使用双向链表来记录数据的访问顺序。双向链表的节点包含数据标识和数据内容，这样可以在O(1)时间内从链表中删除和移动节点。
算法设计：
- 读操作：当读取缓存数据时，先从HashMap中查找数据是否存在。如果存在，更新双向链表中对应节点的位置到链表头部（表示最近访问），并返回数据。
- 写操作：当写入新数据时，先检查缓存是否已满。如果已满，淘汰双向链表尾部的数据（最久未使用），并从HashMap中删除对应的记录。然后将新数据插入到双向链表头部，并在HashMap中添加新的记录。

核心代码框架

use std::collections::HashMap;

// 双向链表节点
struct DoublyLinkedListNode {
    key: i32,
    value: i32,
    prev: Option<Box<DoublyLinkedListNode>>,
    next: Option<Box<DoublyLinkedListNode>>,
}

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

// LRU缓存
struct LRUCache {
    capacity: i32,
    cache: HashMap<i32, (Box<DoublyLinkedListNode>, Option<&'static mut DoublyLinkedListNode>)>,
    head: Option<Box<DoublyLinkedListNode>>,
    tail: Option<Box<DoublyLinkedListNode>>,
}

impl LRUCache {
    fn new(capacity: i32) -> Self {
        LRUCache {
            capacity,
            cache: HashMap::new(),
            head: None,
            tail: None,
        }
    }

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

    fn put(&mut self, key: i32, value: i32) {
        if let Some((node, _)) = self.cache.get_mut(&key) {
            node.value = value;
            self.move_to_head(node);
        } else {
            let new_node = Box::new(DoublyLinkedListNode::new(key, value));
            if self.cache.len() as i32 >= self.capacity {
                self.remove_tail();
            }
            self.add_to_head(new_node);
        }
    }

    fn move_to_head(&mut self, node: &mut Box<DoublyLinkedListNode>) {
        if let Some(ref mut prev) = node.prev {
            prev.next = node.next.take();
        }
        if let Some(ref mut next) = node.next {
            next.prev = node.prev.take();
        }
        if let Some(ref mut tail) = self.tail {
            if tail.key == node.key {
                self.tail = node.next.take();
            }
        }
        self.add_to_head(node);
    }

    fn add_to_head(&mut self, mut node: Box<DoublyLinkedListNode>) {
        if let Some(ref mut head) = self.head {
            head.prev = Some(node);
            node.next = Some(Box::from(*head));
        }
        self.head = Some(node);
        if self.tail.is_none() {
            self.tail = self.head.clone();
        }
    }

    fn remove_tail(&mut self) {
        if let Some(mut tail) = self.tail.take() {
            if let Some(prev) = tail.prev.take() {
                prev.next = None;
                self.tail = Some(prev);
            } else {
                self.head = None;
                self.tail = None;
            }
            self.cache.remove(&tail.key);
        }
    }
}

面试题：Rust HashMap缓存系统的内存管理与设计权衡

知识考点

面试题答案

高效内存利用与快速响应机制设计思路

结合HashMap实现LRU缓存淘汰策略设计

核心代码框架