admin管理员组文章数量:1566221
1、散列表
看过HashMap源码的同学应该知道,HashMap是基于哈希表(散列表)的 Map 接口的非同步实现。
在我们put了一条key-value数据后,如下图,程序会先将key通过hash(key)这个函数转化成整形,这个整形做为数组的下标,插入数据或查找数据。
我们发现,散列表用的是数组支持按照下标随机访问数据的特性(时间复杂度O(1)),所以散列表其实就是数组的一种扩展,由数组演化而来。
我们通过散列函数的哈希算法(业界著名的有MD5、SHA、CRC等算法)把元素的键值映射为下标,然后将数据存储在数组中对应下标的位置。当我们按照键值查询元素时,我们用同样的散列函数,将键值转化数组下标,从对应的数组下标的位置取数据。
对于散列函数,实现的基本要求可以归纳为3点:
- 散列函数计算得到的散列值是一个非负整数;
- 如果 key1 = key2,那 hash(key1) == hash(key2) ;
- 如果 key1 ≠ key2,那 hash(key1) ≠ hash(key1) ;
对于第1点,因为数组下标从0开始;对于第2点,相同key,经过散列函数得到的值理应相同;但是对于第3点,会存在散列冲突的问题,既难以找到一个完美无冲突的算法,使得key不同时对应的散列值也不同【存在key1 ≠ key2,hash(key1) = hash(key1)的情况 】,即便是业界著名的哈希算法,也存在散列冲突的问题。
因此,对于散列冲突问题,可以其他低时间成本、低计算成本的途径解决
散列冲突解决方案
1. 开放寻址法
开放寻址法的核心思想是,如果出现了散列冲突,我们就重新探测一个空闲的位置。
开放寻址法解决方案有线性探测法、二次探测、双重散列等方案:
线性探测法(Linear Probing):
1)插入数据:当我们往散列表中插入数据时,如果某个数据经过散列函数之后,存储的位置已经被占用了,我们就从当前位置开始,依次往后查找(到底后从头开始),看是否有空闲位置,直到找到为止。
2)查找数据:我们通过散列函数求出要查找元素的键值对应的散列值,然后比较数组中下标为散列值的元素和要查找的元素是否相等,若相等,则说明就是我们要查找的元素;否则,就顺序往后依次查找。如果遍历到数组的空闲位置还未找到,就说明要查找的元素并没有在散列表中。
当然这里存在一个问题,就是存数据那块位置往前的某个数据被删除了,那么线性探索查到那块位置的时候就会判断元素不在散列表,查找就会失效,面对这个问题,我们在删除的时候,用下面删除的方法
3)删除数据:为了不让查找算法失效,可以将删除的元素特殊标记为deleted,当线性探测查找的时候,遇到标记为deleted的空间,并不是停下来,而是继续往下探测。
二次探测(Quadratic probing):线性探测每次探测的步长为1,即在数组中一个一个探测,而二次探测的步长变为原来的平方。
双重散列(Double hashing):使用一组散列函数,直到找到空闲位置为止。
线性探测法的性能描述:
用“装载因子”来表示空位多少,公式:散列表装载因子=填入表中的个数/散列表的长度。
装载因子越大,说明空闲位置越少,冲突越多,散列表的性能会下降。
2. 链表法
散列表中,每个“桶(bucket)”都会对应一个条链表,在查找时先听过hash(key)找到位置,然后遍历链表找到对应元素
插入数据:当插入的时候,我们需要通过散列函数计算出对应的散列槽位,将其插入到对应的链表中即可,所以插入的时间复杂度为O(1)。
查找或删除数据:当查找、删除一个元素时,通过散列函数计算对应的槽,然后遍历链表查找或删除。对于散列比较均匀的散列函数,链表的节点个数k=n/m,其中n表示散列表中数据的个数,m表示散列表中槽的个数,所以是时间复杂度为O(k)。
HashMap就是用链表法解决散列冲突的问题
冲突解决方法对比
优点 | 缺点 | 适用场景 | 案例 | |
开放寻址法 | 1、数据存储在数组,可以有效利用CPU缓存加速查询速度 2、序列化简单 | 1、删除需要特殊标记已删除数据 2、所有数据存储在一个数组,发生冲突时,解决的代价更高,造成装载因子不能太大,使得更加浪费内存空间 | 1、数据量小 2、装载因子小 | Java的ThreadLocalMap |
链表法 | 1、内存利用率高,需要时再申请 2、对大装载因子容忍度高,可大于1 | 1、因为链表需要存储指针,存储指针需要消耗内存,不适合小对象存储(万一存储数据没有指针大???多浪费) 2、链表节点不是连续空间,因此CPU缓存不友好 | 1、存储大对象、大数据量的散列表 2、支持更多优化策略,如红黑树代替链表。 | Java的LinkedHashMap |
版权声明:本文标题:散列表及散列冲突解决方案 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1725724399a1038769.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论