LRU、Top K 和任务依赖，怎样用数据结构解决？

标准回答

我会从操作需求选数据结构，而不是只记名称。按 taskId 查任务适合哈希表；先进先出的待执行任务适合队列；要优先执行高优任务，可以考虑堆实现的优先队列，同时处理低优任务长期得不到执行的问题。

LRU 要求快速查找，并在每次访问后更新最近使用顺序，可以用哈希表加双向链表：哈希表找到节点，链表把节点移动到头部，容量超限时移除尾部。正常哈希分布下查询和更新平均为 O(1)。Java 的 LinkedHashMap 可以启用访问顺序并结合淘汰规则实现简化版本，但它不是线程安全容器。

从 N 个分数中找最大的 K 个，可以维护大小为 K 的最小堆。堆顶是当前入选项里最小的，新分数更大才替换；处理成本为 O(N log K)，空间为 O(K)。如果要求最终按分数排序，还需要对入选的 K 个结果排序。K 接近 N 或数据很小时，也应比较全量排序的实现成本。

多步任务存在依赖时，可以用有向图和入度表。把入度为零的节点放入队列，处理后减少后继入度；最终未能处理所有节点说明存在环。这可以得到拓扑顺序，但真实异步执行还必须等待前置任务成功后才放行后继，失败和取消由状态机处理，不能只算出顺序就同时启动全部任务。

“读取设备状态”和“加载歌单”互不依赖，可在资源允许时并行；“开始播放”必须等目标连接及必要准备完成。依赖图表达前置条件，执行器负责并发上限，状态机负责异常。

哈希表已经能找到被访问的节点，接下来要在 O(1) 时间把它从当前位置摘下并移到头部。双向链表可以直接访问前后节点；普通单链表如果没有额外记录前驱，还要遍历找前驱。淘汰尾节点时同样需要更新前驱，因此双向链表更直接。

访问顺序模式下 get 也会修改链表，所以不能只保护 put。最简单是用同一把锁保护完整的读写与淘汰过程，且不在锁内做网络加载。更高并发时可采用成熟缓存组件，但仍要明确容量、过期和重复加载语义；把 HashMap 换成 ConcurrentHashMap 并不能自动保护旁边的链表。

HashMap 的平均 O(1) 不是无条件最坏 O(1)；LRU 不自动处理 TTL，PriorityQueue 遍历也不保证整体有序。下面示例只演示单线程、按条目数量限制的缓存。