浅谈哈希冲突

理想的哈希函数是不会有冲突的,但是实际的哈希函数,不可能完全避免冲突。

一般有 4 中解决办法:

  • 开放定址法
    • 线性探测
    • 二次探测
    • 伪随机探测
  • 再哈希
  • 链地址
  • 建立公共溢出区

开放定址法

$$H_{i} = (H(key) + d_{i}) \% m, \space \space \space \space \space i=1,2,…,n$$

其中 H (key) 为哈希函数,m 为表长,di称为增量序列。

线性探测

$d_{i} = 1, 2, …, m - 1$

二次探测

$d_{i} = 1^{2}, -1^{2}, 2^{2}, -2^{2},…, k^{2}, -k^{2} (k^{2} < m)$

伪随机探测

$d_{i}=$ 伪随机数序列

再哈希法

$$H_{i} = H_{i}(key), \space \space \space \space \space i=1,2,…,k$$

当 $H_{1}(key)$ 发生冲突时,在计算 $H_{2}(key)$,… 直到冲突不再产生。

链地址法

将所有哈希地址相同的元素,构成一个同义词链的链表。

建立公共溢出区

将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表。

开放探测 vs 链地址法

开放探测的缺点:

  • 需要一个处理溢出的程序
  • 删除工作,为什么保证同义词链的话,不能直接把删除节点置为空 (因为会影响到该节点后面的节点) ,只能标上一个删除记号
  • 容易产生堆积

链地址的优点:

  • 无堆积
  • 节点空间动态申请,适合无法确定表长的情况
  • 删除简单

链地址的缺点:

  • 指针需要额外的空间

References