系统结构类代码题最高频，LeetCode 146，几乎所有大厂都问。
要求：get和put都O(1)；容量满时淘汰最久未用。
HashMap单独：查O(1)但无序。链表单独：有序但查O(n)。组合：map→链表节点，双向链表支持O(1)摘除。
get(key)：map查节点→摘除→移到头。put(key)：存在就更新+移头；不存在就建节点插头，超容量删尾。
必须双向链表——中间节点O(1)摘除要知道前驱。
用哨兵头尾伪节点避免边界null判断。
HashMap指向双向链表节点。get：map查到节点、摘下、插到头、返回值。put：存在就改值并移头；不存在造节点插头，超容量就删尾并同步map。每步O(1)：map O(1)、知道节点后双向链表摘O(1)、头尾插O(1)。Java的LinkedHashMap就是这个结构——重写removeEldestEntry五行搞定——但面试要你展示内部实现。两个坑：删尾时一定也删map里的键、用哨兵头尾避免null判断。
LinkedHashMap(accessOrder=true)是真实代码里的五行版。
LFU（按频率）是常见追问——要桶结构，比LRU难。
即答侠背了40行Java版和LFU扩展。
中间节点O(1)摘除要知道前驱。单链表要从头走O(n)。
朴素实现不是线程安全的。并发LRU用Caffeine或加锁——完全无锁的LRU很难。