哈希表查找法

# 4. 哈希表查找法

哈希法又称散列法、杂凑法或关键字地址计算法等，相应的表称为哈希表、散列表、杂凑表等。

** 基本思想：** 根据问题中的关键字构造一个合适的函数，利用这个函数求得各记录的存储位置，然后存储；在查找时用相同的函数找其元素。即：
Addr(ai)=H(Ki)
其中：
Addr (ai) 为 ai 的存储地址
H 为散列函数
Ki 为 ai 的关键字

# 1. 概念

** 散列表（哈希表）：** 按散列存储方式构造的存储结构为散列表。
** 散列函数（哈希函数）：**H（ki），关键字与表之间的对应关系。
** 散列地址（哈希地址）：** 散列函数的值。
** 散列：** 将结点按关键字的散列地址存储到散列表中的过程，又称哈希造表。
** 同义词：**k1 ≠k2，但 H（k1）＝H（k2），即映射到同一哈希地址上的关键码 k1 和 k2 为同义词。
** 冲突：**k1 ≠k2，但 H（k1）＝H（k2），将不同的关键码映射到同一个哈希地址上，即同义词之间发生地址争夺的现象。

# 2. 构造哈希表

构造哈希函数的原则是：
①函数本身便于计算；
②计算出来的地址分布均匀，即对任一关键字 k，H (k) 对应不同地址的概率相等，目的是尽可能减少冲突。

1、直接定址法
取关键字的某个线性函数值为哈希地址。
H (key)=key 或 H (key)=a*key+b
例：H (key)= 学号 - 2020100100

2、数字分析法
如果事先知道关键字集合，并且每个关键字的位数比哈希表的地址码位数多时，可以从关键字中选出分布较均匀的若干位，构成哈希地址。
例如，有 80 个记录，关键字为 8 位十进制整数 d1d2d3…d7d8，如哈希表长度取为 100，则哈希表的地址空间为：0~99。
假设经过分析，各关键字中 d4 和 d7 的取值分布较均匀，则哈希函数为：
H (key)= H (d1d2d3…d7d8)=d4d7。
例如，H (81346532)=43，H (81301367)=06。
相反，假设经过分析，各关键字中 d1 和 d8 的取值分布极不均匀， d1 都等于 5，d8 都等于 2，此时，如果哈希函数为：H (key)= H (d1d2d3…d7d8)=d1d8，则所有关键字的地址码都是 52，显然不可取。

3．平方取中法
当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。
例如：

4. 分段叠加法
按哈希表地址位数将关键字分成位数相等的几部分（最后一部分可以较短），然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址。
具体方法有折叠法与移位法
移位法是将分割后的每部分低位对齐相加
折叠法是从一端向另一端沿分割界来回折叠（奇数段为正序，偶数段为倒序），然后将各段相加。
例如：key=12360324711202065

5. 除留求余法
哈希表长为 m，
p 为小于等于 m 的最大素数，
则哈希函数为 H(key)=key%p ，
其中 % 为模 p 取余运算。

例如，已知待散列元素为（18，75，60，43，54，90，46），表长 m=10，p=7，则有
h(18)=18 % 7=4 h(75)=75 % 7=5 h(60)=60 % 7=4 h(43)=43 % 7=1 h(54)=54 % 7=5 h(90)=90 % 7=6 h(46)=46 % 7=4
此时冲突较多。为减少冲突，可取较大的 m 值和 p 值，如 m=p=13，结果如下：
h(18)=18 % 13=5 h(75)=75 % 13=10 h(60)=60 % 13=8 h(43)=43 % 13=4 h(54)=54 % 13=2 h(90)=90 % 13=12 h(46)=46 % 13=7

6. 伪随机数法
采用一个伪随机函数做哈希函数，即 H(key)=random(key) 。

在实际应用中，应根据具体情况，灵活采用不同的方法，并用实际数据测试它的性能，以便做出正确判定。通常应考虑以下五个因素：
计算哈希函数所需的时间。
关键字的长度。
哈希表的大小。
关键字分布的情况。
记录查找的频率。

# 3. 处理冲突的方法

1. 开放定址法（open Addressing）
所谓开放定址法，即是由关键字得到的哈希地址一旦产生了冲突，就去寻找下一个空的哈希地址，只要哈希表足够大，空的哈希地址总能找到，并将数据元素存入。
Hi=(Hash(key)+di) m i=1,2,…k (k<=m-1)
其中：
Hash (key) 为哈希函数
m 为哈希表长度
di 为增量序列

增量序列，可有下列 3 种取法：
①线性探测再散列
这种方法的特点是：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。
di =1,2,3,...,m-1
②二次探测再散列
特点是：冲突发生时，在表的左右进行跳跃式探测，比较灵活。
di=1²,-1²,2²,-2²,...，k²,-k²( k<=m/2 )
③伪随机探测再散列
di＝伪随机数序列

2. 再哈希法
这种方法是同时构造多个不同的哈希函数：
Hi=RHi（key） i=1，2，…，k
当哈希地址 H1=RH1（key）发生冲突时，再计算 H2=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。

3. 链地址法 (拉链法)
基本思想是将所有哈希地址为 i 的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第 i 个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
例：
已知一组关键字（32，40，36，53，16，46，71，27，42，24，49，64），哈希表长度为 13，哈希函数为：H（key）= key %13，给出用链地址法处理冲突的结果，计算平均查找长度。如下图所示：

平均查找长度 ASL=(1*7+2*4+3*1)/12=1.5

4. 建立公共溢出区
基本思想是：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素一律填入溢出表。

# 4. 查找

哈希表的查找过程与哈希表的创建过程是一致的。假设要查找关键字为 K 的元素，则查找过程如下：
算法思想：
（1）首先计算 h0= hash（K）；
（2）如果单元 h0 为空，则所查元素不存在；
（3）如果单元 h0 中元素的关键字为 K，则找到所查元素；
（4）否则重复下述解决冲突的过程：
a. 按解决冲突的方法，找出下一个哈希地址 hi ；
b. 如果单元 hi 为空，则所查元素不存在；
c. 如果单元 hi 中元素的关键字为 K，则找到所查元素。下面以线性探测再散列为例，给出哈希表的查找算法

// 哈希表的查找算法

#define m <哈希表长度>

#define NULLKEY <代表空记录的关键字值>

typedef int KeyType; /* 假设关键字为整型 */

typedef struct{

	KeyType key;

	…… /* 记录中其它分量按需求确定 */

	……

} RecordType ;

typedef RecordType HashTable[m] ;

int HashSearch( HashTable ht, KeyType K){

	h0=hash(K);

	if (ht[h0].key==NULLKEY) return (-1);

	else if (ht[h0].key==K) return (h0);

	else{ /* 用线性探测再散列解决冲突 */

		for (i=1; i<=m-1; i++){

			hi=(h0+i) % m;

			if (ht[hi ].key==NULLKEY) return (-1);

			else if (ht[hi].key==K) return (hi);

		}

	return (-1);

	}

}

# 5. 性能分析

哈希法中影响关键字比较次数的因素有三个：
哈希函数、处理冲突的方法以及哈希表的装填因子。
哈希表的装填因子 α 的定义如下：
α= 哈希表中元素个数/哈希表的长度
α 可描述哈希表的装满程度。显然，α 越小，发生冲突的可能性越小。

以下按处理冲突的不同方法，分别列出相应的平均查找长度的近似公式：

手工计算等概率情况下查找成功的平均查找长度公式：
ASLsucc=(比较次数)/表中元素个数

手工计算在等概率情况下查找不成功的平均查找长度公式
ASLunsucc=(比较次数)/哈希函数取值个数

例子：

ASLsucc=1/12(1*7+2*4+3*1)=1.5
ASLunsucc=1/13(1*6+2*3+3*3+4)=1.9