设计散列表 #

散列表的两个核心问题就是“散列函数设计”和“散列冲突解决”。散列函数设计不好，或者装载因子过高，都可能导致散列冲突，导致查询效率下降。

在极端情况下，恶意的攻击者通过构造数据，是的所有数据经过散列函数之后都散列到同一个槽里，如果是基于链表实现的散列表，那么时间复杂度就退化为 O(n) 了。

比如散列表有 10 万个数据，退化的散列表查询的效率退化 10 万倍。如果之前 100 次查询需要 0.1 秒，那么现在需要 10000 秒。这样的查询可能消耗大量 CPU 或者线程资源，导致系统无法响应其他请求，从而达到拒绝服务攻击（DoS）的目的。这也就是散列表碰撞攻击的基本原理。

如何设计散列函数 #

散列函数的设计直接影响散列表的性能。

散列表的设计原则 #

首先，散列函数不能设计得太复杂。过于复杂的散列函数，本身的计算就消耗很多时间，直接影响散列表的性能。

此次，散列函数生成散列值要尽可能的随机并且均匀分布。这样才能避免或最小化散列冲突，即便出现冲突，散列到每个槽里的数据也比较平均，不会出现某个槽数据很多的情况。

实际工作中，还需要综合考虑各种因素，包括键的长度、特点、分布，还需要考虑散列表的大小。

例如，前面的参数选手例子，通过分析选手编号，把编号的后两位作为散列值。这种方法叫作数据分析法。另外还有直接寻址法、平方取中法、折叠法、随机数法等等。

装载因子过多怎么办 #

用散列表的装载因子表示空闲槽位的比例：

装载因子 = 填入表中的元素个数 / 散列表的长度

也就是，装载因子越大，空闲位置越少，冲突概率越大；反之，装载因子越小，空闲位置越多，冲突概率越小。

对于静态的数据集合，很容易根据数据特点设计出完美的、极少冲突的散列函数。但是对于动态的散列表来说，数据集合频繁变动，无法预估将要加入的数据个数，所以无法事先申请一个足够大的散列表。

随着数字加入，装载因子也就会加大。当装载因子大到一定程度，散列冲突会变得不可接受。

动态扩容 #

还记得数组的动态扩容吗？一样的，这里就需要对散列表进行动态扩容。如果当前装载因子是 0.8，当申请一个 2 倍的空间之后，通过扩容，装载因子就下降到 0.4 了。

和数组的动态扩容时数据搬移不同，散列表的数据搬移比较麻烦。因为散列表大小变了，数据的存储位置也变了，所以需要通过散列函数重新计算每个数据的位置。

插入数据的时候，时间复杂度可以使用摊还分析法，时间复杂度接近最好时间复杂度，就是 O(1)。

装载因子超过某个阈值时，需要进行扩容。同样，如果装载因子小于某个值之后，如果对空间消耗非常敏感，那么这时就可以进行缩容。

避免低效扩容 #

动态扩容的散列表插入一个数据很快。但当装载因子已经达到阈值，需要进行扩容，再插入数据，这时候就很慢。如果这部分的业务代码直接服务于客户，那这极个别的插入很慢的情况，体验也不好。

为了避免一次性扩容存在的问题，可以将扩容操作分散到插入操作中，分批完成。当装载因子达到阈值之后，只申请空间，单并不把老的数据搬移到新的散列表中。

接着当有新数据插入的时候，先将新数据插入到新的散列表，并且从老的散列表中拿出一个数据放到新的散列表中。没插入一个数据就重复上面的过程，经过多次插入之后，老的散列表中的数据就被全部搬移到新散列表中了。

对于查询和删除操作，需要兼容新、老散列表。可以先在新的散列表中查找，如果没有找到，就去老的散列表找。

如何选择散列冲突的解决方法 #

前面讲到了开放寻址法和链表法。这两种方法都常用，比如 Java 中 LinkedHashMap 就采用了链表法解决冲突，ThreadLocalMap 是通过线性探测的开放寻址法来解决冲突。

开放寻址法 #

开发寻址法不像链表法，它的数据都存储在数组中，可以有效的利用 CPU 缓存加快查询速度。而且，这种散列表序列化比较简单，链表法包含指针，序列化比较麻烦。

但是，删除数据的时候比较麻烦，需要特殊标记已经删除的数据。另外所有数据都存数在数组中，冲突代价比较高，需要遍历来处理。所以使用开放寻址法解决散列冲突时，装载因子的上限不能太多，但是这也导致这种方法比链表法更加浪费资源。

总结一下，当数据量比较小、装载因子小的时候，适合采用开发寻址法。这也是 ThreadLocalMap 使用开发寻址法解决散列冲突的原因。

链表法 #

首先，链表法对内存的利用率比寻址法更高。因为链表结点可以在使用的时候再创建，不需要像开放寻址法一样事先申请好。

链表法对装载因子的容忍度比开放寻址法更高。开放寻址法的装载因子只能小于 1，而且接近 1 时，可能会导致大量的散列冲突，造成大量的探测。而链表法，只要散列函数的值比较均匀，即便装载因子变成 10，也就是链表长度变成了，查询效率有所下降，但是比开放寻址法还是快很多。

但是链表法需要存储指针，所以对于比较小的对象存储，还是比较消耗内存的，可能会让内存的消耗翻倍。而且，链表中的结点在内存中是零散的，不连续，所以对 CPU 缓存并不友好，这方面对执行效率有一定影响。

如果存储的是大对象，那么链表中指针的内存消耗对大对象来说，可以忽略不计的。

实际上，对链表法稍加改造，可以时间一个更高效的散列表。就是将链表改造为其他高效的动态数据结构，比如跳表、红黑树。这样即便出现散列冲突，所有数据都在一个槽里，那么散列表查询的时间复杂度只不过退化为 O(logn)，而不是 O(n)。避免前面说的散列表碰撞攻击。

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