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

Question

Python 字典的查找算法内部是怎么工作的呢？

mydi['foo'] 

如果字典里有 1,000,000 个条目，查找的时候会执行树形搜索吗？我应该关注键字符串的长度，还是字典的大小来评估性能呢？也许把所有东西都放进字典里，和为 500 万个字符写一个树形搜索索引效果是一样的？

Answer 1

这里有个很好的解释：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

Answer 2

正如你在标题中提到的，字典其实就是哈希表。它并不使用树形搜索。查找一个键的操作几乎是恒定时间的，无论字典有多大。

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

Answer 3

这里有一些接近实际情况的伪代码。想象一下，字典有一个 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 时，都会进行字典查找，但不会调用哈希函数。