python中字典和集合内部用的就是哈希表(散列表)所以他们的查找速度非常快。
数组可以迅速通过下标去查找,O(1);但是删除数组元素就要向前依次移动其他元素,所以O(n);
循环双端链表在知道一个节点的情况下迅速删除它,O(1),但是它的节点查找又成了 O(n),比较慢。
扩展:
给元素一个逻辑下标,这样在存储一个元素的时候,通过这个元素计算一个逻辑下标,这样就可以迅速通过这个下标找到这个元素,这也就是哈希表的工作原理。
举例:
有个长度为13个元素的数组,定义一个哈希函数
h(key) = key % M
使用取余运算是的h(key)的结果不会超过数组长度的下标,再来分别插入以下元素:
765, 431, 96, 142, 579, 226, 903, 388
先来计算下它们应用哈希函数后的结果:
M = 13
h(765) = 765 % M = 11
h(431) = 431 % M = 2
h(96) = 96 % M = 5
h(142) = 142 % M = 12
h(579) = 579 % M = 7
h(226) = 226 % M = 5
h(903) = 903 % M = 6
h(388) = 388 % M = 11
可以看到 96 和 226,以及 765 和 388 产生了哈希冲突。
下图模拟哈希表的插入过程(链接法):
![](https://img.laitimes.com/img/_0nNw4CM6IyYiwiM6ICdiwiI9s2RkBnVHFmb1clWvB3MaVnRtp1XlBXe0xCM581dvRWYoNHLwEzX5xCMx8FesU2cfdGLwATMfRHLGZkRGZkRfJ3bs92YskmNhVTYykVNQJVMRhXVEF1X0hXZ0xiNx8VZ6l2cssmch1mclRXY39CXldWYtlWPzNXZj9mcw1ycz9WL49zZuBnLwUjMwkDNzkTOzUzN0MTNx8CXwIDOwgTMwIzLcNXZnFWbp9CXvwVbvNmLvR3YxUjL0M3Lc9CX6MHc0RHaiojIsJye.png)
当出现哈希冲突的时候,就把这个位置当成链接表,226就往这个链接表里面插入,所以用链接法解决哈希冲突,缺点也很明显,如果哈希冲突的比较多,导致这个链过长,这时去查找元素的时候,没法通过O(1)时间去定位,就发生了时间复杂度退化的情况。
另外一种方法就相对较好:开放寻址法
它的思想比较简单,当一个槽被占用的时候,采用一种方式寻找下一个可用的槽,这里的槽指的是数组中的一个位置,根据找下一个槽的方式不同分为几种:
(1)线性探查:当一个槽被占用,找下一个可用的槽
h(k, i) = (h'(k) +i) % m, i=0,1,2,....,m-1
#k 是插入元素的key值
#i 是位置
#h'(k) + i 是对M取模
#m-1 是槽的长度
(2)2次探查:【python内置使用的就是二次探查】
当一个槽被占用时,以2次方作为偏移量
h(k,i)=(h′(k)+c1+c2i2)%m,i=0,1,...,m−1
选取c1,c2两个常数,之前计算得到的一个哈希表的位置(h'(k))之后,加上c1和c2i2的和,对m取模,以2次方作为偏移量。
(3)双重散列:重新计算哈希结果
h(k,i)=(h1(k)+ih2(k))%m
这种方法根据哈希函数进行二次哈希,用的很少
python实际上使用的是二次探查法:
h(k, i) = (home +i2) % m
意思是如果遇到了冲突,就在原始计算的位置上不断加上i的平方。之后再对m使用取模。
下面的代码模拟了计算逻辑下标的过程:
inserted_index_set = set()
M = 13
def h(key, M=13):
return key % M
to_insert = [765, 431, 96, 142, 579, 226, 903, 388]
for number in to_insert:
index = h(number)
first_index = index
i = 1
while index in inserted_index_set: #如果计算发现已经占用,继续计算得到下一个可用槽的位置
print('\th({number}) = {number} % M = {index} collision'.format(number=number, index=index))
index = (first_index + i*i) % M #根据二次方探查的公式重新计算下一个需要插入的位置
i += 1
else:
print('h({number}) = {number} % M = {index}'.format(number=number, index=index))
inserted_index_set.add(index)
这段代码输出的结果如下:
h(765) = 765 % M = 11
h(431) = 431 % M = 2
h(96) = 96 % M = 5
h(142) = 142 % M = 12
h(579) = 579 % M = 7
h(226) = 226 % M = 5 collision
h(226) = 226 % M = 6
h(903) = 903 % M = 6 collision
h(903) = 903 % M = 7 collision
h(903) = 903 % M = 10
h(388) = 388 % M = 11 collision
h(388) = 388 % M = 12 collision
h(388) = 388 % M = 2 collision
h(388) = 388 % M = 7 collision
h(388) = 388 % M = 1
遇到冲突之后会重新计算,每个待插入元素最终的下标就是:
h(765) => 11
h(431) => 2
h(96) => 5
h(142) => 12
h(579) => 7
h(226) => 5(collision) => 6
h(903) => 6(collision) => 7(collision) => 10
h(338) => 11(collision) => 12(collision) => 2(collision) => 7(collision) => 1
详细解释如下:
h(226)的逻辑下标是5,冲突了,所以5+12=6,查看6的位置为空,OK,找到位置了;
h(903)的逻辑下标是6,冲突了,所以6+12=7,7冲突,继续,6+22=10,10的位置为空,找到位置了;
h(388)的逻辑下标是11,冲突了,所以11+12=12,也冲突,11+22=15,15%13=2,2冲突,继续,11+32= 20,20%13=7,7冲突,继续,11+42=27,27%13=1, 1的位置为空,找到位置了;