redis - hash冲突

hash table 也叫做时 “散列表”、哈希表

redis的数据结构也有用到这个数据结构。哈希表用的时数组支持下标随机访问数据的特性,所以哈希表其实就是数组得一种扩展,是由数组演化而来的。

  

通过hash函数得到的hash值有一下几个特点:

1、hash函数得到的 value值 是一个非负整数

2、如果key相同 通过hash函数得到的 value值肯定相同

3、如果key不相同的话,通过hash函数得到的value不一定不同(涉及到了哈希冲突问题)

 

相对于哈希冲突而言,业界比较著名的哈希算法函数 MD5、SHA、CRC 都不发完全避免哈希冲突的问题。数组得存储空间有限,也会加大哈希冲突的概率。

以下为解决hash冲突问题的方法:

 

1、开放寻址法

  开发寻址法的核心思想,hash(key)得到的hash值,在哈希表中找到下标值,发现已经被占用了,就会从存储位置下一个开始进行探测寻找,寻找没有被占用的空闲位置,

找到了位置以后将数据存入。如果发现找到尾部以后都被占用,则会从头开始继续寻址,直到找到为止。数据量大的话,性能会就下降

       

  查找操作:

      通过hash(key) 查找该hash值对应的数据时,会通过hash函数得到一个hash值,然后比较数组种下标为散列值得数据和要查找的元素是否相等,不相等则顺序往后查找,

如果遍历到空闲位置还没有找到的话就返回为 未找到。

 

      删除操作:

  在hash表中是否可直接删除一个数据,然后将hash表中直接置为空呢?!其实时不可以的,因为在查找数据的过程中,遇到空闲位置时,则认为该数据不存在hash表中,所以如果在hash表中删除一个

一个数据时将位置 设置为空,会造成查找数据出现问题。解决方案就是将删除的数据置位deleted ,这样在查找数据时就会跳过继续查找下一个位置。

 

2、链表法

     hash表有一个指标来表示hash冲突严重程度:

    hash表装载因子 = 填入表中的元素个数 / hash表长度;

    "hash表装载因子" 这个值越大表明hash冲突越严重,hash表的性能就会下降的。

 

下面一个比较常用的解决hash冲突的办法就是 链表法 。在hash表有一个概念叫做hash槽,每个hash槽会对应一个链表,所有的通过hash函数得到的散列值相同的元素会放在相同的hash槽位对应的链表中。

 

插入数据:

  通过hash函数查询到对应的hash槽位,将数据插入到对应链表的中。这个插入数据的时间复杂度时O(1)

查找、删除数据:

      查找数据、删除数据时,通过hash函数得到的哈希值,找到对应的哈希槽位,遍历槽位对应的链表,找到要删除或查找的数据进行对应的操作。

这个时间复杂度取决于hash槽位对应的链表的长度。

比如:元素个数为n个

        hash槽位有m个

那时间复杂度就是 O(n/m)

 

上一篇:helm3部署es kubernetes高可用集群


下一篇:【数据结构与算法】哈希表