[数据结构与算法]009.查找手机电话簿【散列表】

1. 散列表

顺序存储的结构类型需要一个一个地按顺序访问元素，当总量很大且我们所要访问的元素比较靠后时，顺序存储的结构类型性能就比较低。而散列表是一种空间换时间的存储结构，也是提升效率的一种比较常用的方式。由于它所需空间太大，所以通常需要使用者在“效率”和“占空间大小”二者之间权衡。

1.1 什么是散列表

利用字典查找汉字的过程就是散列表的思想。散列表，又叫作哈希表，是通过给定的关键字直接访问到具体对应值的数据结构。简单的说，就是把关键字映射到一个表中的位置来直接访问记录，以加快访问速度。通常把关键字称为Key，把对应的记录称为Value，把存放记录的数组叫作散列表。

1.2 散列函数

散列函数又称为哈希函数，给定一个输入 x (任何数据)，它都会算出相应的输出 H(x)(一般为数字)。散列表具有如下特征：

• 输入 x 可以是任意字符串
• 输出结果 H(x) 的长度是固定的
• 计算 H(x) 的过程是高效的
• 尽可能输入一个 x 就能得出唯一的 H(x)

散列函数之所以最终会输出数字，是因为散列函数计算出的数字需要用来做索引。

1.3 解决散列表的冲突

1.3.1 开放定址法

开放定址法就是当数据的散列地址遇到冲突，系统就会去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，系统将记录存入该散列地址。

H(i)=(H(key)+d(i)) MOD m

• key： 要存储的数据
• H(key)：散列函数
• m：散列表长度
• d(i)：增长序列
• MOD：%

其中，d(i) 有三种取法：

• 线性探测法：d(i)=1，2，3，4，…，m-1
• 平方探测法：d(i)=12，22，32，42，… 或 d(i)=-12，-22，-32，-42，…
• 伪随机探测法：d(i)=伪随机数序列

线性探测法：以线性的方式向散列表后面寻找空的存储位置，一旦找到位置就将数据放进去。

平方探测法：线性探测法有一个缺点，就是相类似的键值经常会聚集在一起。当多个数据键值类似时，它们就会聚集，会产生冲突。为了防止这样的事情发生，在线性的基础上做了改进，使用平方探测法：d(i)=1²，2²，3²，…

伪随机探测法：伪随机探测法指 d(i) 采用随机函数计算得到的。如果设置的随机种子相同，则不断调用随机数可以生成不会重复的数列。在查找时，用同样的随机种子每次得到的数据是相同的，相同的数据产生相同的d(i) ，相同的 d(i) 就会得到相同的散列地址。

1.3.2 链地址法

链地址法就是将经过散列函数得到的相同的数值（索引值）放在同一个位置，就在这个位置存储为一个单链表。用专业术语描述就是将相同的键映射到同一个位置。散列表中只存储头指针，相同的数据放到同义词子表。

对于可能会造成很多冲突的散列函数来说，链地址法提供了绝不会出现找不到地址的保障，但这种方法也带来了缺点：查找数据时增加了遍历单链表的时间。

1.3.3 再散列函数法

再散列函数法就是一开始就先设置一些散列函数（比如除留取余、平方取中、折叠等等），如果使用第一种散列函数出现冲突就改用第二种，如果第二种也出现冲突就改用第三种，一直到没有冲突为止。

虽然再散列函数法不易产生聚集，但是从步骤上看，明显增加了计算时间。

1.3.4 建立公共溢出区法

建立公共溢出区法就是将散列表分为基本表和溢出表两部分，凡是与基本表发生冲突的，都存放在溢出表中。

这种方法在查找数据时，在散列函数计算出索引位置后，先与基本表的相应位置做比较，如果相等，就查找成功；如果不相等，就到溢出表中进行顺序查找。就相对查询而言，在少量数据冲突的情况下，公共溢出区法对查找数据的速度来说是比较快的。

1.3.5 解决冲突方法的比较

元素少，用开放定址法，冲突少，速度快；元素多，用链地址法。

1.4 散列表的性能

负载因子：也称为填装因子，负载因子度量的是散列表中有多少位置是空的。

a=n/m

• a：负载因子
• n：散列表中键值的个数
• m：散列表的大小

负载因子值=1，说明每个元素都有自己的位置。
负载因子值<1，说明还有空位置。
负载因子值>1，说明位置不足，需要调整长度，增加散列表中的位置。

总结：负载因子越低，发生冲突的可能性越小，散列表的性能越高。

时间性能：在理想的情况下，散列表执行各种操作的时间都是 O(1)，也就是常量时间。即使有 1 亿条数据，它的运行时间也是相同的，所以说在各种条件相同的情况下，散列表的查询速度最快。

2. 查找手机电话簿

散列表广泛应用于查找，例如查找员工信息，学生信息，电话簿等等。下边列举如何快速查找到联系人的信息。

# 创建散列表
# TelephoneBook=dict()
# TelephoneBook={}
TelephoneBook=dict(阿美='187-6667-****',阿彪='186-****-4544',爸爸='136-9475-****',白雪='136-1231-****',陈明='178-****-9490')
print("电话薄信息如下：")
# 输出完整散列表
print(TelephoneBook)
print('')

print("查找联系人“白雪”的信息：")
# 查找白雪信息并输出
print("姓名：白雪 电话号码：",TelephoneBook['白雪'])
print('')

# 添加“彩虹”信息
TelephoneBook['彩虹']="188-****-5556"
print("添加彩虹之后的完整电话薄：")
# 输出添加之后的完整散列表
print(TelephoneBook)
print('')

# 修改“阿彪”信息
TelephoneBook['阿彪']="178-****-5555"
print("修改阿彪之后的完整电话薄：")
# 输出修改之后的完整散列表
print(TelephoneBook)
print('')

# 删除“白雪”信息
del TelephoneBook['白雪']
print("删除白雪之后的完整电话薄：")
# 输出删除之后的完整散列表
print(TelephoneBook)