缺陷
线性探测法其实存在很大问题。当散列表中数据越多，hash冲突可能性越大，空闲位越少，线性探测时间越久。
极端情况下，可能需探测整个散列表，所以最坏时间复杂度O(n)。
删除和查找时，也可能线性探测整张散列表，才能找到要查找或删除的数据。
二次探测（Quadratic probing）
双重散列（Double hashing）
类似线性探测，线性探测每次探测的步长是1，那它探测的下标序列就是
- hash(key)+0
- hash(key)+1
- hash(key)+2
- 。。。
二次探测探测的步长就变成了原来的“二次方”，即探测的下标序列是：
- hash(key)+0
- hash(key)+12
- hash(key)+22
- ……
双重散列就是不仅要使用一个散列函数，而使用一组散列函数：
先用第一个散列函数，如果计算得到的存储位置已被占用，再用第二个散列函数，直到找到空闲位。
不管哪种探测方法，当散列表中空闲位置不多时，散列冲突的概率就会大大提高。为了尽可能保证散列表的操作效率，一般情况下，我们会尽可能保证散列表中有一定比例的空闲槽位。
优点
- 不像链表法，需要拉很多链表。数据都存在数组中，可有效地利用CPU缓存加快查询速度
- 序列化也更简单。链表法包含指针，序列化比较麻烦。
缺点
- 删除数据时，需特殊标记已删除的数据
- 所有的数据都存储在一个数组中，冲突的代价更高
所以，使用开放寻址法解决冲突的散列表，装载因子的上限不能太大。这也导致这种方法比链表法更浪费内存空间。
当数据量比较小、装载因子小的时候，适合采用开放寻址法。这也是Java中的ThreadLocalMap使用开放寻址法解决散列冲突的原因。
3.2 链表法
相比开放寻址法简单。
散列表中，每个“桶（bucket）”或“槽（slot）”对应一条链表：散列值相同的元素放到相同槽位对应的链表。
- 插入时，只需通过hash函数计算对应槽位，将其插入到对应链表，时间复杂度O(1)。
查找、删除
同样通过hash函数计算出对应槽，然后遍历链表查找或删除。
时间复杂度都和链表长度k成正比，即O(k)，所以查询的效率并非简单地O(1)，若hash函数设计得不好或loadFactor过高，都可能导致散列冲突发生的概率升高，查询效率下降。
对于散列均匀的hash函数，理论上：
k=n/m
其中n表示散列中数据的个数，m表示散列表中“槽”的个数。
优点
- 对内存的利用率比开放寻址法要高
因为链表结点可以在需要的时候再创建，并不需要像开放寻址法那样事先申请好。这也是链表优于数组的地方。 - 对大装载因子的容忍度更高。开放寻址法只能适用装载因子小于1的情况。接近1时，就可能会有大量的散列冲突，导致大量的探测、再散列等，性能会下降很多。但是对于链表法来说，只要散列函数的值随机均匀，即便装载因子变成10，也就是链表的长度变长了而已，虽然查找效率有所下降，但是比起顺序查找还是快很多。
缺点
链表因为要存储指针，所以对于比较小的对象的存储，是比较消耗内存的，还有可能会让内存的消耗翻倍。而且，因为链表中的结点是零散分布在内存中的，不是连续的，所以对CPU缓存是不友好的，这方面对于执行效率也有一定的影响。
存储的是大对象，也就是说要存储的对象的大小远远大于一个指针的大小（4个字节或者8个字节），那链表中指针的内存消耗在大对象面前就可以忽略了。
对链表法稍加改造，可以实现一个更加高效的散列表。那就是，我们将链表法中的链表改造为其他高效的动态数据结构，比如跳表、红黑树。这样，即便出现散列冲突，极端情况下，所有的数据都散列到同一个桶内，那最终退化成的散列表的查找时间也只不过是O(logn)。这样也就有效避免了前面讲到的散列碰撞攻击。
基于链表的散列冲突处理方法比较适合存储大对象、大数据量的散列表，而且，比起开放寻址法，它更加灵活，支持更多的优化策略，比如用红黑树代替链表。
