Java 8中的HashMap性能改进到底有多快

Java 8的HashMap.get(obj)方法平均比Java 7快20%,HashMap在100万条目(entries)中,单次查找时间小于10纳秒。

这只是在Intel Core i7 @2.4 GHz/8G RAM/64位JVM上执行的基准测试。如果想对hash结构和操作过程有个清晰的理解,可以能过hashing动态演示程序进行全面的了解。

在Java中影响HashMap性能的参数有两个,初始化大小和临界阀值,默认值为new HashMap(16,0.75f)。16为数组的长度,0.75f是HashMap默认的扩容阀值(比例),当元素个数超过阀值(16*0.75f)时,扩容会基于当前数组的长度成倍增加(oldCap << 1),得到新的数组,并把原数组中的元素(链表)复制到新数组,新的容量阀值也成倍增长(oldThr << 1)。

当数组某一个下标上的链表的长度超过8时,这个下标上对应的链表(Node)会被替换成红黑树(TreeNode),以此来提高大量条目(entries)下的操作效率。以下是Java各种Map实现的适用场景:

ConcurrentHashMap

旨在解决吞吐量,和线程安全之间的平衡问题,而提出的一个结构和指导。

ConcurrentNavigableMap

作为ConcurrentMap的补充,ConcurrentNavigableMap支持对键(key)的总体排序(默认按升序排列)。

LinkedHashMap

在很多方面,LinkedHashMap与HashMap非常相似,LinkedHashMap映射基于哈希表和链表,它实现的是双向链表,以增强哈希映射的功能。

由于维护双向链表的额外开销,LinkedHashMap可能比HashMap的常量时间稍差,但LinkedHashMap在迭代过程中,线性时间优于HashMap。

对于LinkedHashMap而言,为初始容量选择过高的值,不会像HashMap那样产生严重的影响,因为LinkedHashMap的迭代次数不受容量的影响。

ConcurrentSkipListMap

对键进行排序的场景使用ConcurrentSkipListMap,它是TreeMap的并发版本,ConcurrentSkipListMap是SkipList的一个变种实现。

TreeMap

默认情况下,TreeMap对所有条目(entries)按自然顺序进行排序。对于整数按升序,对于字符串按字母顺序。TreeMap实现了NavigableMap接口,其内部结构为红黑树。

TreeMap、HashMap、LinkedHashMap简单比较

HashMap作为通用的映射实现,提供快速存储和检索操作。然而,条目(entries)的混乱和不规则安排,不能满足一些场景,对大量的迭代表现不佳,鉴于底层数组的容量对遍历产生的影响,已不仅仅是条目数量的问题了。

LinkedHashMap拥有HashMap的良好属性,并为条目添加了顺序,在有大量迭代的情况下表现更好,因为无论容量如何,只考虑条目数。

TreeMap通过对键的排序方式可以控制,对排序需求的处理更得心应手,但相对于前面两种Map它的性能会较差。

LinkedHashMap不会出现像HashMap排序混乱的问题,也不会像TreeMap一样影响性能。