散列表（下）

如何设计一个好的散列函数

• 散列函数的设计不能太复杂，过于复杂的散列函数会消耗很多计算时间，间接影响散列表的性能。
• 散列表生成的值要尽可能随机并且均匀分布，能避免或最小化散列冲突，而且即便冲突出现，也不会出现某个槽位内数据特别多的情况。
• 常见散列函数设计方法，数据分析法、直接寻址法、平方取中法、折叠法、随机数法。

装载因子过大解决方法

• 设置动态扩容的阈值，选择设置动态缩容的阈值。
• 动态扩容，可以重新申请一个更大的散列表，将数据搬移到新散列表中。针对单纯数组的扩容，数据搬移操作比较简单。但是针对散列表的扩容，数据搬移操作要复杂得多，因为散列表的大小变了，数据的存储位置也变了，需要通过散列函数重新计算每个数据的存储位置。
• 对于支持动态扩容的散列表，最好时间复杂度是O(1)；最坏情况下由于散列表装载因子过高，启动扩容，重新申请连续内存空间，重新计算哈希位置并且搬移数据，时间复杂度O(n)；用摊还法分析，均摊情况下时间复杂度接近O(1)。
• 装载因子阈值设置要权衡时间、空间复杂度。如果内存空间不紧张，对执行效率要求很高，可以降低负载因子的阈值；如果内存空间紧张，对执行效率要求又不高，可以增加负载因子的阈值，甚至可以大于1。

避免低效地扩容

• 大部分情况下，动态扩容的散列表插入一个数据都很快，但是当装载因子达到阈值时，就需要先进行扩容，再插入数据。此时插入数据就会变得很慢，甚至无法接受。
• 为了解决一次性扩容耗时过多的情况，可以将扩容的数据搬移操作穿插在插入操作过程中，分批次完成。当装载因子达到阈值时，只进行新空间的申请，但不将老数据搬移到新散列表中。
• 当有新数据插入时，将新数据插入到新的散列表，并从老的散列表中拿出一个数据放入到新的散列表。重复这个过程，这样老散列表中的数据就一点点地全部搬移到新的散列表中。这样没有了集中的一次性数据搬移，插入操作就变得很快。
• 在分散搬移数据这个期间，对于查询操作，为了兼容新、老散列表中的数据，先从新的散列表汇总查找，找不到再去老的散列表中查找。
• 通过这种均摊方法，将一次性扩容的代价，均摊到多次插入操作中，避免了一次性扩容耗时过多的情况。这种实现方式，在任何情况下，插入一个数据的时间复杂度都是O(1)。

解决散列冲突开放寻址法与链表法对比

• 开放寻址法
  优点：
  1.不需要拉很多链表，散列表中的数据存储在数组中，可以有效地利用CPU缓存加速查询速度；
  2.基于开放寻址法实现的散列表，序列化起来比较简单；而链表法包含指针，序列化起来没那么容易。
  缺点：
  1.删除数据时比较麻烦，需要特殊标记已经删除掉的数据；
  2.所有的数据都存储在一个数组中，比起链表法，冲突的代价更高；
  3.基于缺点2，使用开放寻址法解决冲突的散列表，装载因子上限不能太大，导致此种方法比链表法更浪费内存空间。
  适用场景：
  数据量比较小，装载因子小的时候，适合采用开放寻址法。
• 链表法
  优点：
  1.内存利用率比开放寻址法高，可以再需要的时候再创建，并不需要像开放寻址法那样事先申请好；
  2.比起开放寻址法，对大装载因子的容忍度更高。
  缺点：
  1.因为链表要存储指针，所以对较小的对象的存储，是比较消耗内存的，还可能会让内存的消耗翻倍；
  2.链表中的节点是零散分布在内存中的，不是连续的，所以对CPU缓存是不友好的，这对于执行效率也有一定的影响。
  适用场景：
  基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且相对于开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。

何为一个工业级的散列表，它应该具有哪些特性？

• 支持快速的查询、插入、删除操作；
• 内存占用合理，不能浪费过多的内存空间；
• 性能稳定，极端情况下，散列表的性能也不会退化到无法接受的情况。

如何实现一个工业级的散列表？

• 设计一个合适的散列函数；
• 定义装载因子阈值，并且设计动态扩容策略；
• 选择合适的解决散列冲突的方法。