最近最少使用(LRU)缓存

Question

我知道我可以在STL中使用各种容器类,但对于此目的而言,这是一种过度杀伤并且代价高昂.

我们有超过1M +用户在线,每个用户需要维护8个不相关的32位数据项.目标是

1. 查找列表中是否存在项目,
2. 如果没有,请插入.如果已满,请删除最旧的条

蛮力方法是维护最后一个写指针并迭代(因为只有8个项目),但我正在寻找更好的分析和实现的输入.

期待在设计模式和算法方面提出一些有趣的建议.

Answer 1

您想在这里使用Hash表和的组合doubly linked list。
每个项目都可以通过哈希表访问，该哈希表包含您需要的键以及指向列表中元素的指针。

算法：

给定新项目x，执行以下操作：
1. 添加x到列表的头部，将指针保存为ptr。
2. 添加x到存储数据的哈希表中，并添加ptr。
3. 如果列表大于允许的大小，则取出最后一个元素（从列表的尾部开始）并将其删除。使用该元素的键也可以将其从哈希表中删除。