第3章 数据结构选型与权衡：双向链表 vs 有序字典、哈希表冲突处理、优先级队列适用场景

选择合适的数据结构是缓存系统设计的核心决策。LRU淘汰要求O(1)的移动和O(1)的访问，TTL过期需要高效的过期扫描，而哈希表冲突处理直接影响最坏情况性能。本章从工程角度对比四种主流方案，帮助你在不同约束下做出权衡。

核心数据结构对比一览

3.1 双向链表 + 哈希表：经典LRU组合

这是LRU缓存的标准实现方案。哈希表提供O(1)的键到节点的映射，双向链表维护访问顺序——每次访问将节点移到链表头部，淘汰时移除链表尾部节点。

节点定义

class Node:
    def __init__(self, key: int, value: int):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

核心操作

class LRUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = {}          # key -> Node
        self.head = Node(0, 0)   # 虚拟头
        self.tail = Node(0, 0)   # 虚拟尾
        self.head.next = self.tail
        self.tail.prev = self.head

    def _remove(self, node: Node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _add_to_head(self, node: Node):
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        node = self.cache[key]
        self._remove(node)
        self._add_to_head(node)
        return node.value

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self._remove(node)
            self._add_to_head(node)
        else:
            if len(self.cache) >= self.capacity:
                lru = self.tail.prev
                self._remove(lru)
                del self.cache[lru.key]
            new_node = Node(key, value)
            self.cache[key] = new_node
            self._add_to_head(new_node)

3.2 有序字典：语言内置的捷径

Python的OrderedDict、Java的LinkedHashMap等有序字典本质上是哈希表+双向链表的组合封装。它们对外暴露了“保持插入顺序”的迭代能力，并支持move_to_end等高效操作。

Python OrderedDict 实现 LRU

from collections import OrderedDict

class LRUCacheOrderedDict:
    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)   # 弹出最早插入的键

3.3 哈希表冲突处理：链地址法 vs 开放地址法 vs 再哈希

无论使用哪种上层方案，底层哈希表的冲突处理策略决定了最坏情况查找时间和内存密度。下表总结了三种主流方法：

3.4 优先级队列：TTL过期的利器

当缓存需要TTL自动过期时，单独依赖哈希表或链表无法高效判断“哪些键已经过期”。使用最小堆（优先级队列）存储(expiry_time, key)，可以在O(log n)时间内找到最早过期的键，配合惰性删除，实现高效的过期清理。

TTL过期堆实现

import heapq
import time

class TTLHeap:
    def __init__(self):
        self.heap = []          # (expiry, key)
        self.active_keys = set()  # 辅助去重

    def add(self, key: int, ttl: int):
        expiry = time.time() + ttl
        heapq.heappush(self.heap, (expiry, key))
        self.active_keys.add(key)

    def pop_expired(self):
        """返回所有已过期的key（惰性删除）"""
        now = time.time()
        while self.heap and self.heap[0][0] <= now:
            expiry, key = heapq.heappop(self.heap)
            if key in self.active_keys:    # 防止重复
                self.active_keys.discard(key)
                yield key

与LRU组合作业流程

1. put(key, value, ttl)时：写入哈希表/链表，同时在堆中压入(time+ttl, key)。
2. get(key)时：先检查堆顶是否过期，若过期则惰性清理，再访问哈希表。
3. 后台线程或pop_expired周期清理：从堆中弹出所有过期key，并从LRU结构中删除对应节点。

3.5 综合选型决策建议

• 纯LRU（无TTL或TTL统一）：推荐双向链表+哈希表，实现透明且性能可预测。
• LRU + 差异化TTL：推荐双向链表+哈希表+优先级队列，三类结构各司其职。
• 快速验证：直接使用有序字典（如Python OrderedDict），但需注意TTL需额外实现。
• 内存极度受限：考虑开放地址法的哈希表，但需控制负载因子在0.6~0.7以下。