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

Question

我正在实现类似缓存的功能，其工作方式如下:

1. 如果给定键的新值来自某个外部进程，则存储该值，并记住该值到达的时间。
2. 如果我们空闲，找到缓存中最旧的条目，从外部源获取键的新值并更新缓存。
3. 在询问时返回给定键的值。

我需要一个数据结构来存储键值对，以便尽快执行以下操作(按速度优先顺序):

1. 找到具有最低(未知)值的键。
2. 更新给定键的值，或者如果键不存在则添加新的键值对。
3. 其他常规哈希表操作，如删除键、检查键是否存在等。

是否有任何数据结构允许这样做？这里的问题是，为了快速执行第一个查询，我需要一些按值排序的东西，而要快速更新给定键的值，我需要一些按键排序的东西。到目前为止，我最好的解决方案是这样的:

将值存储在常规哈希表中，并将(值，键)对存储为按值排序的堆。找到最低值的键是这样的:

1. 找到堆上最低值的键。
2. 从哈希表中找到该键的值。
3. 如果值不匹配，则从堆中弹出值并从第 1 步开始重复。

更新值是这样的:

1. 将值存储在哈希表中。
2. 将新的(值，键)对推送到堆中。

删除键比较棘手，需要在堆中搜索值。这提供了类似 O(log n) 的性能，但这个解决方案对我来说似乎很麻烦。

是否有任何数据结构结合了键的哈希表和关联值的堆的属性？我正在用 Python 编程，所以如果 Python 中有现有的实现，那将是一个很大的优势。

Answer 1

大多数堆实现将在 O(1) 时间内为您获取集合中最低的键，但不能保证随机查找或删除的速度。我建议配对两种数据结构:任何简单的堆实现和任何开箱即用的哈希表。

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