LRU 缓存的底层数据结构详解一、LRU 是什么LRULeast Recently Used最近最少使用是一种缓存淘汰策略当缓存满时优先淘汰最久没有被访问的数据。访问顺序A → B → C → D → B → A → E 缓存容量 3 步骤 1. 访问 A[A] (A 最近使用) 2. 访问 B[B, A] (B 比 A 新) 3. 访问 C[C, B, A] (满了) 4. 访问 D淘汰 A[D, C, B] (A 最久没用了) 5. 访问 B移到头部[B, D, C] 6. 访问 A淘汰 C[A, B, D] 7. 访问 E淘汰 D[E, A, B]二、LRU 的底层数据结构标准实现HashMap 双向链表LinkedHashMap┌─────────────────────────────────────────┐ │ HashMapK, Node │ │ Key → Node 引用 │ │ 提供 O(1) 的查找能力 │ └─────────────────────────────────────────┘ │ ▼ ┌─────────────────────────────────────────┐ │ 双向链表维护访问顺序 │ │ │ │ head ←→ Node1 ←→ Node2 ←→ Node3 ←→ tail│ │ (最近使用) ↑ (最久未用) │ │ 新节点插入头部 │ │ 访问节点移到头部 │ │ 淘汰从尾部移除 │ └─────────────────────────────────────────┘为什么必须结合两者单独使用 HashMap单独使用链表HashMap 链表查找 O(1) ✅查找 O(n) ❌查找 O(1) ✅无法维护顺序 ❌顺序维护方便 ✅顺序维护方便 ✅淘汰需遍历 ❌插入/删除 O(1) ✅插入/删除 O(1) ✅三、双向链表如何提高查询效率关键认知双向链表本身查询是 O(n)// 普通双向链表查找必须遍历Nodefind(Nodehead,intkey){Nodecurhead;while(cur!null){if(cur.keykey)returncur;curcur.next;}returnnull;// O(n)}真正提高查询效率的是 HashMap不是链表。那链表的作用是什么链表负责维护访问顺序和实现 O(1) 的插入/删除/移动。classLRUCache{// HashMapO(1) 查找节点位置privateHashMapInteger,Nodemap;// 双向链表维护访问顺序O(1) 调整位置privateNodehead,tail;classNode{intkey,value;Nodeprev,next;// 双向指针O(1) 删除和插入}}为什么是双向链表而不是单向链表操作单向链表双向链表头部插入O(1) ✅O(1) ✅头部删除O(1) ✅O(1) ✅尾部删除O(n)❌O(1)✅已知节点删除O(n)❌O(1)✅节点前移O(n) ❌O(1) ✅LRU 的核心操作访问节点 → 移到头部 → 需要删除原位置 插入头部缓存满 → 淘汰尾部 → 需要删除尾部这两个操作在单向链表中都需要遍历找到前驱节点是 O(n)。双向链表通过prev指针直接定位前驱是 O(1)。四、完整 Java 实现publicclassLRUCacheK,V{// 双向链表节点privateclassNode{Kkey;Vvalue;Nodeprev,next;Node(Kkey,Vvalue){this.keykey;this.valuevalue;}}privatefinalintcapacity;privatefinalHashMapK,Nodemap;// O(1) 查找privatefinalNodehead,tail;// 虚拟头尾节点简化边界处理publicLRUCache(intcapacity){this.capacitycapacity;this.mapnewHashMap();// 虚拟节点不存数据headnewNode(null,null);tailnewNode(null,null);head.nexttail;tail.prevhead;}// O(1) 查询publicVget(Kkey){Nodenodemap.get(key);if(nodenull)returnnull;// 移到头部最近使用moveToHead(node);returnnode.value;}// O(1) 插入/更新publicvoidput(Kkey,Vvalue){Nodenodemap.get(key);if(node!null){// 更新已有节点node.valuevalue;moveToHead(node);}else{// 新建节点NodenewNodenewNode(key,value);map.put(key,newNode);addToHead(newNode);// 超出容量淘汰尾部if(map.size()capacity){NoderemovedremoveTail();map.remove(removed.key);}}}// O(1) 移到头部privatevoidmoveToHead(Nodenode){removeNode(node);// 先删除原位置addToHead(node);// 再插入头部}// O(1) 删除节点双向链表的核心优势privatevoidremoveNode(Nodenode){node.prev.nextnode.next;node.next.prevnode.prev;}// O(1) 插入头部privatevoidaddToHead(Nodenode){node.prevhead;node.nexthead.next;head.next.prevnode;head.nextnode;}// O(1) 删除尾部双向链表的核心优势privateNoderemoveTail(){Nodenodetail.prev;// 直接通过 prev 找到尾部前驱removeNode(node);returnnode;}}五、LinkedHashMap 实现Java 内置Java 的LinkedHashMap已经内置了 LRU 功能只需重写removeEldestEntrypublicclassLRUCacheK,VextendsLinkedHashMapK,V{privatefinalintcapacity;publicLRUCache(intcapacity){// accessOrder true按访问顺序排序false 是按插入顺序super(capacity,0.75f,true);this.capacitycapacity;}OverrideprotectedbooleanremoveEldestEntry(Map.EntryK,Veldest){// 当容量超过时自动移除最老的条目returnsize()capacity;}// 使用// LRUCacheString, Bitmap cache new LRUCache(100);// cache.put(key, bitmap);// Bitmap bmp cache.get(key); // 访问后自动移到头部}LinkedHashMap 内部结构HashMap 部分 table[0] → Entry1 → Entry2 table[1] → Entry3 table[2] → null ... 双向链表部分维护顺序 header ←→ Entry3 ←→ Entry1 ←→ Entry2 (最近使用) (最久未用)六、Android 中的 LRU 应用1. LruCacheAndroid 内置// 内存缓存用于图片等intmaxMemory(int)(Runtime.getRuntime().maxMemory()/1024);intcacheSizemaxMemory/8;// 取 1/8LruCacheString,BitmapbitmapCachenewLruCacheString,Bitmap(cacheSize){OverrideprotectedintsizeOf(Stringkey,Bitmapvalue){// 返回每个条目的大小KBreturnvalue.getByteCount()/1024;}OverrideprotectedvoidentryRemoved(booleanevicted,Stringkey,BitmapoldValue,BitmapnewValue){// 条目被移除时的回调可以回收 Bitmapif(oldValue!null!oldValue.isRecycled()){oldValue.recycle();}}};// 使用bitmapCache.put(url,bitmap);BitmapcachedbitmapCache.get(url);2. Glide 的缓存结构Glide 三级缓存 1. 活动资源缓存ActiveResources - 弱引用 HashMap正在显示的图片 - 不在 LRU 中避免被回收 2. 内存缓存LruResourceCache - LruCache最近使用的图片 - 容量屏幕尺寸 × 2.5 3. 磁盘缓存DiskLruCache - 基于文件的 LRU 缓存 - 默认 250MB七、总结问题答案LRU 底层数据结构HashMap 双向链表HashMap 的作用O(1) 查找节点双向链表的作用O(1) 维护访问顺序插入、删除、移动为什么不用单向链表删除尾部和已知节点需要 O(n) 找前驱为什么不用数组插入/删除需要 O(n) 移动元素为什么不用红黑树不需要排序链表即可维护顺序且常数更小查询效率谁贡献的HashMap 贡献 O(1) 查找链表只负责顺序维护一句话HashMap 提供找到它在哪双向链表提供快速调整位置。两者缺一不可。
