锐客网

  1. 首页 > it技术 > >

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

数据结构

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

  1. 直接寻址法（直接定址法）：
    • 公式：f(key)=a*key+b （a,b都是常数）
    • 适合查找表较小且连续的情况
    • 优点：简单、均匀，不会产生冲突
    • 缺点：需要知道关键字的分布，现实中不常用
  2. 数字分析法
    • 方法：抽取关键字中的一部分来计算存储位置
    • 适用于关键词较长的情况
  3. 平方取中法
    • 方法：将关键字先平方，然后截取中间x位作为存储位置
    • 适合用于不知道关键词分布，且位数不长的情况
  4. 折叠法
    • 方法：将关键字拆分成若干部分后累加起来，根据散列表表长取总和的后若干位作为存储位置
    • 适用于不知道关键字分布，且位数较长的情况
  5. 除留余数法
    • 方法：f(key)=key mod p (p<=m)，m是散列表表长
    • p取小于等于m的最小质数或者不包含小于20质因子的合数，以减少冲突的情况
  6. 随机数法
    • 方法：f(key)=random(key)
    • 注意random的随机种子需要是固定的，以便查询的时候能够根据key重新找到存储位置
    • 适用于关键字长度不等的情况
【哈希函数的常用构造方法和处理冲突方法】常用冲突处理方法：
  1. 开放定址法：
    • 方法： fi(key)=(f(key)+di) mod m，(di=1,2,3,4...,m?1)
    • 线性探测：只要一旦发现冲突，就寻找下一个空的散列地址
    • 二次探测：di=12,?12,22,?22,...,q2,?q2，目的是不让关键词集中在某块区域，产生堆积
    • 随机探测：di是一个随机数，但查询时需要设置和插入时相同的随机种子
  2. 再散列函数法：
    • 方法：fi(key)=RHi(key) (i=1,2,...k)
    • 遇到冲突就重新采用一个散列函数计算新的存储位置，可以使关键字不产生聚集
  3. 链地址法（拉链）
    • 方法：将所有关键字的同义词记录在一个单链表中，在散列表中只存储所有同义词表的头指针
  4. 公共溢出区法
    • 方法：为所有冲突的关键字开辟一个公共的溢出区来存放
    • 适用于相对于基本表来说冲突数据很少的情况

    推荐阅读


    上一篇：511减肥咖啡511咖啡，定义性感让年轻尖叫，定格青春，品味震撼销量，定义时尚，掀起爆品时尚潮

    下一篇：8/5|8/5 日精进