1 合理选择 Hash
冲突解决办法
在Hash表(二)——散列冲突中学到常用的解决 Hash
冲突的方法有开放寻址法和链表法。在 Java
中 ThreadLocalMap
采用线性探测的开放寻址法来解决冲突, LinkedHashMap
采用了链表法解决 Hash
冲突,现将开放寻址法和链表法总结如下。
2 Java
中的 HashMap
分析
HashMap
是一个成熟的散列表,在Java中得到了广泛应用,下面来具体分析。
如下图所示, HashMap
默认的初始大小为16。
如果事先知道数据量的大小,可以通过修改初始大小,减少动态扩容次数,来提升 HashMap
性能。
如下图所示, HashMap
默认的装载因子为0.75。
当 HashMap
中元素个数超过 0.75*capacity
( capacity
表示 HashMap
实际的容量),就会启动动态扩容,每次扩容的大小为原来的两倍。
Hash
冲突的解决办法 在 JDK1.8
之前, HashMap
底层采用的链表法来解决冲突。即使装载因子和 Hash
函数设计的再合理,随着数据量的增加也会出现链表过长的情况,一旦链表过长,严重影响了 HashMap
的性能。
在 JDK1.8
中对 HashMap
底层做了优化。当链表长度大于8时,链表就转化为红黑树,当链表小于8时,将红黑树转化为链表。因为当链表过长的时候,查找的效率将会变慢,利用红黑树快速增删改查的特性,可以提高 HashMap
的性能,而链表不长时,红黑树的快速增删改查的特性就不太明显,并且红黑树的还有维护成本,因此当链表不长时,不需要将链表转化为红黑树。
Hash
函数 HashMap
中的 Hash
函数如下图所示,追求简单高效且分布均匀。