4s店网站建设方案,个人网站怎么建立流程,网页代做价格,cps广告联盟网站散列函数
算法不能设计太过复杂
太复杂的散列函数#xff0c;势必会消耗很多计算时间
散列函数生成的值要尽可能随机并且均匀分布
这样才能避免或者最小化散列冲突而且即便出现来冲突#xff0c;散列到每个槽里的数据也会比较平均#xff0c;不会出现某个槽内数据特别多…散列函数
算法不能设计太过复杂
太复杂的散列函数势必会消耗很多计算时间
散列函数生成的值要尽可能随机并且均匀分布
这样才能避免或者最小化散列冲突而且即便出现来冲突散列到每个槽里的数据也会比较平均不会出现某个槽内数据特别多的情况
散列冲突
开放寻址法
概述
如果出现了散列冲突我们就重新探测一个空闲位置将其插入
优点
开放寻址法不像链表法需要拉很多链表散列表中的数据都存储在数据中可以有效利用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那点事儿
