解决哈希冲突的4种常用方法

文章目录

    • 相关概念及说明
    • 一、开放地址法
      • (1)、线性探测再散列
      • (2)、二次探测再散列
      • (3)、伪随机再散列
    • 二、链地址法
    • 三、再散列法
    • 四、公共溢出区


相关概念及说明

  • 哈希冲突:
    由于哈希算法被计算的数据是无限的,而计算后的结果范围有限,因此总会存在不同的数据经过计算后得到的值相同,这就是哈希冲突。

  • 哈希构造函数
    本文的哈希构造函数采用除留余数法,哈希构造函数可以参考我的另一篇文章:常见的六种哈希构造函数

  • 例子
    哈希函数为Hash (key)=key%7,关键字序列为{32,24,15,27,20,13}

一、开放地址法

  • 定义
    Hi=(H(key) + di) MOD m,i=1,2,…,k(k<=m-1),其中H(key)为散列函数,m为散列表长(本例取7),di为增量序列,可有下列三种取法:

(1)、线性探测再散列

  • 定义: di=1,2,3,…,m-1,称线性探测再散列
  • 分析
    H(32)=4,H(24)=3,H(15)=1,H(27)=6
    H(20)=6出现冲突,使用线性探测再散列,H(20)=(6+1)%7=0
    H(13)=6出现冲突,使用线性探测再散列,H(13)=(6+1)%7=0,依旧冲突继续;H(13)=(6+2)%7=1.,依旧冲突继续;H(13)=(6+3)%7=2。
  • 结果
    解决哈希冲突的4种常用方法_第1张图片

(2)、二次探测再散列

  • 定义: di=1^2 ,-1^2, 2^2 ,-2^2 ,3^2 ,±k^2,(k<=m/2)称二次探测再散列
  • 分析
    H(32)=4,H(24)=3,H(15)=1,H(27)=6
    H(20)=6出现冲突,使用二次探测再散列,H(20)=(6+1)%7=0
    H(13)=6出现冲突,使用线性探测再散列,H(13)=(6+1)%7=0,依旧冲突继续;H(13)=(6-1)%7=5。
  • 结果
    解决哈希冲突的4种常用方法_第2张图片

(3)、伪随机再散列

  • 定义:di=伪随机数序列,称伪随机探测再散列
  • 分析
    假设伪随机数序列为{1,3,5,7,8,9,11}
    H(32)=4,H(24)=3,H(15)=1,H(27)=6
    H(20)=6出现冲突,使用线性探测再散列,H(20)=(6+1)%7=0
    H(13)=6出现冲突,使用线性探测再散列,H(13)=(6+1)%7=0,依旧冲突继续;H(13)=(6+3)%7=2。
  • 结果
    解决哈希冲突的4种常用方法_第3张图片

二、链地址法

  • 定义:将所有关键字为同义词(即H(key)相同)的结点链接在同一个单链表中。若选定的哈希表长度为m,则可将散列表定义为一个由m个头指针组成的指针数组T[0…m-1]。凡是散列地址为i的结点,均插入到以T[i]为头指针的单链表中。
  • 分析
    H(32)=4,H(24)=3,H(15)=1,H(27)=6,H(20)=6,H(13)=6
  • 结果
    解决哈希冲突的4种常用方法_第4张图片

三、再散列法

  • 定义:
    这种方法是同时构造多个不同的哈希函数:
    Hi=RH1(key); i=1,2,…,k
    当哈希地址Hi=RH1(key)发生冲突时,再计算Hi=RH2(key)……,直到冲突不再产生。这种方法不易产生聚集,但增加了计算时间
  • 分析
    RH1(key)=key%7(即除留余数法的哈希构造函数),设RH2(key)=key%5,RH3(key)=key%8
    则H1(32)=4,H1(24)=3,H1(15)=1,H1(27)=6,当key=20时,H1(20)=6发生冲突,因此使用第二个散列函数,得到H2(20)=0,不发生冲突;当key=13时,H1(13)=6,H2(13)=3均发生冲突,H3(13)=5不发生冲突。
  • 结果
    解决哈希冲突的4种常用方法_第5张图片

四、公共溢出区

  • 定义:即为所有冲突的关键字建立一个公共的溢出区来存放。在查找时,对给定值通过散列函数计算出散列地址后,先与基本表的相应位置进行比对,
    如果相等,则查找成功;如果不相等,则到溢出表去进行顺序查找。
    如果对于基本表而言,有冲突的数据很少的情况下,公共溢出区的结构对查找性能来说还是非常高的
  • 分析
    H(32)=4,H(24)=3,H(15)=1,H(27)=6,H(20)=6和H(13)=6发生冲突,因此将20,13放入公共溢出区
  • 结果
    解决哈希冲突的4种常用方法_第6张图片

你可能感兴趣的