顺序表查找时，需要从表头开始，挨个的比较记录 a[i] 与 key 的值相等还是不相等，直到相等才会查找成功。

有序列表查找，可以利用 a[i] 与 key 的 < 或 > 来折半查找，直到相等时查找成功返回索引。

定义

通过关键字，不需要比较，即可获得需要的记录的存储位置——散列技术。

散列技术是在记录的存储位置和它的关键字之间建立一个确定的对应关系 f，使得每个关键字 key 对应一个存储位置 f (key)。查找时，根据这个确定的对应关系找到给定值 key 的映射 f (key) ，若查找集合中存在这个记录，则必定在 f ( key) 的位置上 。

这里我们把这种对应关系 f 称为散列函数 ， 又称为哈希 (Hash) 函数。

按这个思想， 采用散列技术将记录存储在一块连续的存储空间中，这块连续存储空间称为散列表或哈希表 (Hash Table）。 那么关键字对应的记录存储位置我们称为散列地址。

查找步骤

整个散列过程其实就两步：

  1. 在存储时，通过散列函数计算记录的散列地址，并按此散列地址存储该记录
  2. 当查找记录时，我们通过同样的散列函数计算记录的散列地址，按此散列地址访问该记录

所以说，散列技术既是一种存储方法，也是一种查找方法。

然而它与线性表、树、图等结构不同的是，前面几种结构，数据元素之间都存在某种逻辑关系，可以用连线图示表示出来，而散列技术的记录之间不存在什么逻辑关系，它只与关键字有关联。因此，散列主要是面向查找的存储结构。

散列技术最适合的求解问题是查找与给定值相等的记录。

构造方法

  • 直接定址法：需要事先知道关键字分布情况，适合查找表较小且连续的情况
  • 数字分析法：适合关键字位数比较大的情况，如果事先知道关键字的分布且关键字的若干位分布较均匀
    • 反转
    • 右环位移
    • 左环位移
    • 前两数与后两数叠加
  • 平方取中法：适合不知道关键字分布，而位数又不是很大的情况
  • 折叠法：事先不需要知道关键字的分布，适合关键字位数较多的情况
  • 除留余数法：f(key) = key mod p(p<=m)
  • 随机数法：f(key) = random(key)

参考因素：

  • 计算散列地址所需的时间
  • 关键字的长度
  • 散列表的大小
  • 关键字的分布情况
  • 记录查找的频率

处理冲突方法

开放定址法：一旦发生冲突，就去寻找下一个空的散列地址，只要散列表足够大，空的散列表地址总能找到，并将记录存入。

  1. f(key) = (f(key) + di) MOD m(di = 1,2,3,...,m-1)

线性探测法。

不是同义词却需要争夺同一地址的情况，称为堆积。

另外增加平方运算的目的是为了不让关键字都聚集在某一块区域。 我们称这种方法为二次探测法。

还有一种方法是， 在冲突时，对于位移量 d，采用随机函数计算得到，我们称之为随机探测法。

再散列函数法：发生散列地址冲突时，换个散列函数计算，相信总会有个可以把冲突解决掉。这种方法能够使得关键字不产生集聚，当然，相应地也增加了计算的时间。

链地址法：无论有多少冲突，都只是在当前位置给单链表增加结点的问题。

链地址法对于可能会造成很多冲突的散列函数来说，提供了绝不会出现找不到地址的保障。当然，这也就带来了查找时需要遍历单链装的性能损耗。

公共溢出区法：基本表+溢出表

在查找时，对给定值通过散列函数计算出散列地址后，先与基本表的相应位置进行比对，如果相等，则查找成功；如果不相等，则到溢出表去进行顺序查找。

如果相对于基本表而言，有冲突的数据很少的情况下，公共溢出区的结构对查找性能来说还是非常高的。