通俗理解 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处建立链表，链接到已有数据尾部：