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

Question

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

mydi['foo'] 

如果字典有 1,000,000 个词，是否执行树搜索？我会期望在 key 字符串的长度或字典大小方面的性能吗？也许把所有东西都塞进字典里就和为 500 万大小的字符串写一个树搜索索引一样好？

Answer 1

这里有一些更接近实际情况的伪代码。想象一下字典有一个 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 总是比实际使用的单元格数大得多，因此当键不存在时，哈希最终会命中一个空单元格(通常应该很快命中一个)。键还有一个已删除的值，用于指示不应终止搜索但当前未使用的单元格。

至于您关于 key 字符串长度的问题，对字符串进行哈希处理会查看字符串中的所有字符，但字符串也有一个用于存储计算出的哈希值的字段。因此，如果您每次使用不同的字符串进行查找，则字符串长度可能会产生影响，但如果您有一组固定的键并重复使用相同的字符串，则在第一次使用后不会重新计算哈希值. Python 从中受益，因为大多数名称查找都涉及字典，并且每个变量或属性名称的单个副本都存储在内部，因此每次访问属性 x.y 时都会进行字典查找而不是调用散列函数。