工业级的散列表应该具有哪些特性?

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

如何实现这样一个散列表呢?我会从这三个方面来考虑设计思路:

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

1. 如何设计散列函数

首先,散列函数的设计不能太复杂。否则会消耗很多计算时间,影响散列表的性能。其次,散列函数生成的值要尽可能随机并且均匀分布,这样才能避免或者最小化散列冲突。

常见的散列函数设计方法:直接寻址法、平方取中法、折叠法、随机数法等。

2. 如何根据装载因子动态扩容

1. 设置装载因子阈值

针对散列表,当装载因子过大时,我们可以进行动态扩容,重新申请一个更大的散列表,将数据搬移到这个新散列表中,还需要通过散列函数重新计算每个数据的存储位置。对于支持动态扩容的散列表,插入数据的时间复杂度使用摊还分析法是 O(1)。

装载因子阈值的设置要权衡时间、空间复杂度。如果内存空间不紧张,对执行效率要求很高,可以降低负载因子的阈值;相反,如果内存空间紧张,对执行效率要求又不高,可以增加负载因子的值,甚至可以大于 1。

2. 避免低效扩容

分批扩容

为了解决一次性扩容耗时过多的情况,可以将扩容操作穿插在插入操作的过程中,分批完成。

分批扩容的插入操作:当有新数据要插入时,将数据插入新散列表,并且从老散列表中取出一个数据放入新散列表。每次插入都重复上面的过程。

分批扩容的查询操作:先查找新散列表,如果没有找到,再查找老散列表。

通过均摊的方式,任何情况下,插入一个数据的时间复杂度都是O(1)。

3. 如何选择冲突解决方法

开放寻址法和链表法在实际的软件开发中都非常常用。比如,Java 中 LinkedHashMap 就采用了链表法解决冲突,ThreadLocalMap 是通过线性探测的开放寻址法来解决冲突。

开放寻址法

优点:

  • 散列表中的数据都存储在数组中,可以有效地利用 CPU 缓存加快查询速度。
  • 没有指针,序列化起来比较简单。

缺点:

  • 删除数据的时候比较麻烦,需要特殊标记已经删除的数据。
  • 数据存储在一个数组中,比起链表法,冲突的代价更高。
  • 装载因子的上限不能太大,比链表法更浪费内存空间。

结论:
当数据量比较小、装载因子小的时候,适合采用开放寻址法。这也是 Java 中的 ThreadLocalMap 使用开放寻址法解决散列冲突的原因。

链表法

优点:

  • 链表法对内存的利用率比开放寻址法要高。
  • 链表法比起开放寻址法,对大装载因子的容忍度更高。

缺点:

  • 对于比较小的对象的存储,是比较消耗内存的。
  • 对 CPU 缓存是不友好的,对执行效率有一定的影响。

结论:
基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表,而且,比起开放寻址法,它更加灵活,支持更多的优化策略,比如用红黑树代替链表。

4. 工业级散列表举例分析

Java 中的 HashMap

  • 默认初始大小 16
  • 默认最大装载因子 0.75,扩容到原来的两倍
  • 链表法解决冲突,JDK1.8 后引入红黑树
  • 散列函数 (h ^ (h >>> 16)) & (capitity -1);