华为题库已更新至:华为实习&秋招真题题库，请移步。

思路

双向链表 + 哈希表

这是一道经典原题146. LRU缓存 。

每次查询或插入 key 成功后，都会更新 key 的优先级，这个优先级会影响大小满了之后，如何弹出旧元素，以有空间插入新元素。

朴素情况是，我们维护一个链表，每次遍历链表找到 key ，单次查找的时间复杂度是 $O(n)$ ，这会超时，考虑优化单次查找的时间。