胖蔡说技术
随便扯扯

什么是hash碰撞?如何解决hash碰撞?

Hash算法又称散列函数,指的是通过散列算法将任意长度的输入数据转换成固定长度的输出。这个输出就是我们得到的hash值。常见的hash算法有:MD5、SHA-1、SHA-256、RipeMD-160。

什么是hash碰撞?

基石由于hash算法的输入值有足够的大,就会出现了不同输入数据源却出现相同hash的情况。

k1  ≠ k2
h(k1) = h(k2)

如何解决hash碰撞?

通过网上资料总结,发现目前常用的解决hash碰撞的方式大致可以分为四种。

1、开放定址法

就是所有的元素通过散列表方式存储,通过下标地址访问获取。这就有可能会存在控件被填满 ,以致于不能插入任何新的元素。在开放寻址法中,当要插入一个元素时,可以连续地检查或探测散列表的各项,直到有一个空槽来放置待插入的关键字为止。有三种技术用于开放寻址法:

  • 线性探测:步长是1,逐步增加。
  • 二次探测:步长是由另外一个hash函数取模数组长度决定。
  • 双重探测:步长按照平方增加。

2、再hash法

再hash法就是当出现hash碰撞时,使用第二个、第三个…哈希函数,直到无冲突为止,一定程度上可以解决问题,但是付出的却是计算翻倍的代价。

3、链接法

将所有关键字为同义词的记录存储在同一线性单链表中,

我们称这种表为同义词子表,在哈希表中只存储所有同义词子表的头指针。对于关键字集合{12,67,56,16,25,37,22,29,47,48,34},我们用12作为除数,进行除留余数法,可得到下图结构,此时,就不存在哈希冲突换地址的问题,无论有多少个冲突,都只是在当前位置给单链表增加结点的问题。

4、建立公共溢出区

将哈希表分为基本表和溢出表两部分,凡是和基本表发生冲突的元素,一律填入溢出表。建立一个公共溢出区域,就是把冲突的都放在另一个地方,不在表里面。

赞(0) 打赏
转载请附上原文出处链接:胖蔡叨叨叨 » 什么是hash碰撞?如何解决hash碰撞?
分享到: 更多 (0)

请小编喝杯咖啡~

支付宝扫一扫打赏

微信扫一扫打赏