1、背景

在查找的数据结构，无论是 线性表 或者 树 结构，记录在结构中的相对位置是【随机】的，和记录的关键字不存在确定关系，这类查找方法建立在“比较”的基础上。

在顺序查找中，比较的结果为 “＝” 与 “≠” 两种可能；

在折半查找、二叉排序树查找和B树查找时，比较的结果为 “<”, “＝” 和 “>” 三种可能；

【查找的效率】依赖于查找过程中进行的【比较次数】；



理想的情况是【不经过比较】，一次就可以得到记录，这就必须在记录的存储位置与它的关键字之间建立一个确定的【对应关系】，是每个关键字和结构中唯一的存储位置相对应；

因此需要根据【对应关系】找到关键字的位置，这个【对应关系】称作【哈希(Hash)函数】，按这个思想建立的表为【哈希表】；



2、哈希表

2-1、问题

1、【哈希函数】是一个映射，只要关键字经过哈希函数计算得到的值都在【哈希表长】允许范围之内即可；

2、哈希冲突：对不同的关键字可能得到同一哈希地址，这种现象称为【冲突（collision）】；

即 key1 ≠ key2，但 F(key1) = F(key2)；

一般情况，冲突只能尽可能减少，而不能完全避免；

在构建哈希表时不仅要设定“好”的哈希函数，而且要设定一种处理冲突的方法；



2-2、定义

根据设定的哈希函数F(key) 和 处理冲突的方法 将一组关键字映射到一个【有限的】【连续的】地址集上，并以关键字在地址集中的“像”作为记录在表中的存储位置，这种表称为【哈希表】；

这一映像过程称为【散列】，所得存储位置称【哈希地址】或【散列地址】；



2-3、哈希函数的构造方法

2-3-1、什么是“好”的函数？

关键字经过哈希函数得到一个随机地址，使一组关键字的哈希地址【均匀分布】在整个地址区间，从而减少冲突；



2-3-2、直接地址法

取关键字或关键字的某个线性函数值为哈希地址。即：

H(key) = key 或 H(key) = a * key + b

其中 a 和 b 为常数（这种哈希函数叫做自身函数）；



2-3-3、数字分析法

• 关键字以R为基数；

• 并且哈希表中可能出现的【关键字事先知道】；

• 则可取关键字的【若干数位】组成哈希地址；



2-3-4、平方取中法

取关键字平方后的中间几位为哈希地址；



2-3-5、折叠法

将关键字分割成【位数相同】的几部分（最后一部分的位数可以不同），然后取这几部分的【叠加和】作为哈希地址，该方法称为折叠法（folding）；

使用场景：关键字位数很多，而且关键字中每一位上数据分布大致均匀时；



2-3-6、除留余数法

取关键字被某个【不大于】哈希表表长的数，将这个数作为除数，关键字作为被除数，所得【余数】为哈希地址；即

H(key) = key MOD p， p ≤ 哈希表长度；

注意：

使用除留取余法时，对除数的选择很重要，一旦选择不好，会产生较大冲突；



2-3-7、随机数法

选择一个随机函数，取关键字的随机函数值为哈希地址，即 H(key) = random(key)，其中 random 为 随机函数；通常，当关键字长度不等时适合用随机数法构造哈希函数；



2-3-8、选择哈希函数考虑的因素

• 计算哈希函数所需时间；

• 关键字长度；

• 哈希表大小；

• 关键字的分布情况；

• 记录的查找频率；



2-4、处理冲突的方法

2-4-1、开放地址法

H = ( H(key) + d ) MOD m，

其中： H(key) 为哈希函数；m 为哈希表表长；d为增量序列；



2-4-2、再哈希法

H = RH(key)，R 和 H 是不同的哈希函数，再产生哈希冲突时计算另一个哈希函数地址，直到冲突不再发生；

好处：不易产生“聚集”；

坏处：增加计算时间；



2-4-3、链地址法

关键字的哈希值相同的记录存储在同一线性链表上，每个值的初始状态都是空指针；



2-4-4、建立一个公共溢出区

哈希函数的值的范围[0, m-1]，则HashTable为[0 ... m -1 ] 的基本表，每个值存放一个记录；

在另外创建一个向量 OverTable[0 ... V] 为溢出表；

所有关键字和基本表中的关键字为同义词记录，一旦发生冲突，都填入溢出表；