Hash表(四)——Hash冲突解决办法&HashMap分析

1 合理选择 Hash冲突解决办法

在Hash表(二)——散列冲突中学到常用的解决 Hash冲突的方法有开放寻址法和链表法。在 Java中 ThreadLocalMap采用线性探测的开放寻址法来解决冲突， LinkedHashMap采用了链表法解决 Hash冲突，现将开放寻址法和链表法总结如下。

1.1 开放寻址法

• 优点：将数据存储在数组中；利用CPU缓存加快查询速度；并且序列化简单。
• 缺点：删除数据麻烦，需要特殊标记已删除的数据；需要将所有数据存储在一个连续的存储空间中，比起链表来说，冲突的代价更高。
• 适用场景：当数据量较小、装载因子小的时候可以采用开放寻址法。

1.2 链表法

• 优点：对内存利用率高；对装载因子的容忍度高（开放寻址法只适用在装载因子小于1的情况，接近1时，就可能会有大量散列冲突，导致大量的探测、再散列，性能下降很多。但对于链表法，只要散列函数的值随机均匀，当装载因子大于1时，只是对应的链表长度增加，这里也可以通过将链表改造为跳表或者红黑树的方式加快查找速度）
• 缺点：由于链表需要存储指针，存储较小的对象时，指针占用的内容消耗比较大；链表不支持随机查找，查找效率较低。
• 适用场景：适合于存储大对象、数据量大的散列表；比开放寻址法更加灵活，支持更多的优化策略，如使用红黑树替代链表。
• 优化：我们可将链表法中的链表替换成更加高效的动态的数据结构，如跳表、红黑树等。 如下图所示，将链表优化为红黑树。

2 Java中的 HashMap分析

HashMap是一个成熟的散列表，在Java中得到了广泛应用，下面来具体分析。

2.1 初始大小

如下图所示， HashMap默认的初始大小为16。

如果事先知道数据量的大小，可以通过修改初始大小，减少动态扩容次数，来提升 HashMap性能。

2.2 装载因子和动态扩容

如下图所示， HashMap默认的装载因子为0.75。

当 HashMap中元素个数超过 0.75*capacity（ capacity表示 HashMap实际的容量），就会启动动态扩容，每次扩容的大小为原来的两倍。

2.3 Hash冲突的解决办法

在 JDK1.8之前， HashMap底层采用的链表法来解决冲突。即使装载因子和 Hash函数设计的再合理，随着数据量的增加也会出现链表过长的情况，一旦链表过长，严重影响了 HashMap的性能。

在 JDK1.8中对 HashMap底层做了优化。当链表长度大于8时，链表就转化为红黑树，当链表小于8时，将红黑树转化为链表。因为当链表过长的时候，查找的效率将会变慢，利用红黑树快速增删改查的特性，可以提高 HashMap的性能，而链表不长时，红黑树的快速增删改查的特性就不太明显，并且红黑树的还有维护成本，因此当链表不长时，不需要将链表转化为红黑树。

2.4 Hash函数

HashMap中的 Hash函数如下图所示，追求简单高效且分布均匀。