哈希检索算法的深度学习

1 相关概念的理解

1.1 哈希检索

  1. 概念： 哈希检索技术的初衷是组织理想状态的检索表。检索表的理想状态是：把记录的关键字值与记录在检索表中的存储位置建立起某种一对一的关系，这种一对一的关系可以用关键字的一个函数h(key)来表示，这样不必进行关键字与给定值的比较，而是直接依据给定的关键字值来直接计算得到记录在检索表中的存储地址。
  2. 哈希函数（散列函数、杂凑函数）：反应关键字与存储位置一对一关系的函数h(key)

  3. 哈希检索技术必须解决的两个问题

    （1）如何选择一个计算简单且地址冲突尽可能少的哈希函数；
    （2）在出现地址冲突时采用什么办法解决冲突

1.2 哈希函数的构建方法

  1. 直接定址法：h(key) = a*key + b
  2. 数字分析法：提前知道关键字值的集合，分析关键字集合的分布情况，确定散列函数；
  3. 平方取中法：先求出关键字的平方，然后取中间几位作为哈希地址；
  4. 折叠法
  5. 除留余数法：h(key) = key % p
  6. 余取整法
  7. 随机数法：h(key) = random(key)

2 地址冲突的消解策略

2.1 开放地址法

把哈希表中的空位置向处理地址冲突开放，具体的做法是，当发生地址冲突时，从发生地址冲突的那个位置开始，使用某种方法在哈希表中形成一个探查序列。

2.1.1 线性探查法

  • 线性探查法是开放地址法消除地址冲突的一种最简单的探查方法。他把表长为m的哈希表看成是循环表，若发生地址冲突的位置地址为d，则依次探查d+1, d+2, …,直到找到一个空闲位置为止。

  • 公式：（地址）d = (h(key)+i)%m ， 其中i=1,2,…,m-1

  • 缺点：线性探查法易造成堆积现象。

2.1.2 平方探查法

  • 平方探查法也称为二次探查法。在发生地址冲突时，依次探查位置d+i，其中i取 1^2,-1^2,2^2,-2^2,…,
  • 公式：d = (h(key)+i^2)%m,d = (h(key)-i^2)%m 和中心扩展法相同，以地址冲突的位置，分别向两边去寻找空地址。

2.1.3 随机探查法

  • 随机探查法是采用一个随机数作为地址位移来计算下一个位置的地址
  • d = (h(key) + r)%m 其中r表示随机数，范围为 1~m-1

2.2 拉链法

  • 拉链法是将哈希地址相同的关键字的记录链接到同一个单链表中