LRU 缓存为什么常组合哈希表和双向链表？
哈希表负责按键快速定位，双向链表维护最近使用顺序，使命中更新和淘汰尾部都可接近 O(1)。实现难点是两种结构必须原子地保持一致，并定义容量、并发、失败回滚和对象所有权。
Question Bank
按知识、方向与难度筛选；每道题都有分层回答和工程追问。
哈希表负责按键快速定位，双向链表维护最近使用顺序，使命中更新和淘汰尾部都可接近 O(1)。实现难点是两种结构必须原子地保持一致，并定义容量、并发、失败回滚和对象所有权。
最小堆能 O(1) 查看最近到期项，插入和删除根为 O(log n)，适合动态定时器集合；线性表查找最近项为 O(n)，但任务很少时实现更简单且常数更小。
位图用一个 Bit 表示一个固定编号资源，空间紧凑，集合并交和查找空闲位可借助按字运算或 CLZ/CTZ。它适合容量已知、只需占用状态的对象，不适合存储复杂元数据。
侵入式链表把节点嵌入业务对象，不需为节点单独分配内存，插入删除成本稳定，还能用 container-of 找回宿主对象。代价是对象与容器耦合、同一节点不能同时属于多个链表，生命周期必须严格受控。
SPSC 可以让生产者独占写索引、消费者独占读索引，但发布索引前必须保证数据写入已对另一执行单元可见，读取索引后也要建立相应顺序。volatile 只约束编译器访问，不能完整替代原子和屏障。
大 O 描述输入规模增长趋势，忽略常数、缓存、总线争用、分支和抢占；实时系统关心给定平台与输入边界下的时间上界。应先限制数据规模和执行路径，再结合测量与静态分析建立 WCET 证据。