Python字典哈希查找是如何工作的？

Question

Python字典哈希查找是如何工作的？

29

Python 字典的查找算法是如何内部实现的？

mydi['foo']

如果字典有1,000,000个条目，会执行一次树搜索吗？我应该期望基于键字符串的长度还是字典的大小来衡量性能？或许将所有内容塞进字典中和编写一个针对5百万个字符串的树搜索索引一样好呢？

- shigeta

虽然我可以理解Python字典如下所述的工作原理，但哈希总体上比这更丰富。人们可以想象，对于大型字典，这种简单的查找将需要很长时间。Perl哈希使用的系统基本上是通过将哈希元素按键的每个字符进行汇集来建立索引。 - shigeta

请查看http://www.perl.com/pub/2002/10/01/hashes.html。 - shigeta

5个回答

7

正如您在标题中提到的，字典是哈希表。没有使用树搜索。查找键是几乎恒定时间的操作，无论字典的大小如何。

您可能会发现这个问题的答案有帮助：Python内置字典是如何实现的

- Ned Batchelder

1

+1，但是为什么不用“摊销常数”来代替“几乎常数”？最坏情况下的时间复杂度是常数吗？ - Neil G

@Neil 这是最坏情况的线性时间复杂度，如果你得到一组输入，不过它与每个输入都发生了碰撞。然而，即使对手也无法做到这一点，因为通用哈希可以解决这个问题。 - user684934

4

"Nearly constant" 的意思是 "摊销常数"！ :) - Ned Batchelder

@bdares 通用哈希？我只能假设你在谈论完美哈希，但它们在这里不适用。 - Nick Johnson

你能解释一下查找键的工作原理以及为什么它几乎是恒定时间吗？如果字典是一个“哈希、键、值”表，我不明白为什么需要一个“哈希”列。哈希列是否按哈希值排序？为什么不按“键”排序并在键上搜索表呢？ - Dictador

5

这里有一个好的解释：http://wiki.python.org/moin/DictionaryKeys 上面链接中的伪代码：

def lookup(d, key):
    '''dictionary lookup is done in three steps:
       1. A hash value of the key is computed using a hash function.

       2. The hash value addresses a location in d.data which is
          supposed to be an array of "buckets" or "collision lists"
          which contain the (key,value) pairs.

       3. The collision list addressed by the hash value is searched
          sequentially until a pair is found with pair[0] == key. The
          return value of the lookup is then pair[1].
    '''
    h = hash(key)                  # step 1
    cl = d.data[h]                 # step 2
    for pair in cl:                # step 3
        if key == pair[0]:
            return pair[1]
    else:
        raise KeyError, "Key %s not found." % key

- Acorn

似乎需要做很多工作，但对于大多数应用程序来说已经足够好了。这些键并没有像排序索引一样被真正地排序。谢谢，这很有帮助。 - shigeta

1

请注意，此 Python 代码处理冲突的方式与 Python 字典不同。哈希表实现在处理冲突时可能会有所不同。 - Ned Batchelder

1

哈希查找不使用树。它们使用哈希表，并且具有恒定时间的查找。它们将占用更多的空间（平均而言，我认为是两倍），但查找和插入时间会更快。

简单来说，对您的键进行md5处理，然后将其与您拥有的地址数量取模，这就是您保存或查找密钥的位置。无论集合有多大，只要没有重大冲突，它总是需要相同的时间，而一个好的哈希将避免这种情况。

- user684934

我猜这样对于合理的字典大小来说会更简单。看来我最终还是要构建自己的树搜索...如果是这样的话，与哈希查找进行基准测试可能会让我看起来很不错。 - shigeta

@shigeta，你真正的问题似乎是你试图使用内存空间数据结构实现某些可能不太适合内存的东西。我建议你使用DBMS。 - user684934

@shigeta：为什么要构建自己的树搜索？你似乎在暗示你的树会比字典更快，但这是不可能的。即使是5Mb的字符串，每个字符串也只被哈希一次。 - Ned Batchelder

这是关于编程的内容，翻译成中文如下：对于非常长的哈希值而言，一旦你拥有了几亿个键，哈希表的大小就很重要了。在这种情况下，主要是基因组中的子字符串。 - shigeta

@shigeta，您似乎对哈希的工作原理有所误解。您可以拥有无限数量的键，而哈希仍然需要恒定的时间。现在，密钥可能非常长，那么应该考虑到哈希需要与密钥长度成线性关系的时间来处理。但是同样如此的是前缀树查找。 - user684934

0

答案1：此视频中解释了内部工作原理。

答案2：如果您的字典中有一百万条记录，则不会进行树搜索。

答案3：由于可能存在键冲突，您将希望以字典的大小而不是关键字字符串的长度来衡量性能。

答案4：可以将字典视为数组（连续的内存位置），但数组内可能存在未使用的块。因此，与树相比，字典往往浪费大量内存空间。但是，为了更好的运行时性能，字典可能比树更好。键冲突有时会降低性能。您应该阅读有关一致性哈希的信息。

- ajmartin

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Duncan · Accepted Answer

以下是更接近实际情况的伪代码。假设字典具有一个包含键值对的 data 属性，以及一个表示分配的单元格数量的 size 属性。

def lookup(d, key):
    perturb = j = hash(key)
    while True:
        cell = d.data[j % d.size]
        if cell.key is EMPTY:
            raise IndexError
        if cell.key is not DELETED and (cell.key is key or cell.key == key):
            return cell.value
        j = (5 * j) + 1 + perturb
        perturb >>= PERTURB

perturb 值保证在解决哈希冲突时最终使用哈希代码的所有位，但一旦它降级到 0 ，(5*j)+1 将最终触及表中的所有单元格。

size 比实际使用的单元格数量始终要大得多，因此哈希在键不存在时保证最终会命中一个空单元格（并且通常很快就会命中）。还有一个已删除值用于表示不应终止搜索但当前未使用的单元格。

至于您关于键字符串长度的问题，哈希字符串将查看字符串中的所有字符，但字符串还具有用于存储计算出的哈希的字段。因此，如果您每次都使用不同的字符串进行查询，则字符串长度可能会产生影响，但是如果您有一组固定的键并重新使用相同的字符串，则哈希在第一次使用后不会被重新计算。Python 获得了这方面的好处，因为大多数名称查找涉及字典，并且每个变量或属性名称的单个副本都存储在内部，因此每次访问属性 x.y 都会进行字典查找，但不会调用哈希函数。