哈希表与哈希函数
哈希查找因使用哈希 (Hash) 函数而得名，哈希函数又叫散列函数，它是一种能把关键字映射成记录存贮地址的函数。
1.哈希表
①它是一种能把关键字映射成记录存贮地址的函数。
②假定数组 HT[0 ～ m-1] 为存贮记录的地址空间， m 为表长，哈希函数 H 以记录的关键字 K 为自变量，计算出对应的函数值 H(K) ，并以它作为关键字 K 所标识的记录在表 HT 中的 ( 相对 ) 地址或索引号，这样产生的记录表 HT 叫做对应于哈希函数 H 的哈希表。
③简言之，在哈希表中，关键字为 K 的记录，存贮在 HT[H(K)] 位置。
④哈希函数值 H(K) 称为 K 的哈希地址或散列地址。
3、哈希表的冲突现象
（1）冲突
不同的关键字值，具有相同的哈希地址，因而被映射到同一表位置上。该现象称为冲突(Collision)或碰撞。
【例】上图中的k2≠k5，但h(k2)=h(k5)，故k2和K5所在的结点的存储地址相同。
（2）安全避免冲突的条件
如何避免冲突发生，则取决于哈希函数的构造。
使散列地址均匀地分布在哈希表的整个地址区间内，这样可以避免或减少发生冲突。
哈希函数的构造，与关键字的长度、哈希表的大小、关键字的实际取值状况等许多因素有关，而且有的因素事前不能确定。所以，避免冲突这并非是件容易做到的事。
（3）冲突不可能完全避免
由于关键字的值域往往比哈希表的个数大的多，所以哈希函数是一种压缩映射，碰撞是难免的。
【例】存贮 100 个学生记录，尽管安排 120 个地址空间，但由于学生名 ( 假设不超过 10 个英文字母 ) 的理论个数超过 2610 ，要找到一个哈希函数把 100 个任意的学生名映射成 [0 ， 119] 内的不同整数，实际上是不可能的。
注意：问题在于一旦发生了冲突应如何处理。
构造哈希表
构造哈希函数的方法很多，这里只介绍一些常用的，计算简便的方法。
1.平方取中法
算出关键字值的平方，再取其中若干位作为哈希函数值 ( 散列地址 ) 。
【例】假定表中各关键字是由字母组成的，用二位数字的整数 01 ～ 26 表示对应的 26 个英文字母在计算机中的内部编码，则使用平方取中法计算 KEYA ， KEYB ， AKEY ， BKEY 的散列地址可得：
关键字 K K 的内部编码 K 2 H(K)
KEYA 11052501 122157778355001 778
KEYB 11052502 122157800460004 800
AKEY 01110525 001233265775625 265
BKEY 02110525 004454315775625 315
平方之后，取左起第 7 ～ 9 位作为散列地址。
2.除留余数法
这种方法是用模运算 (%) 得到的。设给出的关键字值为 K ，存储区单元数为 m ，则用一个小于 m 的质数 P 去除 K ，得到的余数为 R ，即： R ＝ K % P 。如果 R 落在存储区地址范围内，则 R 就取为哈希函数值 ( 散列地址 ) ；否则，再用一个线性数求出哈希函数值。
【例】有一组关键字从 000001 到 859999 ，指定的存储区地址为 1000000 ～ 1005999 ，即 m ＝ 6000 ，可选 P ＝ 599 ，若要转换关键字 K ＝ 172148 ，则有：
R ＝ 172148 % 599 ＝ 4176
因 R 不在指定的地址范围内，所以，取哈希函数为：
H(K) ＝ 1000000 ＋ R
故有：
H(K) ＝ H(172148) ＝ 1004176
这样就把关键字 K 直接转换成存储地址了。
3.数字分析法
对各个关键字内部代码的各个码位进行分析。假设有 n 个 d 位的关键字，使用 s 个不同的符号 ( 如，对于十进制数，每一位可能出现的符号有 10 个，即 0 、 1 、 2 、…、 9) ，这 s 个不同的符号在各位上出现的频率不一定相同，它们可能在某些位上分布比较均匀，即每一个符号出现的次数都接近 n/s 次；而在另一些位上分布不均匀。这时，选取其中分布比较均匀的某些位作为哈希函数值 ( 散列地址 ) ，所选取的位数应视存储区地址范围而定，这就是数字分析法。
注意：
这种方法适合于关键字值中各位字符分布为已知的情况。
例如，给定一组关键字：
K 1 ： 542482241
K 2 ： 542813678
K 3 ： 532228171
K 4 ： 542389671
K 5 ： 542541577
K 6 ： 542985376
K 7 ： 542193552
这里 n ＝ 7 ； d ＝ 9 ； s ＝ 10 。为了衡量各位上 s 个字符分布的均匀度，可采用度量标准： 式中 a ik 表示第 i 个字符在第 k 位上出现的 (k ＝ 1 ， 2 ，…， d) 次数。λ k 值越小，可认为分布越均匀。这里，自左向右，各位上字符的分布均匀度为：
λ １ ＝ (7 － 7/10) 2 ＋ 9 × (0 － 7/10) 2 ＝ 44.1
λ ２ ＝ 44.1
λ ３ ＝ 44.1
λ ４ ＝ 7 × (1-7/10) 2 ＋ 3 × (0 － 7/10) 2 ＝ 2.1
λ ５ ＝ 4 × (1-7/10) 2 ＋ (3 － 7/10) 2 ＋ 5 × (0-7/10) 2 ＝ 8.1
λ ６ ＝ 5 × (1-7/10) 2 ＋ (2 － 7/10) 2 ＋ 4 × (0-7/10) 2 ＝ 4.1
λ ７ ＝ 3 × (1-7/10) 2 ＋ 2 × (2 － 7/10) 2 ＋ 5 × (0-7/10) 2 ＝ 6.1
λ ８ ＝ 2 × (1-7/10) 2 ＋ (5 － 7/10) 2 ＋ 7 × (0-7/10) 2 ＝ 22.1
λ ９ ＝ 4 × (1-7/10) 2 ＋ (3 － 7/10) 2 ＋ 5 × (0-7/10) 2 ＝ 8.1
假定存储区地址为 000 ～ 999 ，则应取关键字的第 4 、 6 、 7 位作为哈希函数值 ( 散列地址 ) ，它们分别为 422 、 836 、 281 、 396 、 515 、 953 和 135 。由于数字分析法需预先知道各位上字符的分布情况，这就大大限制了它的实用性。
构造哈希函数除了上面介绍的几种常用方法外，还有截段法，即截取关键字中的某一段数码作为哈希函数；分段迭加法，即把关键字的机内代码分成几段，再进行迭加 ( 可以是算术加，也可以是按位加 ) 得到哈希函数值。对于各种构造哈希函数的方法，很难一概而论地评价其优劣，任何一种哈希函数都应当用实际数据去测试它的均匀性，才能做出正确的判断和结论。
解决冲突的主要方法
虽然我们不希望发生冲突，但实际上发生冲突的可能性仍是存在的。当关键字值域远大于哈希表的长度，而且事先并不知道关键字的具体取值时。冲突就难免会发生。另外，当关键字的实际取值大于哈希表的长度时，而且表中已装满了记录，如果插入一个新记录，不仅发生冲突，而且还会发生溢出。因此，处理冲突和溢出是哈希技术中的两个重要问题。
1、开放定址法
用开放定址法解决冲突的做法是：当冲突发生时，使用某种探查(亦称探测)技术在散列表中形成一个探查(测)序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址(即该地址单元为空)为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探查到开放的地址则表明表中无待查的关键字，即查找失败。
注意：
①用开放定址法建立散列表时，建表前须将表中所有单元(更严格地说，是指单元中存储的关键字)置空。
②空单元的表示与具体的应用相关。
按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、线性补偿探测法、随机探测等。
（1）线性探查法(Linear Probing)
该方法的基本思想是：
将散列表T[0..m-1]看成是一个循环向量，若初始探查的地址为d(即h(key)=d)，则最长的探查序列为：
d，d+l，d+2，…，m-1，0，1，…，d-1
即:探查时从地址d开始，首先探查T[d]，然后依次探查T[d+1]，…，直到T[m-1]，此后又循环到T[0]，T[1]，…，直到探查到T[d-1]为止。
探查过程终止于三种情况：
(1)若当前探查的单元为空，则表示查找失败（若是插入则将key写入其中）；
(2)若当前探查的单元中含有key，则查找成功，但对于插入意味着失败；
(3)若探查到T[d-1]时仍未发现空单元也未找到key，则无论是查找还是插入均意味着失败(此时表满)。
利用开放地址法的一般形式，线性探查法的探查序列为：
hi=(h(key)+i)％m 0≤i≤m-1 //即di=i
用线性探测法处理冲突，思路清晰，算法简单，但存在下列缺点：
① 处理溢出需另编程序。一般可另外设立一个溢出表，专门用来存放上述哈希表中放不下的记录。此溢出表最简单的结构是顺序表，查找方法可用顺序查找。
② 按上述算法建立起来的哈希表，删除工作非常困难。假如要从哈希表 HT 中删除一个记录，按理应将这个记录所在位置置为空，但我们不能这样做，而只能标上已被删除的标记，否则，将会影响以后的查找。
③ 线性探测法很容易产生堆聚现象。所谓堆聚现象，就是存入哈希表的记录在表中连成一片。按照线性探测法处理冲突，如果生成哈希地址的连续序列愈长 ( 即不同关键字值的哈希地址相邻在一起愈长 ) ，则当新的记录加入该表时，与这个序列发生冲突的可能性愈大。因此，哈希地址的较长连续序列比较短连续序列生长得快，这就意味着，一旦出现堆聚 ( 伴随着冲突 ) ，就将引起进一步的堆聚。
（2）线性补偿探测法
线性补偿探测法的基本思想是：
将线性探测的步长从 1 改为 Q ，即将上述算法中的 j ＝ (j ＋ 1) % m 改为： j ＝ (j ＋ Q) % m ，而且要求 Q 与 m 是互质的，以便能探测到哈希表中的所有单元。
【例】 PDP-11 小型计算机中的汇编程序所用的符合表，就采用此方法来解决冲突，所用表长 m ＝ 1321 ，选用 Q ＝ 25 。
（3）随机探测
随机探测的基本思想是：
将线性探测的步长从常数改为随机数，即令： j ＝ (j ＋ RN) % m ，其中 RN 是一个随机数。在实际程序中应预先用随机数发生器产生一个随机序列，将此序列作为依次探测的步长。这样就能使不同的关键字具有不同的探测次序，从而可以避免或减少堆聚。基于与线性探测法相同的理由，在线性补偿探测法和随机探测法中，删除一个记录后也要打上删除标记。
2、拉链法
（1）拉链法解决冲突的方法
拉链法解决冲突的做法是：将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为m，则可将散列表定义为一个由m个头指针组成的指针数组T[0..m-1]。凡是散列地址为i的结点，均插入到以T[i]为头指针的单链表中。T中各分量的初值均应为空指针。在拉链法中，装填因子α可以大于1，但一般均取α≤1。
【例】设有 m ＝ 5 ， H(K) ＝ K mod 5 ，关键字值序例 5 ， 21 ， 17 ， 9 ， 15 ， 36 ， 41 ， 24 ，按外链地址法所建立的哈希表如下图所示：
（2）拉链法的优点
与开放定址法相比，拉链法有如下几个优点：
①拉链法处理冲突简单，且无堆积现象，即非同义词决不会发生冲突，因此平均查找长度较短；
②由于拉链法中各链表上的结点空间是动态申请的，故它更适合于造表前无法确定表长的情况；
③开放定址法为减少冲突，要求装填因子α较小，故当结点规模较大时会浪费很多空间。而拉链法中可取α≥1，且结点较大时，拉链法中增加的指针域可忽略不计，因此节省空间；
④在用拉链法构造的散列表中，删除结点的操作易于实现。只要简单地删去链表上相应的结点即可。而对开放地址法构造的散列表，删除结点不能简单地将被删结点的空间置为空，否则将截断在它之后填人散列表的同义词结点的查找路径。这是因为各种开放地址法中，空地址单元(即开放地址)都是查找失败的条件。因此在用开放地址法处理冲突的散列表上执行删除操作，只能在被删结点上做删除标记，而不能真正删除结点。
（3）拉链法的缺点
拉链法的缺点是：指针需要额外的空间，故当结点规模较小时，开放定址法较为节省空间，而若将节省的指针空间用来扩大散列表的规模，可使装填因子变小，这又减少了开放定址法中的冲突，从而提高平均查找速度。
(mikenoodle) |
