数据结构与算法 · 单选题 · 第 61 题

计算机基础面试八股 · 第 61 题

实现一个 get 和 put 操作都是 O(1) 的 LRU 缓存,常用的数据结构组合是?

答案

C C. 哈希表加双向链表

哈希表用于 O(1) 定位节点,双向链表维护访问顺序:访问时把节点移到表头,容量满时删掉表尾,两种操作都是 O(1)。必须是双向链表,因为删除任意节点要能找到它的前驱。堆按时间戳排序时,每次更新都是 O(log n)。Java 的 LinkedHashMap 开启访问顺序后就能直接实现 LRU。