Python 中set
,dict
都是基于哈希表的数据结构,这两个数据结构有着广泛的应用。因此很有必要弄懂哈希表的原理。
数组和链表是数据结构的两大基石,这个在前面我们多次提到过。哈希表的实现也正是基于数组和链表。
哈希表最大特点O(1)时间内确定某元素是否位于容器中。下面探讨它是如何基于数组和链表实现的。
O(1)内确定元素在不在的实现原理,一句话总结:
通过一种方法将元素值转化为数组的index,如果index位置处为None
则不存在,不为None
则表明存在。
创建如下一个数组,长度为9
:
现在想把python
字符串存储到数组中,哈希表的一种做法如下:
python
存储到数组索引2处因此,判断字符串python
是否位于数组中时,
只需重复上面的先hash再取余,检查索引2处是否为None,故时间复杂度为O(1).
当存储10时,如上相同的存储原理,计算后等于索引2,但是2处已经有数据,
此时发生哈希冲突:
其中一种解决方法,在索引2处建立链表,链接到已有数据尾部:
本文分享自 程序员郭震zhenguo 微信公众号,前往查看
如有侵权,请联系 cloudcommunity@tencent.com 删除。
本文参与 腾讯云自媒体同步曝光计划 ,欢迎热爱写作的你一起参与!