哈希函数的常用构造方法和处理冲突方法数据结构

常用的哈希函数构造方法包括：

直接寻址法（直接定址法）：
- 公式：f(key)=a*key+b （a,b都是常数）
- 适合查找表较小且连续的情况
- 优点：简单、均匀，不会产生冲突
- 缺点：需要知道关键字的分布，现实中不常用
数字分析法
- 方法：抽取关键字中的一部分来计算存储位置
- 适用于关键词较长的情况
平方取中法
- 方法：将关键字先平方，然后截取中间x位作为存储位置
- 适合用于不知道关键词分布，且位数不长的情况
折叠法
- 方法：将关键字拆分成若干部分后累加起来，根据散列表表长取总和的后若干位作为存储位置
- 适用于不知道关键字分布，且位数较长的情况
除留余数法
- 方法：f(key)=key mod p (p<=m)，m是散列表表长
- p取小于等于m的最小质数或者不包含小于20质因子的合数，以减少冲突的情况
随机数法
- 方法：f(key)=random(key)
- 注意random的随机种子需要是固定的，以便查询的时候能够根据key重新找到存储位置
- 适用于关键字长度不等的情况

【哈希函数的常用构造方法和处理冲突方法】常用冲突处理方法：

开放定址法：
- 方法： fi(key)=(f(key)+di) mod m，(di=1,2,3,4...,m?1)
- 线性探测：只要一旦发现冲突，就寻找下一个空的散列地址
- 二次探测：di=12,?12,22,?22,...,q2,?q2，目的是不让关键词集中在某块区域，产生堆积
- 随机探测：di是一个随机数，但查询时需要设置和插入时相同的随机种子
再散列函数法：
- 方法：fi(key)=RHi(key) (i=1,2,...k)
- 遇到冲突就重新采用一个散列函数计算新的存储位置，可以使关键字不产生聚集
链地址法（拉链）
- 方法：将所有关键字的同义词记录在一个单链表中，在散列表中只存储所有同义词表的头指针
公共溢出区法
- 方法：为所有冲突的关键字开辟一个公共的溢出区来存放
- 适用于相对于基本表来说冲突数据很少的情况