散列表效率
之前讲到散列表的查询效率并不能笼统地说成是 O(1) 。它跟散列函数、装载因子、散列冲突都有关系。在极端情况下，恶意攻击者，通过精心构造的数据，使得所有数据经过散列函数后，都散列到同一个槽里。若我们使用的是基于链表的冲突解决办法，那这个时候，散列表就会退化为链表，查询时间度也退化为 O(n)。
开篇问题
如何设计一个可以应对各种异常情况的工业级散列表？在散列冲突的情况下，能够避免散列表性能的急剧下降。
散列函数
- 设计不能太复杂 ：避免消耗很多计算时间
- 生成的值要尽可能随机并且均匀分布：避免或者最小化散列冲突
装载因子过大怎么办？
装载因子越大，说明散列表中的元素越多，空闲位置越少，散列冲突的概率就越大。
不仅插入数据的过程要多次寻址或者拉很长的链，查找的过程也会因此变得很慢。
解决办法
使用动态扩容，重新申请一个更大的散列表，将数据搬移到这个新散列表中。
存在问题：数据搬移操作很复杂，需要通过散列函数重新计算每个数据的存储位置。
插入数据时间复杂度
- 最好情况：不需要扩容，复杂度为
O(1) - 最坏情况：散列表装载因子过高，需扩容，重新申请内存，重新计算哈希位置，并搬移位置，复杂度为
O(n) - 平均情况：摊还分析，时间复杂度接近最好情况，为
O(1)
平衡空间与时间的消耗
若对空间消耗非常敏感，可以为装载因子设置阈值，当装载因子小于阈值之后，启动动态缩容。
若更在意执行效率，能够容忍多消耗一点内存空间，就不需要缩容。
装载因子阈值需要选择得当。如果太大，会导致冲突过多；如果太小，会导致内存浪费严重。
阈值的设置要权衡时间、空间复杂度。
如果内存空间不紧张，对执行效率要求很高，可以降低负载因子的阈值；
相反，如果内存空间紧张，对执行效率要求又不高，可以增加负载因子的值，甚至可以大于 1。
避免低效扩容
为解决一次性扩容耗时过多的情况，可以将扩容操作穿插在插入操作的过程中，分批完成。
具体过程
- 当装载因子触达阈值之后，只申请新空间，并不将老的数据搬移到新的散列表中。
- 每当有新数据插入，将新数据插入新散列表，并从旧散列表拿一个数据放入新散列表。
时间复杂度
通过以上均摊方法，将一次扩容的代价，均摊到多次插入操作中。这种实现方式，在任何情况下，插入一个数据的时间复杂度都是 O(1)
查询操作
- 先在新散列表中查询
- 未查询到，再到旧散列表中查找
冲突解决方法
开放寻址法
优点
- 数据存储在数组中，有效利用CPU缓存加快查询速度
- 方便序列化
- 不需要额外空间
缺点
- 查找、删除数据时，涉及到
delete标记，比较麻烦 - 所有数据存储在一个数组中，冲突代价比较高
- 装载因子的上限不能太大，更浪费空间
链表法
优点
- 对内存的利用率更高
- 对装载因子的容忍度更高；即便装载因子变成10，也只是链表的长度变长
缺点
- 需要额外的空间来保存指针
- 结点零散分布在内存中，不连续，对CPU缓存不友好
总结
当数据量比较小、装载因子小的时候，适合采用开放寻址法；
面对大对象、大数据量的散列表时，适合采用基于链表的散列冲突处理方法。
而且，比起开放寻址法，链表法更加灵活，支持更多的优化策略，比如用红黑树代替链表。
解答开篇
工业级的散列表应该具有哪些特性？
- 支持快速的查询、插入、删除操作；
- 内存占用合理，不能浪费过多的内存空间；
- 性能稳定，极端情况下，散列表的性能也不会退化到无法接受的情况。
从三个方面来考虑设计思路
- 设计一个合适的散列函数；
- 定义装载因子阈值，并且设计动态扩容策略；
- 选择合适的散列冲突解决方法。