社区所有版块导航
Python
python开源   Django   Python   DjangoApp   pycharm  
DATA
docker   Elasticsearch  
aigc
aigc   chatgpt  
WEB开发
linux   MongoDB   Redis   DATABASE   NGINX   其他Web框架   web工具   zookeeper   tornado   NoSql   Bootstrap   js   peewee   Git   bottle   IE   MQ   Jquery  
机器学习
机器学习算法  
Python88.com
反馈   公告   社区推广  
产品
短视频  
印度
印度  
Py学习  »  Python

python dictionary get()update()的时间复杂性始终为o(1)?

JnB • 8 年前 • 1481 次点击  

如果我只使用最大长度为15的字符串作为Python中字典的键,是否不可能发生任何冲突?

最坏的情况似乎是访问或更新值的O(N),其中N是字典中的键数。使用python的内置字符串散列,不可能在最大长度为15的两个不同字符串上使用相同的散列,最坏的情况是o(1),对吗?

还是我理解错误?

事先谢谢。

Python社区是高质量的Python/Django开发社区
本文地址:http://www.python88.com/topic/30675
文章 [ 1 ]  |  最新文章 8 年前
Willem Van Onsem
Reply   •   1 楼
Willem Van Onsem    8 年前

如果我只使用最大长度为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 九十 迭代。