§05 线性结构

LRU 缓存

哈希表 + 双向链表：O(1) 定位 + O(1) 淘汰。头部 MRU、尾部 LRU——容量满时淘汰最久未使用者。

LRU 缓存

第 01 / 11 步

put(1, 11)：新节点插入头部。当前 1/4。　缓存: [1=11] 比较 0 · 交换 0

伪代码


				
					
					1
					// LRU：哈希表定位 + 双向链表维护顺序
				
			
				
					
					2
					get(key):
				
			
				
					
					3
					  if key in map: 节点移到链表头; return value
				
			
				
					
					4
					  else: return -1
				
			
				
					
					5
					put(key, value):
				
			
				
					
					6
					  if key in map: 更新值 + 移到头
				
			
				
					
					7
					  else:
				
			
				
					
					8
					    if size == capacity: 淘汰链表尾（LRU）
				
			
				
					
					9
					    新节点插到链表头

01 / 11

速度