数据结构入门7-2（散列表）_设散列表的长度为100

目录

注

散列表的基本概念

散列函数的构造方式

构造散列函数的常见方法

1. 数字分析法

2. 平方取中法

3. 折叠法

4. 除留余数法

处理冲突的方法

开放地址法

链地址法

散列表的查找

---

 

注

        本笔记参考：《数据结构（C语言版）（第2版）》

---

散列表的基本概念

        像基于线性表、数表的查找方式，往往都是以关键字的比较为基础的。这种比较方式在遇到结点数量很多的情况时就会暴露其的弊端：需要大量匹配无效结点。为此，就提出了散列查找法（哈希）的思想：将元素的存储位置和其关键字之间建立某种直接关系，即需要一种关键字到地址的直接转换方法。

散列表的术语：

        事实上，在实际应用中，不产生冲突的散列函数极为少见。这是因为散列表中的关键字的取值集合往往远大于表空间的地址集。要将大量的关键字映射到有限的地址上，难免会产生冲突。通常，散列表的映射采取一对多的方式，而为了解决冲突，一般从两个方面入手：

1. 设计一个“好”的散列函数（可以在一定程度上减少冲突）；
2. 发生冲突时，采取相应措施处理冲突。

散列函数的构造方式

构造散列表前，通常需要考虑以下因素：

1. 散列表的长度；
2. 关键字的长度；
3. 关键字的分布情况；
4. 计算散列函数所需的时间；
5. 记录的查找频率。

构造散列函数的两条原则：

    1. 函数计算简单，每个关键字只对应一个散列地址；

    2. 函数的值域需要在表长的范围内，计算出的散列地址的分布应该均匀，尽量减少冲突。

构造散列函数的常见方法

1. 数字分析法

【适用范围】

• 事先知道关键字集合；
• 每个关键字的位数比散列表的地址码位数多。

【使用方法】

        设每个关键字由x位数组成，如k₁k₂...kₓ，则可以从关键字中提取出分布较为均匀的若位作为散列地址。

【例子】

假设：

• 有80个记录，其关键字为8位十进制数；
• 散列表长度为100。

        则取关键字中的两位十进制数（两位对应100个地址）组成散列地址，下图所示是80个关键字中的一部分：

        对上述关键字全体进行分析：第①、②位分别只取“8”、“1”，第③位只取“3”或“4”，第⑧位取“2”、“5”或“7”，变化太少，无法反映位置信息。其余四位近乎随机，可将其化作散列地址（直接使用其中任意两位；或取其中两位后，与另外两位叠加、求和再舍去进位）。

---

2. 平方取中法

【适用范围】

        不能事先了解关键字的所有情况，或难以直接从关键字中找到取值较为分散的几位。

【使用方法】

        取关键字平方后的中间几位或其组合作为散列地址，使随机分布的关键字得到的散列地址也是随机的（具体的散列地址位数由表长决定）。

---

3. 折叠法

【适用范围】

• 散列地址的位数较少，而关键字的位数较多；
• 难以直接从关键字中找到取值比较分散的几位。

【使用方法】

1. 将关键字分割为位数相同的几部分（最后一部分的位数可以不同）；
2. 取这几部分的叠加和（舍去进位）作为散列地址。

折叠方式也分为两种：

【例子】

 假设：

• 散列表长度为1000；
• 关键字key = 45387765213。

        将key从左到右每3位数进行一次分割，得到：453、877、652、13。对应的两种叠加方式如图所示：

---

4. 除留余数法

【适用范围】

        适用范围广，是最常用的构造散列函数的方法。

【使用方法】

        假设散列表长度为m，选取一个数p（p ≤ m），用p去除关键字，所得余数就是散列地址，即：

    一般情况下，p可选取小于m的最大质数。

处理冲突的方法

        在实际应用中，仅靠一个“好”的散列函数是难以完全避免冲突的，此时就会需要处理冲突。下面说明几种处理冲突的方法。

        按照散列表本身组织形式的不同，可以将处理冲突的方法分为两种：开放地址法和链地址法。

开放地址法

        基本思想：把记录存储在数组中，当某一关键字key的初始散列地址H(key)与数组内现有的记录发生冲突时，采取合适的方法计算，得到另一个地址。若得到的新地址仍会冲突，则继续寻求下一个地址。

在使用这种方法时，数组的存储空间对所有元素开放，故称该方法为开放地址法。其中，进行寻找空位的过程被称为探测。

         这种方法的公式表达如下：

可知，根据增量序列的取值不同，可以分为不同的探测方法。

线性探测法

        这种探测方式将散列数组看成了一个循环表。发生冲突时，程序会查看下一个存储单元是否为空，直到最后一个存储位置。若仍未找到，将会回到表头进行寻找。若始终没有空位，则进入溢出处理。

二次探测法

伪随机探测法

【例子】

        假设散列表长度为11，散列函数H(key) = key%11 ，表中已有关键字17、60、29的记录。

        现在插入新记录，其关键字为38。由于其散列地址也是5，产生冲突，此时上述的三种探测法对应的处理如下：

        上述的几种方法都有其优缺点：线性探测法中，只要数组未满，就一定可以找到不冲突的地址，但是可能发生“二次聚集”现象。其余方法则无法保证可以找到不冲突的地址。

---

链地址法

        基本思想：把具有相同散列地址的记录放在同一个单链表中，称其为同义单链表。

【例子】

        有一组关键字为 (19, 14, 23, 1, 68, 20, 84, 27, 55, 11, 10, 79) ，散列函数为H(key) = key%13。现在使用链地址法处理冲突，则散列表形式如下：

散列表的查找

        以开放地址法（其中的线性探测法）为例，描述处理冲突的散列表的查找过程。

    散列表的创建与查找类似。

开放地址法中，散列表的存储表示如下：

#define m 20				//散列表的表长
typedef struct {
	KeyType key;			//关键字项
	InfoType otherinfo;		//其他数据项
}HashTable[m];

【参考代码：散列表的查找】

#define NULLKEY -1			//单元为空的标记
int SearchHash(HashTable HT, KeyType key)
{
	int H_0 = Hash(key);			//计算key值对应的散列地址
 
	if (HT[H_0].key == NULLKEY)		//若目标单元为空，则所查元素不存在
		return -1;
	else if (HT[H_0].key == key)	//若查找成功
		return H_0;
	else							//发生冲突的情况
	{
		for (int i = 1; i < m; i++)
		{
			int H_i = (H_0 + i) % m;	//按照线性探测法计算下一个散列地址
			if (HT[H_i].key == NULLKEY)	//若下一地址为空，所查元素不存在
				return -1;
			else if (HT[H_i].key == key)	//若找到目标元素
				return H_i;
		}
		return -1;						//若查找一轮后未找到目标元素，查找失败
	}
}

【算法分析】

        虽然散列表在关键字和存储位置之间建立了直接联系，但由于“冲突”的存在，散列表的查找仍然需要一个比较的过程。因此在衡量散列表的查找效率时，仍然可以用平均查找长度作为量度。

查找过程的比较取决于三个因素：

• 散列函数
• 处理冲突的方法
• 散列表的装填因子α：α越大，发生冲突的可能性越大。查找时进行比较的关键字的个数也越多。

  

        散列表的“好坏”首先影响冲突的频繁程度。认为：“均匀”的散列函数，对于同一组随机的关键字，其产生冲突的可能性相同。在这种条件下，不同方式处理冲突的平均查找长度如下：

        在查找概率相等的前提下，直接计算查找成功的平均查找长度可以使用以下公式：

        对应的，查找失败的平均查找长度可以使用下面的公式：