LRU 是什么（缓存淘汰策略）
想象你有一个小书桌，只能放 3 本书。当你需要一本新书时，如果桌子满了，你会扔掉最久没翻过的那本。这就是 LRU（Least Recently Used） 缓存淘汰策略：当缓存空间满时，优先淘汰最久未被访问的数据。
为什么需要 双向链表+哈希表 两种结构
仅用链表，查找数据需要 O(n) 遍历；仅用哈希表，无法快速调整节点顺序（因为哈希表无序）。双向链表 负责维护访问顺序（最近访问的放头部，最久未用的放尾部），哈希表 负责 O(1) 定位节点。两者配合，才能同时实现快速查找和快速顺序调整。
get 和 put 的完整流程
get(key)：从哈希表找节点，若存在则将该节点移到链表头部（表示最近使用），返回 value；否则返回 -1。
put(key, value)：若 key 已存在，更新 value 并移到头部；若不存在，创建新节点加入头部，若容量超限，则删除链表尾部节点（最久未用）并同时从哈希表移除。
为什么 get/put 都是 O(1)
- 哈希表查找、插入、删除都是 O(1)。
- 双向链表的头部插入、尾部删除、节点移动（删除+插入）都是 O(1)，因为只需修改相邻节点的指针，无需遍历。
- 因此整个操作时间复杂度为 O(1)。
工程实现与面试手写
在 Java 中可使用 LinkedHashMap，设置 accessOrder=true 并重写 removeEldestEntry 即可实现 LRU。Python 中 OrderedDict 的 move_to_end 和 popitem(last=False) 也能轻松实现。面试手写时，通常要求自己实现双向链表和哈希表，以考察对数据结构的理解。