通俗理解 set,dict 背后的哈希表

哈希表

Python 中set,dict都是基于哈希表的数据结构,这两个数据结构有着广泛的应用。因此很有必要弄懂哈希表的原理。

哈希表

数组和链表是数据结构的两大基石,这个在前面我们多次提到过。哈希表的实现也正是基于数组和链表。

哈希表最大特点O(1)时间内确定某元素是否位于容器中。下面探讨它是如何基于数组和链表实现的。

实现原理

O(1)内确定元素在不在的实现原理,一句话总结:

通过一种方法将元素值转化为数组的index,如果index位置处为None则不存在,不为None则表明存在。

原理图解

创建如下一个数组,长度为9

现在想把python字符串存储到数组中,哈希表的一种做法如下:

  • 使用Python的hash函数,

  • 然后对数组长度取余数,得到2,

  • 最后将python存储到数组索引2处

因此,判断字符串python是否位于数组中时,

只需重复上面的先hash再取余,检查索引2处是否为None,故时间复杂度为O(1).

链表解决哈希冲突

当存储10时,如上相同的存储原理,计算后等于索引2,但是2处已经有数据,

此时发生哈希冲突:

其中一种解决方法,在索引2处建立链表,链接到已有数据尾部:

以上就是哈希表最核心知识的扼要总结。