usestd::collections::HashMap;// 哨兵节点下标constHEAD:usize0;constTAIL:usize1;structNode{key:i32,value:i32,prev:usize,next:usize,}pubstructLRUCache{map:HashMapi32,usize,// key - nodes 中的下标nodes:VecNode,// 用 Vec 做 arena下标代替指针capacity:usize,}implLRUCache{pubfnnew(capacity:i32)-Self{// nodes[HEAD] 与 nodes[TAIL] 是哨兵互指letheadNode{key:0,value:0,prev:HEAD,next:TAIL};lettailNode{key:0,value:0,prev:HEAD,next:TAIL};Self{map:HashMap::new(),nodes:vec![head,tail],capacity:capacityasusize,}}pubfnget(mutself,key:i32)-i32{matchself.map.get(key).copied(){Some(idx){self.detach(idx);self.attach_front(idx);self.nodes[idx].value}None-1,}}pubfnput(mutself,key:i32,value:i32){// 已存在更新值并提到最前ifletSome(idx)self.map.get(key){self.nodes[idx].valuevalue;self.detach(idx);self.attach_front(idx);return;}// 不存在满了就先淘汰 TAIL 前一个最久未使用letidxifself.map.len()self.capacity{letlruself.nodes[TAIL].prev;letlru_keyself.nodes[lru].key;self.detach(lru);self.map.remove(lru_key);lru// 复用这个槽位避免 nodes 无限增长}else{self.nodes.push(Node{key:0,value:0,prev:0,next:0});self.nodes.len()-1};self.nodes[idx]Node{key,value,prev:0,next:0};self.attach_front(idx);self.map.insert(key,idx);}/// 把节点从链表中摘下来fndetach(mutself,idx:usize){letprevself.nodes[idx].prev;letnextself.nodes[idx].next;self.nodes[prev].nextnext;self.nodes[next].prevprev;}/// 把节点挂到 HEAD 后面最近使用端fnattach_front(mutself,idx:usize){letfirstself.nodes[HEAD].next;self.nodes[idx].prevHEAD;self.nodes[idx].nextfirst;self.nodes[HEAD].nextidx;self.nodes[first].previdx;}}思路LRU 需要哈希表 双向链表· HashMap 负责 O(1) 找到某个 key 对应的节点· 双向链表维护访问顺序头部是最近使用尾部是最久未使用。Rust 里手写双向链表绕不开所有权问题有两种常见做法RcRefCell安全但有运行时开销且 prev 需要 Weak 防循环引用写起来很啰嗦。Arena 下标上面这种用 Vec 存所有节点用 usize 下标代替指针完全 safe性能也好是竞赛/工程里最常见的写法。两个哨兵 HEAD / TAIL 让插入和删除都不用判空。复杂度· 时间get / put 均为 O(1)· 空间O(capacity)测试#[test]fntest(){letmutcLRUCache::new(2);c.put(1,1);c.put(2,2);assert_eq!(c.get(1),1);// 1 变为最近使用c.put(3,3);// 淘汰 2assert_eq!(c.get(2),-1);c.put(4,4);// 淘汰 1assert_eq!(c.get(1),-1);assert_eq!(c.get(3),3);assert_eq!(c.get(4),4);}如果不想手写链表生产代码里可以直接用 hashlink crate 的 LinkedHashMap它内部就是哈希表 链表的实现能把 LRUCache 压成十几行usehashlink::LinkedHashMap;pubstructLRUCache{map:LinkedHashMapi32,i32,capacity:usize,}implLRUCache{pubfnnew(capacity:i32)-Self{Self{map:LinkedHashMap::new(),capacity:capacityasusize}}pubfnget(mutself,key:i32)-i32{// to_back 把 key 移到“最近使用”端matchself.map.to_back(key){Some(v)v,None-1,}}pubfnput(mutself,key:i32,value:i32){ifself.map.contains_key(key){self.map.insert(key,value);self.map.to_back(key);}else{ifself.map.len()self.capacity{self.map.pop_front();// 淘汰最久未使用}self.map.insert(key,value);}}}但面试/刷题时建议手写第一种能体现你对所有权和数据结构的基本功。