Folders and files Name Name Last commit message
Last commit date
parent directory
View all files
算法不能设计太过复杂
散列函数生成的值要尽可能随机并且均匀分布
这样才能避免或者最小化散列冲突
而且即便出现来冲突，散列到每个槽里的数据也会比较平均，不会出现某个槽内数据特别多的情况
开放寻址法
概述
如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入
优点
开放寻址法不像链表法，需要拉很多链表
散列表中的数据都存储在数据中，可以有效利用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缓存是不友好的，这方面对于执行效率也有一定的影响
总结
基于链表的散列冲突处理方法比较合适存储大对象，大数据量的散列表
而且，比起开放寻址法，它更加灵活，支持更多优化策略，比如用红黑树代替链表
要求
支持快速的查询，插入，删除操作
内存占用合理，不能浪费过多的内存空间
性能稳定，极端情况下，散列表的性能也不会退化到无法接受的程度
设计
设计一个合适的散列函数
定义装载因子阀值，并且设计动态扩容策略
选择合适的散列冲突解决方法
缺点
散列表这种数据结构虽然支持非常高效的数据插入，删除，查找操作，但是散列表中的数据都是通过散列函数打乱之后无规律存储的。也就是，它无法支持按照某种顺序快速地遍历数据
如果希望按照顺序遍历散列表中的数据，那我们需要将散列表中的数据拷贝到数组中，然后排序，再遍历
改进
因为散列表是动态数据结构，不停有数据的插入，删除，所以每当我们希望按顺序遍历散列表中的数据的时候，都需要先排序，那效率势必会很低
为了解决这个问题，我们将散列表和链表（或跳表）结合一起使用
You can’t perform that action at this time.