哈希

哈希函数

数据中的关键字映射到存放位置的映射函数叫做 哈希函数 。

哈希冲突

$K_i,K_j(i\neq j)$是两个关键字。 把$K_i \neq K_j$,并且$h(K_i)=h(K_j)$现象叫做哈希冲突这样的$K_i,K_j$叫做 同义词

哈希冲突的可能性与三个因素有关：

1. 填装因子$\alpha$。设已存入数据个数为n，哈希地址空间大小m，$\alpha=\dfrac{n}{m}$
2. 哈希函数。如果选择得当，可以使哈希地址尽可能均匀分布在地址空间上。
3. 哈希冲突函数：为解决哈希冲突问题，有哈希冲突函数，哈希冲突函数的选取也影响哈希冲突的可能性

几个经典哈希函数

余数法

• 算法：关键字K，哈希表长度为m，那么：$h(K)=K \mod m$
• 优点：
  • 算法简单，适用范围广
  • 如果关键字均匀，那么映射到每个地址的概率也均匀，减少了哈希冲突的概率

直接定址法

• 算法：关键字K加上某个常量C，$h(K)=K+C$
• 特点：
  • 优点：
    • 计算简单
    • 不可能有哈希冲突
  • 缺点：
    • 如果有1~1000的7个数字需要存放，可能需要1000个内存单元，造成大量浪费

数值分析法

• 分析数据内容，找出比较均匀的位（可以是多个），组合成为哈希地址
• 例如，某组数据有1000个数字，这些数字第1,3,6位取值比较均匀，那么可以提取1,3,6位，组成一个三位数作为哈希地址

哈希冲突的解决方法

有两个思路

• 链表法
• 开放定址法

链表法

• 如果哈希地址空闲，直接存放该数据。
• 如果哈希地址已被占用，把哈希冲突的数据放到链表中

开放定址法

• 如果没发生哈希冲突，直接存放该数据
• 如果发生了哈希冲突，把冲突的数据放入到别的 空闲单元 中

一些相关概念：

• 非同义关键字：把某个发生哈希冲突的数据放到另一个空闲单元d中，因为对应的关键字的哈希值不为d，就称为非同义关键字
• 开放定址法中，哈希空闲单元既向 同义关键字 开放，又向 非同义关键字开放，至于填入哪个，要看谁先占用它
• 非同义词冲突 在解决哈希冲突时，如果$K_i \neq K_j(i\neq j), h(K_i) \neq h(K_j)$, 但哈希冲突函数$h_1(K_i) = h_2(K_j)$，这种现象叫做非同义词冲突

开放定址法，在d位置发生哈希冲突时，探查下一个地址，这有几种探查策略：

1. 线性探查法 \(\left \{ \begin{array}{lcl} d_0=h(K)\\ d_i=(d_{i-1}+1)\mod m \end{array}\right.\)
   • 缺点是容易产生堆积问题，如果连续出现几个同义词后，将连续占用哈希表的内存单元

2. 平方探查法 \(\left \{ \begin{array}{lcl} d_0=h(K)\\ d_i=(d_{i-1}+2^{i-1})\mod m \end{array}\right.\)

3. 伪随机数法 \(\left \{ \begin{array}{lcl} d_0=h(K)\\ d_i=(d_{i-1}+R)\mod m \end{array}\right.\)
   • 其中，R是一个伪随机数