企业官网建设流程全解析

usestd::collections::HashMap;// 哨兵节点下标constHEAD:usize=0;constTAIL:usize=1;structNode{key:i32,value:i32,prev:usize,next:usize,}pubstructLRUCache{map:HashMap<i32,usize>,// key -> nodes 中的下标nodes:Vec<Node>,// 用 Vec 做 arena，下标代替指针capacity:usize,}implLRUCache{pubfnnew(capacity:i32)->Self{// nodes[HEAD] 与 nodes[TAIL] 是哨兵，互指lethead=Node{key:0,value:0,prev:HEAD,next:TAIL};lettail=Node{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].value=value;self.detach(idx);self.attach_front(idx);return;}// 不存在：满了就先淘汰 TAIL 前一个（最久未使用）letidx=ifself.map.len()==self.capacity{letlru=self.nodes[TAIL].prev;letlru_key=self.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){letprev=self.nodes[idx].prev;letnext=self.nodes[idx].next;self.nodes[prev].next=next;self.nodes[next].prev=prev;}/// 把节点挂到 HEAD 后面（最近使用端）fnattach_front(&mutself,idx:usize){letfirst=self.nodes[HEAD].next;self.nodes[idx].prev=HEAD;self.nodes[idx].next=first;self.nodes[HEAD].next=idx;self.nodes[first].prev=idx;}}

思路

LRU 需要哈希表 + 双向链表：

· HashMap 负责 O(1) 找到某个 key 对应的节点；
· 双向链表维护访问顺序，头部是最近使用，尾部是最久未使用。

Rust 里手写双向链表绕不开所有权问题，有两种常见做法：

1. Rc<RefCell>：安全但有运行时开销，且 prev 需要 Weak 防循环引用，写起来很啰嗦。
2. Arena + 下标（上面这种）：用 Vec 存所有节点，用 usize 下标代替指针，完全 safe，性能也好，是竞赛/工程里最常见的写法。

两个哨兵 HEAD / TAIL 让插入和删除都不用判空。

复杂度

· 时间：get / put 均为 O(1)
· 空间：O(capacity)

测试

#[test]fntest(){letmutc=LRUCache::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:LinkedHashMap<i32,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);}}}

但面试/刷题时建议手写第一种，能体现你对所有权和数据结构的基本功。