浅谈Python中字典和散列表以及散列冲突的解决
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了浅谈Python中字典和散列表以及散列冲突的解决,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2434字,纯文字阅读大概需要4分钟。
内容图文
![浅谈Python中字典和散列表以及散列冲突的解决](/upload/InfoBanner/zyjiaocheng/429/0088885f6df04520a755968c271eb6dc.jpg)
Python 用散列表来实现 dict。
散列表其实是一个稀疏数组(总是有空白元素的数组称为稀疏数组)。在一般书中,散列表里的单元通常叫做表元(bucket)。在 dict 的散列表当中,每个键值对都占用一个表元,每个表元都有两个部分,一个是对键的引用,一个是对值的引用。因为每个表元的大小一致,所以可以通过偏移量来读取某个表元。
Python会设法保证大概还有三分之一的表元是空的,当快要达到这个阀值的时候,会进行扩容,将原散列表复制到一个更大的散列表里。
如果要把一个对象放入到散列表里,就先要计算这个元素键的散列值。这就要求键(key)必须是可散列的。
一个可散列的对象必须满足以下条件:
支持 hash() 函数,并且通过 __hash__() 方法所得到的散列值是不变的。
支持通过 __eq__() 方法来检测相等性。
若 a == b 为真,则 hash(a) == hash(b) 也为真。
下面主要来说明一下散列表的算法。
为了获取键
search_key 所对应的值 search_value,python 会首先调用 hash(search_key) 计算
search_key
的散列值,把这个值最低的几位数字当作偏移量,在散列表里查找表元(具体取几位,得看当前散列表的大小)。若找到的表元是空的,则抛出 KeyError
异常;若不为空,则表元里会有一对 found_key:found_value,检验 search_key 和 found_key
是否相等,若相等,则返回 found_value。若不相等,这种情况称为散列冲突。
为了解决散列冲突,算法会在散列值中另外再取几位,然后用特殊的方法处理一下,把得到的新数值作为偏移量在散列表中查找表元,若找到的表元是空的,则同样抛出 KeyError 异常;若非空,则比较键是否一致,一致则返回对应的值;若又发现散列冲突,则重复以上步骤。
添加新元素跟上面的过程几乎一样,只不过在发现空表元的时候会放入这个新元素,不为空则为散列重复,继续查找。
当往 dict 里添加新元素并且发生了散列冲突的时候,新元素可能会被安排存放到另一个位置。于是就会发生下面的情况:dict([key1, value1], [key2, value2]) 和 dict([key2, value2], [key1, value1]) 两个字典,在进行比较的时候是相等的,但如果 key1 和 key2 散列冲突,则这两个键在字典里的顺序是不一样的。
无论何时,往 dict 里添加新的键,python 解析器都可能做出为字典扩容的决定。扩容导致的结果就是要新建一个更大的散列表,并把字典里已有的元素添加到新的散列表里。这个过程中可能发生新的散列冲突,导致新散列表中键的次序变化。如果在迭代一个字典的同时往里面添加新的键,会发生什么?不凑巧扩容了,不凑巧键的次序变了,然后就 orz 了。
由于散列表必须是稀疏的,这导致它在空间上的消耗必然要大很多,这是典型的空间换时间。
以上就是浅谈Python中字典和散列表以及散列冲突的解决的详细内容,更多请关注Gxl网其它相关文章!
内容总结
以上是互联网集市为您收集整理的浅谈Python中字典和散列表以及散列冲突的解决全部内容,希望文章能够帮你解决浅谈Python中字典和散列表以及散列冲突的解决所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。