如果我只使用最大长度为15的字符串作为python中字典的键,是否不可能发生任何冲突?
不
. 碰撞
可以
发生。散列函数的结果根据“主机系统”被截断。这意味着
hash(..)
32位系统中的字符串是32位整数,对于64位系统,它通常是64位数字。
现在,如果我们计算少于或等于15个字符的字符串数(这里我们只假设可打印的ASCII字符,但是如果我们考虑所有Unicode字符,我们只会使其更糟),那么这意味着我们可以生成:
15
---
\ i
/ (128-32)
---
i=0
不同的字符串。等于547'792'552'280'497'574'758'284'371'041或约5.47×10
二十九
. 64位数字的数目是2
六十四
=18'446'744'073'709'551'616&约1.84×10
十九
. 所以即使我们只考虑
ASCII可打印字符串
,然后我们不能将每个字符串映射到单独的哈希。
因此,这意味着哈希冲突
将
如果我们继续用新字符串填充字典(最终)。即使字典为每个哈希代码创建一个bucket,多个字符串也将进入同一个bucket,因为“hash space”小于“string space”。
最坏的情况似乎是
o(n)
用于访问或更新值,使用
n
是字典中的键数。使用python的内置字符串散列,不可能在最大长度为15的两个不同字符串上有相同的散列,最坏的情况是
O(1)
对吧?
它是
O(1)
但由于另一个原因。因为字符串的数量最多有15个字符,这意味着可能的字符串(因此是键)的数量是
固定的
. 例如,ASCII可打印密钥的数量固定为我们上面推导的数字(5.47×10
二十九
)是的,我们可以使用Unicode,这将大大增加键的数量,但它仍然是有限的(大约是5.06×10
九十
)
这意味着
上界
n
因此没有真正的
副症状复杂性
. 即使我们设法生成所有这些字符串,并且在最坏的情况下,这些字符串都映射到相同的哈希代码,因此都存储在同一个bucket中,它仍然是恒定时间,处理器在bucket上迭代将非常困难,但它仍然是恒定的:最多5.06×10
九十
迭代。