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)