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

Question

Python字典查找算法如何在内部工作？

mydi['foo'] 

如果字典有1,000,000个术语,是否执行了树搜索？我是否期望在关键字符串的长度或字典的大小方面表现？也许将所有内容都填入字典中就像为500万字符串的字符串编写树搜索索引一样好？

Answer 1

这里有一些伪代码更接近实际发生的事情.想象一下,字典有一个data属性,包含键,值对和a 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时都会进行字典查找,但不会调用哈希函数.

Answer 2

正如您在标题中提到的,dicts是哈希表.不使用树搜索.无论字典的大小如何,查找键都是一个几乎恒定的时间操作.

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

Answer 3

这是一个很好的解释: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