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性能。

检索元素的时间从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)。

注:hashing动态演示程序

选择依据

ConcurrentHashMap

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

ConcurrentNavigableMap

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

LinkedHashMap

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

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

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

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

ConcurrentSkipListMap

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

TreeMap

默认按自然顺序排序、整数升序、字母顺序。

实现NavigableMap接口,内部结构为红黑树。

对比

HashMap

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

大量迭代表现不佳,底层数组容量对遍历产生影响。

Map m = new HashMap();
m.put("1","1");
m.put("3","3");
m.put("2","2");
m.put("5","5");
m.put("4","4");
m.forEach((k, v) -> {
	System.out.println(k+":"+v);
});
//console:
1:1
2:2
3:3
4:4
5:5

LinkedHashMap

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

Map m = new LinkedHashMap();
m.put("1","1");
m.put("3","3");
m.put("2","2");
m.put("5","5");
m.put("4","4");
m.forEach((k, v) -> {
	System.out.println(k+":"+v);
});
//console:
1:1
3:3
2:2
5:5
4:4

TreeMap

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

LinkedHashMap

键有序,性能比TreeMap好。