Python的字典映射使用什么哈希算法？

Question

我正忙着制作一个命令行解析器,并想知道什么样的哈希算法python dict的使用？

我设置它的方式,我有一个模式匹配算法,它将标记化的输入序列与字典键匹配.一些键相对较长(长度为5或6个6-7个字符串的元组).我想知道长字典键是否会显着降低密钥检索的效率.

Answer 1

它使用的散列取决于被用作键的对象 - 每个类可以定义自己的__hash __()方法,并且它为特定实例返回的值是用于字典的值.

Python本身为str和tuple类型提供了哈希实现.快速查看源代码应该揭示这些的确切算法.

元组的散列基于其内容的散列.该算法基本上是这个(略有简化):

def hash(tuple):
    mult = 1000003
    x = 0x345678
    for index, item in enumerate(tuple):
        x = ((x ^ hash(item)) * mult) & (1<<32)
        mult += (82520 + (len(tuple)-index)*2)
    return x + 97531

对于字符串,解释器还迭代每个字符,将它们与此(再次,略微简化)算法组合:

def hash(string):
    x = string[0] << 7
    for chr in string[1:]:
        x = ((1000003 * x) ^ chr) & (1<<32)
    return x

需要担心的一个更大问题是避免哈希冲突.当字典试图找到存储新对象的位置时,碰撞散列键将导致线性搜索(现在这被认为是一个安全问题,并且在即将发布的python版本中行为可能会发生变化)