散列表是什么？

我在静态查找表与静态查找表两篇文章中表示查找表的各种结构的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系，查找的过程为给定值依次和关键字集合中各个关键字进行比较，查找的效率取决于和给定值比较的关键字个数。

用这类方法表示的查找表，其平均查找长度都不为0。不同的表示方法，其差别仅在于：关键字与给定值进行比较的顺序不同。

对于频繁比较的查找表，希望ASL = 0。只有一个方法：预先知道所查关键字在表中的位置，即要求：记录在表中的位置和其关键字之间存在一种确定的关系。

eg：为zsr追求的1000名妹子建立一张查找表，其关键字为序号，其值得范围为 xx000~xx999 (前两位是年份)。
若以下标范围为000~999的顺序表表示之，则查找过程可以简单进行为：取给定值（序号）的后三位，不需要经过比较便可直接从顺序表中找到待查关键字。

但是，对于动态查找表而言：
1）表长不确定；
2）在设计查找表的时候，只知道关键字所属的范围，而不知道确切的关键字；

因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以 f(key) 作为关键字为 key 的记录在表中的位置，通常称 f(key) 为散列函数。

散列函数的性质：

• 散列(Hash)函数是一个映像，即：将关键字的集合映射某个地址集合上，他的设置很灵活，只要这个地址集合的大小不超出允许范围内即可；
• 由于散列函数是一个压缩映像，因此，在一般情况下，很容易产生冲突的情况，即 key1 != key2 ，但是 f(key1) = f(key2)
• 很难找到一个不产生冲突的散列函数。一般情况下，只能选择恰当的散列函数，是冲突尽可能少的产生。

因此，在构造这种特殊的查找表时，除了需要选择一个好(尽可能少产生冲突)的散列函数之外，还需要一种解决冲突的方法。

散列表的定义

根据设定的散列函数 H(key) 和所选中的处理冲突的方法，将一组关键字映像到一个有限的、地址连续的地址集上，并以关键字在地址集中的“像”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“散列表”

构造散列函数的方法

对数字的关键字可有以下构造方法：
直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法

若是非数字关键字，则需先对其进行数字化处理。

1.直接定址法：散列函数为关键字的线性函数，设 H(key) = key 或 H(key) = a * key + b
此法仅适合于：地址集合的大小==关键字集合的大小

2.数字分析法：假设关键字集合中的每个关键字都是有s为有效数字组成(u1,u2,…,us)，分析关键字集中的全体，并从中提取分布均匀的若干位或他们的组合作为地址
此法仅适合于：能预先估计出全体关键字的每一位上
各种数字出现的频度

3.平法取中法：以关键字的平方值的中间几位作为存储地址。求关键字平方值的目的是扩大差别，同时平方值的中间各位又能受到整个关键字中各位的影响
此方法仅适合于：关键字中的每一位都有某些数字重复出现频度很高的现象

4.折叠法：将关键字分割成若干部分，然后取他们的叠加和为散列地址。有两种叠加处理的方法：移位叠加和间界叠加
此方法仅适合于：关键字的数字位数特别多

5.除留余数法

设定散列函数为 H(key) = key MOD p ，其中 p <= m (表长) 并且 p 应为不大于 m 的最大素数

为什么要对p加限制？
减少冲突

6.随机数法：设散列函数为 H(key) = Random(key) ，其中 Random 为伪随机函数
通常此方法用于对长度不等的关键字构造散列函数

实际造表时，采用何种构造散列函数的方法取决于建表的关键字集合的情况（包括关键字的范围与形态），总的原则是使产生冲突的可能性降到尽可能的小

处理冲突的方法

处理冲突的实际含义是：为产生冲突的地址寻找下一个散列地址

• 开放地址法
• 链地址法

1.开放定址法：为产生冲突的地址H(key)求得一个地址序列：H1,H2,…,Hs (1<=s<=m-1) ，其中 H0 = H(key) ,
Hi = (H(key) + di) MOD m , i = 1,2,…,s

对增量di有三种取法：
1）线性探测再散列：di = c i 最简单的情况，c = 1
2）平方法探测再散列：di = 1^2, -1^2, 2^2, -2^2…
3）随机探测再散列：di是一组伪随机数列，或者 di = i H2(key) (又称双散列函数探测)

eg：
关键字集合：{19,01,23,14,55,68,11,82,36}
设散列函数 H(key) = key MOD 11 (表长为11)
若采用线性探测再散列处理冲突：

1
2

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 
55  01  23  14  68  11  82  36  19

2.链地址法：将所有散列地址相同的记录都连接在同一链表中

散列表的查找

查找过程与建表过程一致。假设采用开放定址法处理冲突，则查找过程为：

对于给定值K，计算散列地址 i = H(k)
若 r[i] = NULL ，则查找不成功
若 r[i].key = K ，则查找成功
否则求下一地址 Hi ，直至
r[Hi] = NULL （查找不成功）
或 r[Hi] = K （查找成功）为止

散列表查找的分析：

从查找过程得知，散列表查找过程的平均长度实际上并不为0

绝对散列表ASL的因素：

• 选用的散列函数
• 选用的处理冲突的方法
• 散列表的饱和程度，装载因子 α = n/m 值得大小（n为记录数，m为表的长度）

一般情况下，可以认为选用的散列函数是均匀的，则在讨论ASl时可以不考虑其他因素。

因此，散列表的ASL是处理冲突方法和装载因子的函数

可以证明，查找成功时可以有一下结果（证明过程参见算法导论）

1
2
3

线性探测再散列： Snl = 1/2 * (1+1/(1-α))
随机探测再散列： Snr = -1/α * ln(1-α)
链地址法： Snc = 1 + 2/α

从以上结果可见，散列表的平均查找长度是 α 的函数，而不是 n 的函数。这说明，用散列表构造查找表时，可以选择一个适当的装填因子 α 使得ASL限定在某个范围内。

这就是所有散列表的特点

散列表的删除操作

从散列表中删除记录时，要做特殊处理，相应的，需要修改查找的算法

散列表也可以用来构造静态查找表

并且，对静态查找表，有时可以找到不发生冲突的散列函数。即此时的散列表的ASL=0，称此类散列函数为理想的散列函数