Java 8 HashMap性能

Java 8 HashMap get方法比Java 7快20%,100万个条目单次查找时间小于10纳秒。

在Intel Core i7 @2.4 GHz/8G RAM/64位JVM上执行的基准测试结果。

HashMap将数据存储在多个桶中,每个桶都是一个链表。

新元素以索引方式添加到存储桶。

Java 8以前,哈希冲突会大大降低HashMap性能。

从HashMap检索元素的时间从O(1)增加到O(n)。

Java 8新策略在达到一定阈值后,使用红黑树替换链表结构。

HashMap在链表中存储Entry对象,链表上对象数大于阈值后,链表改为平衡树确保最坏情况下性能为O(logN)。

影响HashMap性能的两个参数:

初始化大小和临界阀值。默认值:new HashMap(16,0.75f)。

16为数组的长度,0.75f是HashMap默认扩容阀值,元素个数超出阀值(16*0.75f)时,扩容基于当前数组长度成倍增加(oldCap << 1),将原数组的元素复制到新数组中,新容量阀值会成倍增长(oldThr << 1)。

当数组某个下标上的链表长度超过8时,下标上的链表结构被替换成红黑树,以解决哈希碰撞下的效率问题。

注:hashing动态演示程序

选择依据

ConcurrentHashMap

旨在吞吐量和线程安全间寻求平衡,提出一个结构和指导。

ConcurrentNavigableMap

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

LinkedHashMap

与HashMap非常相似,映射基于哈希表和链表,以双向链表增强哈希映射功能。

维护双向链表的额外开销导致LinkedHashMap比HashMap的常量时间稍差。

在迭代过程中线性时间优于HashMap。

初始值过高不会产生像HashMap那么严重的影响,迭代次数不受容量影响。

ConcurrentSkipListMap

适合对键执行排序的场景,是TreeMap并发版,是SkipList的变种。

TreeMap

默认对所有条目按自然顺序排序、整数升序、字母顺序。实现了NavigableMap接口,内部结构为红黑树。

对比

HashMap

作为通用映射实现,提供快速存储和检索操作。

条目混乱和不规则安排不能满足一些场景,大量迭代表现不佳,底层数组容量对遍历产生影响。

LinkedHashMap

拥有和HashMap一样的良好属性,为条目引入顺序,大量迭代时表现会更好。

TreeMap

键的排序方式可控,相对前面两种Map,性能稍差些。

LinkedHashMap

键有序,性能比TreeMap好。