哈希表

哈希表

哈希表，也叫散列表，它是基于快速存取的角度设计的，是一种典型的“空间换时间”的做法。它可以提供快速地插入和查找操作。

哈希表函数的构造方法

直接定址法

（、 为常数），即取关键码的某个线性函数值为哈希地址，不会产生冲突，但要求地址集合与关键码集合大小相同。因此，对于较大的关键码集合不适用。

除留余数法

（ 是一个整数），即取关键码除以 的余数作为哈希地址。使用除留余数法，选取合适的 很重要，若哈希表表长为 ，则要求，且接近 或等于 。 一般选取质数，也可以是不包含小于 20 质因子的合数。

数字分析法

设关键码集合中，每个关键码均由 位组成，每位上可能有 种不同的符号。

平方取中法

对关键码平方后，按哈希表大小，取中间的若干位作为哈希地址。

处理冲突的方法

开放寻址法

，其中 为散列函数，为散列表长，为增量序列，可有以下三种去法：

• ，称线性探测再散列；
• 称二次探测再散列；
• 伪随机数序列，称伪随机探测再散列。

再散列法

， 是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。

链地址法（拉链法）

当存储结构是链表时，多采用拉链法。用拉链法处理冲突的办法是：把具有相同散列地址的关键字（同义词）值放在同一链表中，称为用一次链表。有 个散列地址就有 个链表，同时用指针数组 T[0...m - 1] 存放各个链表的头指针，凡事散列地址为 的记录都以结点方式插入到以 T[i] 为指针的单链表中。

建立一个公共溢出区

设哈希函数产生的哈希地址集为，则分配两个表：一个基本表ElemType baseTbl[m]；每个单元只能放一个元素；一个溢出表ElemType overTbl[k]；只要关键码对应的哈希地址在基本表上产生冲突，则所有这样的原色一律存入该表中。

哈希表的查找

• 理想情况下我们根据关键字 key, 通过造表时候的哈希函数求得哈希地址，该表此位置上的记录的关键字与我们给定的关键字 key 相等，则查找成功。
• 但是如果有冲突，即该表此位置上的记录不是我们要查找的记录，则根据造表时候设定的冲突处理方法寻找“下一个地址”，一直到哈希表的某一个位置为“空”或者表中记录的关键字为我们给定的关键字 key。