Python数据结构13：散列（哈希）表，完美散列函数，解决冲突方法，开放寻址，负载因子，平均查找次数_python 散列的实现

散列表是用于查找数据的，它的算法复杂度为O(1)

散列：用数据项的值确定它的位置

1. 散列表

散列表是一种数据集，它的存储方式便于快速查找。

散列表的每一个存储位置，叫做槽(slot)，用于保存数据项，每个槽的名字唯一。

如 一个有11个槽的散列表
槽的名字依次为：0，1，2，3，4，5，6，7，8，9，10，11

每个槽的初始值为None

2. 散列函数

$$槽名=散列函数（数据项）$$

例如，常用的求余数散列函数：数据项除以散列表大小，得到的余数就是槽号。

例如：
h(item) = item % 11
散列表共有 11 个槽
对于 item表 [54, 26, 93, 17, 77, 31]的槽号为[10, 4, 5, 6, 0, 9]

2.1 负载因子

负载因子就是使用了的槽占总槽的比例。
上述的item表共占用了 11个槽里面的6个槽。
负载因子就是 $\frac{6}{11}$。

2.2 查找操作

查找某个值是否在表中，只需要计算这个值的哈希值，检测对应的槽中是否有这一项即可。

代码如下：

the_list = [54, 26, 93, 17, 77, 31]
num_of_hash_slots = 11  # 定义哈希表的大小


def create_hash_slots(a_list):
    slots = [0] * num_of_hash_slots  # 创建一个全0的hash表
    for item in a_list:
        slot = item % num_of_hash_slots  # 求每一个数要放的槽的位置
        slots[slot] = item
    return slots


the_hash_slots = create_hash_slots(the_list)
print(the_hash_slots)


def search_item(item):  # 查找item是不是在哈希表里
    the_position = item % num_of_hash_slots
    if the_hash_slots[the_position] != 0:
        return the_position
    else:
        return False


print(search_item(26))  # 打印出来的就是查找的这个项的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

2.3 哈希表的冲突

对于上述的散列函数，当44和77都要保存到哈希表当中时，他俩的余数都是0，都要分配到0号槽中，这就是冲突collision。

3. 完美散列函数

如果一个散列函数把一组数据项中的每一个数据项都映射到不同的槽中，这个散列函数就是完美散列函数。

获得完美散列函数的一个途径就是扩大散列表的容量，让所有可能出现的数据项都能占据不同的槽。但当可能出现的数据项特别多时，这并不使用。

因此，能做到冲突最少（近似完美）、计算难度低（额外开销小）、充分分散数据项（节约空间）就可以认定为好的散列函数。

4. 散列函数设计

4.1 折叠法

将数据项按照位数分为若干段，再将几段数字相加，最后对散列表大小求余，得到散列值

例如 电话号 62767255

将号码分为 两位两位的 四段(62, 76, 72, 55)
相加 62 + 76 + 72 + 55 = 265
散列表包含 11个槽， 265 % 11 = 1
所以h(62767255) = 1

隔数反转：
(62, 76, 72, 55) 隔数反转后 变成 (62, 67,72 , 55)
相加（62+67+72+55=256）
256 % 11 = 3
h’(62767255) = 3
虽然隔数反转从理论上看来毫无必要，但这个步骤确实为折叠法得到散列函数提供了一种微调手段，以便更好符合散列特性

4.2 平方取中法

平方取中法，首先将数据项做平方运算，然后取平方数的中间两位，再对散列表的大小求余

例如，对44散列
44 * 44 = 1936
取中间的93
93 % 11 = 5
h(44) = 5

4.3 非数项

对非数字的数据项进行散列，把字符串中的每个字符看作ASCII码即可

如 cat, ord(‘c’) == 99, ord(‘a’) == 96, ord(‘t’) == 116
再相加
cat == 99 + 96 +116 = 312
312 % 11 = 4

这种设计有一个缺陷，就是变位词的散列值相同，如act和cat的散列值相同，为了防止这一点，可以将字符串所在的位置作为权重因子，乘以ord值

c的位置是1，a的位置是2，t的位置是3

cat = 99 * 1 + 96 * 2 + 116 * 3 = 641
641 mod 11 = 3

我们还可以设计出更多的散列函数方法，但要坚持的一个基本出发点是，散列函数不能成为存储过程和查找过程的计算负担。如果散列函数设计太过复杂，去花费大量
的计算资源计算槽号。可能还不如简单地进行顺序查找或者二分查找。那就失去了散列本身的意义。

5. 冲突解决方案

如果两个数据项被散列映射到同一个槽，就发生了冲突，把第二个数据项放到合适的槽中，就叫做解决冲突。

如果说散列函数是完美的，那就不会有散列冲突，但完美散列函数常常是不现实的。因此我们需要有合适的解决冲突的方案。

5.1 开放定址 open addressing

给冲突的数据项再找一个开放的空槽来保存。

这种寻找空槽的技术就是开放定址。

5.1.1 线性探测 Linear Probing

最简单的开放定址就是从冲突的槽开始往后扫描，直到碰到一个空槽，如果到散列表尾部还未找到，则从首部接着扫描。

这种向后逐个槽寻找的方法则是开放定址技术中的“线性探测linear probing”。

例如： 我们已有这个散列表

现在往里面插入44，55，20
44 mod 11 = 0,
55 mod 11 = 0,
20 mod 11 = 9
在0这个位置已经有77了，所以44和55都插不进去
从0往后找，发现1为空，插入44

继续找发现2为空，插入55

在9这个位置已经有31了，向后找，10不为空，到头了，从头再找，0，1，2都不为空，直到3为空，插入20

查找使用了线性探测的散列表时，同样需要遵循这个规则，如果在散列位置没有找到查找项的话，就必须向
后做顺序查找，直到找到查找项，或者碰到空槽（查找失，败）。

加上线性探测的代码：

the_list = [54, 26, 93, 17, 77, 31]
num_of_hash_slots = 11  # 定义哈希表的大小
slots = [None] * num_of_hash_slots  # 创建一个全0的hash表


def create_hash_slots(a_list):
    for item in a_list:
        slot = item % num_of_hash_slots  # 求每一个数要放的槽的位置
        while slots[slot] is not None:  # 开放定址线性探测，遇到冲突的时候依次往后放
            if slot == num_of_hash_slots - 1:
                slot = 0
            else:
                slot += 1
            print(slot)
        slots[slot] = item

    return slots


the_hash_slots = create_hash_slots(the_list)
print(the_hash_slots)
insert_list = [44, 55, 20]
the_hash_slots = create_hash_slots(insert_list)
print(the_hash_slots)


def search_item(item):  # 查找item是不是在哈希表里
    the_position = item % num_of_hash_slots
    if the_hash_slots[the_position] != 0:
        return the_position
    else:
        return False


print(search_item(26))  # 打印出来的就是查找的这个项的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

5.1.2 线性探测的改进

线性探测法的 一个缺点是有聚集 （clustering）的趋势

如果同一个槽冲突的数据项较多的话，这些数据项就会在槽附近聚集起来

从而连锁式影响其它数据项的插入

就比如上面的例子中， 77，44，55聚集在0后面，影响了20的插入，20需要找很久，才找到合适的位置。

将逐个探测的方法改为跳跃探测，下图是“+3”探测插入44、55、20

跳跃探测的代码，step可以指定

the_list = [54, 26, 93, 17, 77, 31]
num_of_hash_slots = 11  # 定义哈希表的大小
slots = [None] * num_of_hash_slots  # 创建一个全0的hash表
step = 3  # 跳跃式探测跳跃的步数


def create_hash_slots(a_list):
    for item in a_list:
        slot = item % num_of_hash_slots  # 求每一个数要放的槽的位置
        while slots[slot] is not None:  # 开放定址跳跃探测，遇到冲突的时候从第三个开始往后放
            if slot + step >= num_of_hash_slots:
                slot = slot + step - num_of_hash_slots
            else:
                slot += 3
            print(slot)
        slots[slot] = item

    return slots


the_hash_slots = create_hash_slots(the_list)
print(the_hash_slots)
insert_list = [44, 55, 20]
the_hash_slots = create_hash_slots(insert_list)
print(the_hash_slots)


def search_item(item):  # 查找item是不是在哈希表里
    the_position = item % num_of_hash_slots
    if the_hash_slots[the_position] != 0:
        return the_position
    else:
        return False


print(search_item(26))  # 打印出来的就是查找的这个项的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

5.1.3 再散列

重新寻找空槽的过程可以用一个更为通用的“再散列rehashing”来概括

newhashvalue = rehash(oldhashvalue)
对于线性探测来说，rehash(pos) = (pos+ 1) mod sizeoftable
“+3”的跳跃式探测则是：rehash(pos) = (pos+ 3) mod sizeoftable
跳跃式探测的再散列通式是：rehash(pos) = (pos+skip) mod sizeoftable

跳跃式探测中，需要注意的是skip的取值，不能被散列表大小整除，否则会产生周期，造成很多空槽永远无法探测到一个技巧是，把散列表的大小设为素数，如例子的11

5.1. 二次探测 quadratic probing

不再固定skip的值，而是逐步增加skip值，如1、3、5、7、9， 这样槽号就会是原散列值以平方数增加：h, h+1, h+4, h+9, h+16…

5.2 数据项链 Chaining

与开放定址不同，数据项链的散列表中，一个槽不止能存一个数据项，而是存数据项的集合。冲突发生时仍然存在那个槽里就行了。

查找某一个数据项时，就查找对应的槽里的数据项集合。如果冲突太多的话，查找的时间也会很长

the_list = [54, 26, 93, 17, 77, 31]
num_of_hash_slots = 11  # 定义哈希表的大小
slots = [None] * num_of_hash_slots  # 创建一个全[]的hash表
for i in range(num_of_hash_slots):
    slots[i] = []
step = 3  # 跳跃式探测跳跃的步数


def create_hash_slots(a_list):
    for item in a_list:
        slot = item % num_of_hash_slots  # 求每一个数要放的槽的位置
        slots[slot].append(item)
    return slots


the_hash_slots = create_hash_slots(the_list)
print(the_hash_slots)
insert_list = [44, 55, 20]
the_hash_slots = create_hash_slots(insert_list)
print(the_hash_slots)


def search_item(item):  # 查找item是不是在哈希表里
    the_position = item % num_of_hash_slots
    if item in the_hash_slots[the_position]:  # 判断查找项是不是在列表中
        return the_position
    else:
        return False


print(search_item(44))  # 打印出来的就是查找的这个项的位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

6. 散列算法分析

散列在最好的情况下，可以提供O(1)常数级时间复杂度的查找性能。由于散列冲突的存在，查找比较次数就没有这么简单。

评估散列冲突的最重要信息就是负载因子λ，一般来说：
如果λ较小，散列冲突的几率就小，数据项通常会保存在其所属的散列槽中

如果λ较大，意味着散列表填充较满，冲突会越来越多，冲突解决也越复杂，也就需要更多的比较来找到空槽；如果采用数据链的话，意味着每条链上的数据项增多

如果采用线性探测的开放定址法来解决冲突（λ在0~1之间）

成功的查找，平均需要比对次数为：$\frac{1}{2}(1+\frac{1}{1-\lambda })$
失败的查找，平均需要比对次数为：$\frac{1}{2}(1+(\frac{1}{1-\lambda }{)}^2)$

如果采用数据链来解决冲突（λ可大于1）
成功的查找，平均需要比对次数为：1+λ/2
不成功的查找，平均比对次数为：λ

参考文献

本文的知识来源于B站视频 【慕课+课堂实录】数据结构与算法Python版-北京大学-陈斌-字幕校对-【完结！】，是对陈斌老师课程的复习总结