存储键值对并快速检索最低值键的数据结构

Question

我正在实现一个类似缓存的东西，工作原理如下：

1. 如果有新的值通过某个外部过程传入，先存储这个值，并记住这个值到达的时间。
2. 如果我们处于空闲状态，就找出缓存中最旧的条目，从外部源获取这个键的新值，并更新缓存。
3. 当有人询问时，返回给定键的值。

我需要一个数据结构来存储键值对，这样可以尽可能快地执行以下操作（按速度优先级排序）：

1. 找到值最小的（未知的）键。
2. 更新给定键的值，或者如果这个键不存在，就添加一个新的键值对。
3. 其他常规的哈希表操作，比如删除一个键，检查一个键是否存在等等。

有没有这样的数据结构可以实现这些功能？这里的问题是，为了快速执行第一个查询，我需要某种按值排序的结构，而为了快速更新给定键的值，我又需要某种按键排序的结构。我目前想到的最佳解决方案是这样的：

在一个普通的哈希表中存储值，同时将（值，键）对存储在一个按值排序的堆中。找到最小值对应的键的过程如下：

1. 在堆中找到最小值对应的键。
2. 从哈希表中找到这个键的值。
3. 如果值不匹配，就从堆中弹出这个值，然后从第一步重新开始。

更新值的过程如下：

1. 在哈希表中存储这个值。
2. 将新的（值，键）对推入堆中。

删除一个键就比较棘手，需要在堆中查找这个值。这种方法的性能大约是O(log n)，但我觉得这个解决方案有点麻烦。

有没有结合哈希表和堆特性的数据结构？我用的是Python，如果有现成的Python实现，那就更好了。

Answer 1

你在找的是一种叫做“映射”的东西，或者说是“关联数组”。如果想更详细地了解，我们需要知道你想用哪种编程语言。

Answer 2

我会试试：

import heapq

myheap = []
mydict = {}

...

def push(key, val):
    heapq.heappush(myheap, (val, key))
    mydict[key] = val

def pop():
    ...

更多信息可以在 这里 找到

Answer 3

大多数堆的实现可以在O(1)的时间内找到你集合中的最小值，但对于随机查找或删除的速度就没有保证了。我建议你可以把两种数据结构结合起来使用：一种简单的堆实现和一种现成的哈希表。

当然，任何平衡的二叉树都可以用作堆，因为最小值和最大值分别在最左边和最右边的叶子节点上。红黑树或AVL树应该能让你在O(lg n)的时间内完成堆和字典的操作。