小编典典

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

algorithm

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

mydi['foo']

如果字典中有1,000,000个词,是否执行树搜索?我希望以键串的长度还是字典的大小来提高性能?也许将所有内容填充到字典中就像为大小为500万的字符串编写树搜索索引一样好?


阅读 306

收藏
2020-07-28

共1个答案

小编典典

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

2020-07-28