散列函数的基本概念

散列函数

算法不能设计太过复杂

• 太复杂的散列函数，势必会消耗很多计算时间

散列函数生成的值要尽可能随机并且均匀分布

• 这样才能避免或者最小化散列冲突
• 而且即便出现来冲突，散列到每个槽里的数据也会比较平均，不会出现某个槽内数据特别多的情况

散列冲突

开放寻址法

概述

如果出现了散列冲突，我们就重新探测一个空闲位置，将其插入

优点

• 开放寻址法不像链表法，需要拉很多链表
• 散列表中的数据都存储在数据中，可以有效利用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那点事儿