性能漫谈之HashMap、TreeMap、ConcurrentHashMap性能对比

Java语言中的HashMapConcurrentHashMap应该是最常用的两种Map了吧,通常分别应用于非线程安全和线程安全的场景中。但是它们两个的性能差别到底如何,估计没有几个人知道,本着打破砂锅测到底的精神,我来简单测试与剖析一下。

性能测试

测试的对象包括HashMapTreeMapConcurrentHashMap,以及LinkedHashMap作为陪跑选手。

测试样本数据量分三档128102410240,分别采用随机字符串构造相应大小的Map实例,然后在Benchmark中执行get读取操作,关键代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
static {
for (int i = 0; i < INIT_SIZE; i++) {
String key = RandomStringUtils.randomAlphanumeric(16);
HASH_MAP.put(key, key);
TREE_MAP.put(key, key);
LINKED_MAP.put(key, key);
CONCURRENT_MAP.put(key, key);
}
}

@Benchmark
public void hashBenchmark() {
HASH_MAP.get(KEY);
}

@Benchmark
public void linkedBenchmark() {
LINKED_MAP.get(KEY);
}

@Benchmark
public void treeBenchmark() {
TREE_MAP.get(KEY);
}

@Benchmark
public void concurrentBenchmark() {
CONCURRENT_MAP.get(KEY);
}

完整Benchmark可以直接查阅我的GitHub源代码,最终测试结果如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
128只读get性能测试:
Benchmark Mode Cnt Score Error Units
MapBenchmark.concurrentBenchmark avgt 9 2.150 ± 0.336 ns/op
MapBenchmark.hashBenchmark avgt 9 2.385 ± 0.824 ns/op
MapBenchmark.linkedBenchmark avgt 9 1.803 ± 0.024 ns/op
MapBenchmark.treeBenchmark avgt 9 16.419 ± 3.218 ns/op
1K只读get性能测试:
Benchmark Mode Cnt Score Error Units
MapBenchmark.concurrentBenchmark avgt 9 1.931 ± 0.176 ns/op
MapBenchmark.hashBenchmark avgt 9 2.052 ± 0.010 ns/op
MapBenchmark.linkedBenchmark avgt 9 2.139 ± 0.570 ns/op
MapBenchmark.treeBenchmark avgt 9 23.650 ± 3.106 ns/op
10K只读get性能测试:
Benchmark Mode Cnt Score Error Units
MapBenchmark.concurrentBenchmark avgt 9 2.028 ± 0.394 ns/op
MapBenchmark.hashBenchmark avgt 9 2.148 ± 0.224 ns/op
MapBenchmark.linkedBenchmark avgt 9 1.971 ± 0.221 ns/op
MapBenchmark.treeBenchmark avgt 9 43.367 ± 7.577 ns/op

根据测试结果,结合自己对这些Map实现算法的理解可以得出如下结论:

  1. 红黑树的检索速度不如哈希表,尤其是数据量变大会导致树层级太深,从而更加拖慢检索性能。
  2. LinkedHashMapHashMap性能差不多,一般情况下哈希表节点中链表与数组影响不大。
  3. ConcurrentHashMap的检索速度比HashMap要更快一点。

前两条结论在预期之内,但是第三条就有的奇怪了,为什么额外支持了线程安全的ConcurrentHashMap读操作反而要更快了一些呢?即便是它没有使用锁,也不应该比HashMap更快啊,何况它们的get()逻辑基本相同。

Volatile速度更快吗?

由于ConcurrentHashMap内部的哈希表table字段有额外的volatile描述符,怀疑其对于内存的读写速度有优化效果,所以决定简单测试一下:

1
2
3
4
5
6
7
8
9
10
11
12
private static long counter1 = 0L;
private static volatile long counter2 = 0L;

@Benchmark
public void normal() {
counter1 += 1;
}

@Benchmark
public void volat() {
counter2 += 2;
}

其测试结果证明,单纯volatile并没有性能优化,并且IDE警告Non-atomic operation on volatile field,说明这种用法是不合规的:

1
2
3
Benchmark                                     Mode  Cnt   Score    Error   Units
VolatileBenchmark.normal avgt 9 1.354 ± 0.011 ns/op
VolatileBenchmark.volat avgt 9 6.438 ± 0.032 ns/op

Unsafe才是关键

仔细阅读ConcurrentHashMap你会发现,它内部除了volatile修饰符之外,在table读写时都借助于Unsafe进行数组操作,于是乎参考它的实现重新进行volatile测试:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
private static Object[] arr1 = new Object[100];
private static volatile Object[] arr2 = new Object[1000];

@Benchmark
public void normal() {
Object o = arr1[3];
}

@Benchmark
public void volat() {
Object o = U.getObjectVolatile(arr2, ((long) 3 << ASHIFT) + ABASE);
}

// Unsafe mechanics
private static final sun.misc.Unsafe U;
private static final long ABASE;
private static final int ASHIFT;

static {
try {
U = createUnsafe();
Class<?> ak = Object[].class;
ABASE = U.arrayBaseOffset(ak);
int scale = U.arrayIndexScale(ak);
if ((scale & (scale - 1)) != 0)
throw new Error("data type scale not a power of two");
ASHIFT = 31 - Integer.numberOfLeadingZeros(scale);
} catch (Exception e) {
throw new Error(e);
}
}

以上测试代码测试结果如下:

1
2
3
Benchmark                                     Mode  Cnt   Score     Error   Units
VolatileBenchmark.normal avgt 9 0.512 ± 0.004 ns/op
VolatileBenchmark.volat avgt 9 0.255 ± 0.002 ns/op

看到这个测试数据,终于明白了ConcurrentHashMap在之前的测试中为什么速度始终比HashMap0.2ns左右,原来优化点就在于这个Unsafe操作。

以上测试代码可以从我的GitHub仓库中拉下来完整查看与运行。

结论

TreeMap的红黑树结构导致它天然的性能偏低,如非必须则不要使用它。

ConcurrentHashMap在一般情况下表现比HashMap还要更好一点点,考虑到它额外支持的线程安全,我们可以养成使用ConcurrentHashMap的好习惯。