代码之家  ›  专栏  ›  技术社区  ›  abbot

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

  •  2
  • abbot  · 技术社区  · 14 年前

    我正在实现类似缓存这样的功能:

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

    我需要一个数据结构来存储键值对,它允许尽可能快地执行以下操作(按速度优先顺序):

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

    是否有数据结构允许这样做?这里的问题是,为了快速执行第一个查询,我需要排序的值,为了快速更新给定键的值,我需要排序的键。到目前为止,我拥有的最佳解决方案是这样的:

    将值存储在常规哈希表中,将成对的(值、键)存储为值顺序堆。查找最小值的键如下所示:

    1. 查找堆中最小值的键。
    2. 从哈希表中查找该键的值。
    3. 如果值不匹配,则从堆中弹出值,然后从步骤1中重复。

    更新值的过程如下:

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

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

    是否有任何数据结构组合键的哈希表属性和关联值的堆属性?我正在用python编程,所以如果在python中有现有的实现,这是一个很大的优势。

    3 回复  |  直到 14 年前
        1
  •  3
  •   Juliet    14 年前

    大多数堆实现将在O(1)时间内获得集合中的最低密钥,但对于随机查找或删除的速度没有任何保证。我建议将两个数据结构配对:任何简单的堆实现和任何现成的哈希表。

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

        2
  •  0
  •   Brian S    14 年前

    您正在查找地图或关联数组。为了更具体一些,我们需要知道你想用什么语言。

        3
  •  0
  •   pillmuncher    14 年前

    我会尝试:

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

    更多信息 here