散列函数
算法不能设计太过复杂
- 太复杂的散列函数,势必会消耗很多计算时间
散列函数生成的值要尽可能随机并且均匀分布
- 这样才能避免或者最小化散列冲突
- 而且即便出现来冲突,散列到每个槽里的数据也会比较平均,不会出现某个槽内数据特别多的情况
散列冲突
开放寻址法
概述
如果出现了散列冲突,我们就重新探测一个空闲位置,将其插入
优点
- 开放寻址法不像链表法,需要拉很多链表
- 散列表中的数据都存储在数据中,可以有效利用CPU缓存加快查询速度而且这样实现的散列表,序列化起来比较简单,链表法包含指针,序列化起来就没那么容易
缺点
- 删除数据的时候比较麻烦,需要特殊标记已经删除掉的数据
- 所有数据都存储在一个数组中,比起链表法来说,冲突的代价更高
- 所有,使用开放寻址解决冲突的散列表,装载因子的上限不能太大。这也导致这种方法比链表法更浪费内存空间
方法
线性探测(Linear Probing)
当往散列表中插入数据时,如果某个数据经过散列函数之后,存储位置已经被占用了,我们就从当前位置开始,依次往后查找,看是否有空闲位置,直到找到为止
二次探测(Quadratic probing)
线性探测每次探测的步长是1,那它探测的下标序列就是hash(key) + 0, hash(key) + 1, hash(key) + 2 …
而二次探测探测的步长就变成原来的“二次方”, 也就是说,它探测的下标序列就是 hash(key) + 0, hash(key) + (1 ^ 2), hash(key) + (2 ^ 2)
双重散列(Double hashing)
不仅要使用一个散列函数。我们使用一组散列函数 hash1(key), hash2(key), hash3(key)
我们先用第一个散列函数,如果计算得到的存储位置已经被占用,再用第二个散列,依次类推找到空闲的存储位置
装载因子(load factor)
不管采用那种方法,当散列表中空闲位置不多的时候,散列冲突的概率就会大大提高
为了尽可能保证散列表的操作效率,一般情况下,我们会尽快保证散列表中有一定比例的空闲槽位
状态因子概述及公式
散列表的装载因子 = 填入表中的元素个数 / 散列表的长度
装载因子来表示空位多少,状态因子越大,说明空闲位置越少,冲突越多,散列表的性能就会下降
如何解决装载因子过大的问题?
动态扩容
- 重新申请一个更大的散列表,将数据搬移这个新的散列表中
- 假设每次扩容我们都申请一个原来散列表大小两倍的空间。如果原来散列表的装载因子是0.8,那经过扩容之后,新散列表的装载因子因子就下降为原来的一半,变成了0.4
装载因子阀值的设置要权衡时间,空间复杂度
- 如果内存空间不紧张,对执行效率要求很高,可以降低负载因子的阀值
- 相反,如果内存空间紧张,对执行效率要求又不高,可以增加负载因子的值,甚至可以大于1
如何避免低效地扩容?
为了解决一次性扩容耗时过多的情况,我们可以将扩容操作穿插在插入操作的过程中,分批完成
当装载因子触达阀值之后,我们只申请新空间,但并不将老的数据搬移到新散列表中
当有新数据要插入时,我们将新数据插入新散列表中,并且从老的散列表中拿出一个数据放入新散列表中
每次插入一个数据到散列表,我们都重复上面的过程。经过多次插入操作之后,老的散列表中的数据就一点一点全部搬移到新散列表中
这时间的查询,为了兼容了新,老散列表中的数据,我们先从新散列表中查找,如果没有找到,再去老的散列表中查找
通过这样均摊的方法,将一次性扩容的代价,均摊到多次插入操作中,就避免一次性扩容耗时过多的情况。这种实现方式,任何情况下,插入一个数据的时间复杂度都是O(1)
链表法
概述
在散列表中,每个"桶(bucket)" 或者"槽(slot)" 会对应一条链条,所以散列值相同的元素我们都会放在相同槽位对应的链表中
当插入的时候,我们只需要通过散列函数计算出对应的散列槽位,将其插入到对应链表中即可,所以插入的时间复杂度O(1)
当查找删除一个元素时,我们同样通过散列函数计算出对应的槽,然后遍历链表查找或删除。那查找或删除操作的时间复杂度是多少呢?
- 实际上,这两个操作的时间复杂度跟链表的长度k成正比,也就是O(k)
- 对于散列比较均匀的散列函数来说,理论上讲, k = n / m,其中n表示散列中数据个数,m表示散列中“槽”的个数
优点
- 链表法对内存的利用率比开放寻址法要高
- 因为链表结点可以在需要的时候再创建,并不需要像开放寻址法那样事先申请好
- 链表法比起开放寻址法,对大装载因子的容忍度更高
- 开放寻址法只能适用装载因子小于1的情况
- 接近1时,就可能会又大量的散列冲突,导致大量的探测,再散列等,性能会下降很多
- 但是对于链表法,只要散列函数的只随机均匀,即便装载因子变成10,也就是链表的长度变长了而已,虽然查找效率有所下降,但是比起顺序查找还是快很多
缺点
- 链表因为要存储指针,所有对于比较小的对象的存储,是比较消耗内存,还有可能会让内存的消耗翻倍
- 而且,因为链表中的结点是零散分布在内存中,不是连续,所有对于CPU缓存是不友好的,这方面对于执行效率也有一定的影响
- 总结
- 基于链表的散列冲突处理方法比较合适存储大对象,大数据量的散列表
- 而且,比起开放寻址法,它更加灵活,支持更多优化策略,比如用红黑树代替链表
工业级的散列表应该具有哪些特征?
要求
支持快速的查询,插入,删除操作
内存占用合理,不能浪费过多的内存空间
性能稳定,极端情况下,散列表的性能也不会退化到无法接受的程度
设计
设计一个合适的散列函数
定义装载因子阀值,并且设计动态扩容策略
选择合适的散列冲突解决方法
散列表的缺点和改进
缺点
- 散列表这种数据结构虽然支持非常高效的数据插入,删除,查找操作,但是散列表中的数据都是通过散列函数打乱之后无规律存储的。也就是,它无法支持按照某种顺序快速地遍历数据
- 如果希望按照顺序遍历散列表中的数据,那我们需要将散列表中的数据拷贝到数组中,然后排序,再遍历
改进
- 因为散列表是动态数据结构,不停有数据的插入,删除,所以每当我们希望按顺序遍历散列表中的数据的时候,都需要先排序,那效率势必会很低
- 为了解决这个问题,我们将散列表和链表(或跳表)结合一起使用
资料参考
- [Data Structure & Algorithm] Hash那点事儿