hash常见构造和处理冲突方法

发表于 分类于
本文字数： 242 阅读时长 ≈ 1 分钟

几种hash的构造和处理冲突方法的名字经常记混，记录一下。

构造方法

  1. 直接定址法

$H(key)=a*key+b$

  1. 除留余数法

$H(key)=key%p$

  1. 数字分析法
  2. 平方取中法
  3. 折叠法

处理冲突

开放定址

$H_i=(H(key)+d_i)%m$

  1. 线性探测

$d_i=0,1,2,…,m-1$

  1. 平方探测

$d_i=0^2,1^2,…,k^2,-k^2; k<=m/2$

  1. 再散列

$d_i=Hash_2(key)$

  1. 伪随机序列

链地址

同义词存在链表中。