注

        本笔记参考：《数据结构（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的最大质数。

处理冲突的方法