Python的字典映射使用什么散列算法？
Python的字典映射使用什么散列算法？
提问于 2012-01-25 12:40:48
我在做一个命令行解析器，想知道python dict使用哪种散列算法？
在我设置它的方式中，我有一个模式匹配算法，它将标记化的输入序列与字典键进行匹配。一些键相对较长(长度为5或6个6-7个字符串的元组)。我想知道是否有一个点，长字典关键字显着降低了关键字检索的效率。
回答 1
Stack Overflow用户
回答已采纳
发布于 2012-01-25 12:56:29
它使用的散列取决于用作键的对象--每个类都可以定义自己的__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版本中行为可能会发生变化)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/8997894
复制相关文章
相似问题