性能漫谈之哈希表(HashMap)与二分法查找(BinarySearch)

哈希表与二分法查找是两种非常通用的快速检索算法,前者在绝大部分语言中都有相应的实现,如Java语言中的HashMapGolang语言中的map。本文将针对这两种算法进行性能对比与浅析,语言上将交替采用JavaGolang两种语言。

算法浅析

哈希算法以及哈希表的原理,在许多地方都可以见到。以Java语言中的HashMap为例,可以根据哈希算法计算出key的哈希值,取模后挂载入链表组成的数组中。Java中哈希表检索的源码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 && (e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h)
if ((ek = e.key) == key || (ek != null && key.equals(ek))) return e.val;
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null)
if (e.hash == h && ((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
return null;
}

二分法查找的数据源必须是一个有序数组,此处以Golang语言针对有序int[]实现二分法查找:

1
2
3
4
5
6
7
8
9
10
11
func binarySearch(arr []int, val int) int {
low := 0
high := len(arr) - 1
for high >= low {
middle := (low + high) / 2
if arr[middle] == val { return middle }
if arr[middle] < val { low = middle + 1 }
if arr[middle] > val { high = middle - 1 }
}
return -1
}

以上代码分别取自JDK源码以及我自己的代码,为了方便阅读而改的更加紧凑。

由于算法特点所致,二分法查找的时间复杂度一般为O(logn),而哈希表查找的时间复杂度理论上为O(1),实际上受哈希取模后数据碰撞的影响,数据量变大之后会存在性能上的降低。

当然哈希表的O(1)也并不一定比二分法查找的O(logn)更快,因为前者需要进行额外的哈希运算等。所以在许多追求高性能的组件或系统中,也会采用有序数组的二分法查找来替代哈希表。

但是这种做法一定要慎重再慎重,不深入研究就随便采用二分法查找反而会带来额外的性能损耗。

性能测试

本章节采用Golang语言对以上两种算法进行性能测试对比,分别针对有序的int16[]进行二分法查找以及map[int16]bool进行哈希查找,具体源码参见我的GitHub仓库

最终测试结果如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
当数组长度为16时:
BenchmarkInt16Binary-12 200000000 5.90 ns/op 0 B/op 0 allocs/op
BenchmarkInt16Map-12 100000000 19.9 ns/op 0 B/op 0 allocs/op

当数组长度为64时:
BenchmarkInt16Binary-12 200000000 8.57 ns/op 0 B/op 0 allocs/op
BenchmarkInt16Map-12 50000000 26.2 ns/op 0 B/op 0 allocs/op

当数组长度为256时:
BenchmarkInt16Binary-12 100000000 11.5 ns/op 0 B/op 0 allocs/op
BenchmarkInt16Map-12 50000000 27.7 ns/op 0 B/op 0 allocs/op

当数组长度为1024时:
BenchmarkInt16Binary-12 100000000 15.6 ns/op 0 B/op 0 allocs/op
BenchmarkInt16Map-12 50000000 29.2 ns/op 0 B/op 0 allocs/op

当数组长度为10240时:
BenchmarkInt16Binary-12 50000000 27.7 ns/op 0 B/op 0 allocs/op
BenchmarkInt16Map-12 50000000 30.7 ns/op 0 B/op 0 allocs/op

当数组长度为50000时:
BenchmarkInt16Binary-12 30000000 40.5 ns/op 0 B/op 0 allocs/op
BenchmarkInt16Map-12 50000000 35.3 ns/op 0 B/op 0 allocs/op

以上Benchmark结果中BenchmarkInt16Binary-12表示二分法查找,而BenchmarkInt16Map-12表示哈希表查找。在这种最简单测试中,我们可以非常明显的看到数据量不超过10k时,BinarySearch的性能高于Map,而伴随着数据量的提升,BinarySearch的性能便开始下降。

但是千万不要浅尝辄止,这个结果并不代表二分法查找可以应用于所有的小数据场景。

反面案例

我在查阅Fastjson源代码时,偶然发现其中有用到BinarySearch进行快速检索,基于我自己对这两种算法的使用经验,感觉它的用法并不合理,本着实事求是的态度,特意针对这种实现方案进行测量研究。具体代码参见JavaBeanDeserializer.java,其中采用smartMatchHashArraysmartMatchHashArrayMapping维护二分法查找的索引,然后在smartMatch()中尝试使用它们优化FieldDeserializer的检索速度,大致逻辑如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
private final FieldDeserializer[]   fieldDeserializers;
private transient long[] smartMatchHashArray;
private transient short[] smartMatchHashArrayMapping;

// 建立哈希数组的逻辑
smartMatchHashArray = new long[sortedFieldDeserializers.length];
for (int i = 0; i < sortedFieldDeserializers.length; i++)
smartMatchHashArray[i] = TypeUtils.fnv1a_64_lower(sortedFieldDeserializers[i].fieldInfo.name);
Arrays.sort(smartMatchHashArray);

// 建立哈希数组索引的逻辑
smartMatchHashArrayMapping = new short[smartMatchHashArray.length];
Arrays.fill(smartMatchHashArrayMapping, (short) -1);
for (int i = 0; i < sortedFieldDeserializers.length; i++) {
int p = Arrays.binarySearch(smartMatchHashArray, TypeUtils.fnv1a_64_lower(sortedFieldDeserializers[i].fieldInfo.name));
if (p >= 0)
smartMatchHashArrayMapping[p] = (short) i;
}

// 通过BinarySearch检索key
long smartKeyHash = TypeUtils.fnv1a_64_lower(key);
int pos = Arrays.binarySearch(smartMatchHashArray, smartKeyHash);
int deserIndex = smartMatchHashArrayMapping[pos];
fieldDeserializer = sortedFieldDeserializers[deserIndex];

我采用同样的逻辑写了一款Java版的benchmark进行性能测试,最终性能表现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Item数量为64
Benchmark Mode Cnt Score Error Units
SearchBenchmark.binary avgt 9 348.692 ± 3.918 ns/op
SearchBenchmark.map avgt 9 169.892 ± 2.776 ns/op

Item数量为256
Benchmark Mode Cnt Score Error Units
SearchBenchmark.binary avgt 9 2014.112 ± 64.266 ns/op
SearchBenchmark.map avgt 9 890.706 ± 26.997 ns/op

Item数量为1024
Benchmark Mode Cnt Score Error Units
SearchBenchmark.binary avgt 9 43502.328 ± 2760.750 ns/op
SearchBenchmark.map avgt 9 5046.955 ± 336.107 ns/op

SearchBenchmark.binary表示二分法查找,SearchBenchmark.map表示哈希查找。每一轮测试都会针对全部数据进行相应算法的快速检索,测量值为总耗时,希望以此避免单个key的随机性所造成测量数据不准的情况。

在这份测试数据中,我们可以发现二分法查找的性能全面落后于哈希查找,即便64个样本的测试中它也远低于后者,而Fastjson源代码里面针对小于128的数组都采用这种低效的算法,实在令人费解。

我也采用Golang语言实现了相同的benchmark,具体测试代码参见这里。这个代码没有任何依赖,可以直接复制走自己运行,其具体测试结果如下:

1
2
3
4
5
6
7
8
9
10
11
数据量为64
BenchmarkBinarySearch-12 300000 4157 ns/op 1024 B/op 64 allocs/op
BenchmarkMapSearch-12 2000000 745 ns/op 0 B/op 0 allocs/op

数据量为256
BenchmarkBinarySearch-12 100000 23523 ns/op 4096 B/op 256 allocs/op
BenchmarkMapSearch-12 500000 3511 ns/op 0 B/op 0 allocs/op

数据量为1024
BenchmarkBinarySearch-12 10000 116149 ns/op 16384 B/op 1024 allocs/op
BenchmarkMapSearch-12 100000 20021 ns/op 0 B/op 0 allocs/op

BenchmarkBinarySearch-12表示二分法查找,BenchmarkMapSearch-12表示哈希表查找。

可以看到在这份测试中,二分法查找的性能整体同样大幅落后于哈希查找,有意思的是数据量增加的过程中它们的性能波动曲线相同。并且Java版与Golang版实现逻辑基本相同,但是最终性能表现差距较大。

BTW,Fastjson的代码质量真的是有够差的。