从理论上讲,正确的答案是:使用可能专门为此而设计的
std::hash
,如果不适用,则使用良好的哈希函数而不是快速的哈希函数。哈希函数的速度并不那么重要,它的质量才更为重要。
实际上,答案是:使用
std::hash
,它很差劲,但表现出人意料之外的好。
在产生兴趣后,我在周末进行了约30小时的基准测试。除其他事项外,我试图获得平均情况与最坏情况,并尝试通过在插入的集合大小方面故意提供错误的桶计数提示,来迫使
std::unordered_map
呈现最坏情况的行为。
我比较了糟糕哈希值(
std::hash<T*>
)和著名的通用哈希值(djb2、sdbm),以及针对非常短的输入长度的这些变体,以及专门用于哈希表的哈希值(murmur2 和 murmur3),还有非常糟糕的哈希值,它们实际上比不进行哈希还要糟糕,因为它们丢失了熵。
由于指针的最低2-3位由于对齐而始终为零,因此我认为测试简单右移作为“哈希”是值得的,因此只使用非零信息,以防哈希表例如仅使用最低 N 位。结果证明,对于合理的移位(我也尝试过不合理的移位!)这实际上表现得相当好。
发现
我的一些发现是众所周知且毫不意外的,而其他的则非常惊人:
- 很难预测什么是“好”的哈希函数。编写好的哈希函数很困难。这不足为奇,是一个众所周知的事实,并再次得到证明。
- 没有单个哈希函数在每种情况下都显著优于其他所有哈希函数。没有单个哈希函数甚至在80%的时间内显着优于其他所有哈希函数。第一个结果是可以预料的,第二个结果尽管令人惊讶。
- 很难使
std::unordered_map
表现不佳。即使给出故意错误的桶计数提示,强制进行多次重新哈希,总体性能也不会差太多。只有那些以几乎荒谬的方式丢弃大部分熵的最坏的哈希函数才能显着影响性能超过10-20%(例如right_shift_12
,它实际上为50,000个输入产生了仅12个不同的哈希值!在这种情况下,哈希映射运行约慢100倍-我们基本上在链表上进行随机访问查找。)。
- 一些“有趣”的结果肯定是由于实现细节造成的。我的实现(GCC)使用略大于2 ^ N的素数桶计数,并将具有相同哈希值的值以头部优先插入到链接列表中。
std::hash<T * >
的特化对于GCC来说非常糟糕(一个简单的reinterpret_cast
)。有趣的是,一个做完全相同事情的函数对象在插入时表现更快,在随机访问时表现更慢。差异很小(在8-10秒的测试运行中有几十毫秒),但它不是噪音,它始终存在-可能与指令重排或流水线相关。这个代码完全相同的情况下,两种不同场景下的表现一致不同,这真是太惊人了。
- 可怜的哈希函数并不比“好”的哈希函数或专门设计用于哈希表的哈希函数表现得更差。实际上,它们有一半的时间是最好的表现者,或者是前三名之一。
- “最佳”哈希函数很少能够产生最佳的整体性能。
- 在此SO问题中发布的哈希函数通常是可以接受的。它们是良好的平均值,但不优于
std::hash
。通常它们会排在前3-4位。
- 较差的哈希函数对插入顺序有一定的敏感性(在随机插入和随机查找之后进行随机查找时表现更差),而“好”的哈希函数对插入顺序的影响更具弹性(几乎没有差异),但总体性能仍然稍慢。
测试设置
测试不仅针对任意的4字节或8字节(或其他)对齐的值,而是针对从堆上分配完整元素集合获得的实际地址进行的,并将地址存储在std::vector
中由分配器提供(然后删除对象,它们不再需要)。
地址按照存储在向量中的顺序插入到新分配的std::unordered_map
中,一次按原始顺序("sequential"),一次在向量上应用std::random_shuffle
后。
对大小为4、16、64、256和1024的50,000和1,000,000个对象进行了测试(此处省略了64的结果,因为篇幅过长,它们位于16和256之间-- StackOverflow只允许发布30k个字符)。
测试套件运行3次,结果有时相差3或4毫秒,但整体上是相同的。这里发布的结果是最后一次运行的结果。
"随机"测试中插入的顺序以及访问模式(在每个测试中)是伪随机的,但在测试运行中,每个哈希函数的顺序完全相同。
哈希基准测试中的时间是为了将4,000,000,000个哈希值相加到一个整数变量中。
列insert
是以毫秒为单位的时间,用于创建50个元素的std::unordered_map
,分别插入50,000和1,000,000个元素,并销毁该映射表的50次迭代。
列access
是以毫秒为单位的时间,用于在“vector”中查找100,000,000个伪随机元素,然后在unordered_map
中查找该地址。
对于大数据集(小数据集完全适合于L2),这个时间包括平均一个缓存未命中来访问vector
中的随机元素。
所有时间都在2.66GHz Intel Core2,Windows 7,gcc 4.8.1/MinGW-w64_32上进行。计时器粒度@ 1ms。
源代码
源代码在Ideone上可用,这是因为Stackoverflow有30k字符限制。
注意:在台式电脑上运行完整的测试套件需要超过2小时,因此如果您想重现结果,请准备好散步。
测试结果
Benchmarking hash funcs...
std::hash 2576
reinterpret_cast 2561
djb2 13970
djb2_mod 13969
sdbm 10246
yet_another_lc 13966
murmur2 11373
murmur3 15129
simple_xorshift 7829
double_xorshift 13567
right_shift_2 5806
right_shift_3 5866
right_shift_4 5705
right_shift_5 5691
right_shift_8 5795
right_shift_12 5728
MyTemplatePointerHash1 5652
BasileStarynkevitch 4315
--------------------------------
sizeof(T) = 4
sizeof(T*) = 4
insertion order = sequential
dataset size = 50000 elements
name insert access
std::hash 421 6988
reinterpret_cast 408 7083
djb2 451 8875
djb2_mod 450 8815
sdbm 455 8673
yet_another_lc 443 8292
murmur2 478 9006
murmur3 490 9213
simple_xorshift 460 8591
double_xorshift 477 8839
right_shift_2 416 7144
right_shift_3 422 7145
right_shift_4 414 6811
right_shift_5 425 8006
right_shift_8 540 11787
right_shift_12 1501 49604
MyTemplatePointerHash1 410 7138
BasileStarynkevitch 445 8014
--------------------------------
sizeof(T) = 4
sizeof(T*) = 4
insertion order = random
dataset size = 50000 elements
name insert access
std::hash 443 7570
reinterpret_cast 436 7658
djb2 473 8791
djb2_mod 472 8766
sdbm 472 8817
yet_another_lc 458 8419
murmur2 479 9005
murmur3 491 9205
simple_xorshift 464 8591
double_xorshift 476 8821
right_shift_2 441 7724
right_shift_3 440 7716
right_shift_4 450 8061
right_shift_5 463 8653
right_shift_8 649 16320
right_shift_12 3052 114185
MyTemplatePointerHash1 438 7718
BasileStarynkevitch 453 8140
--------------------------------
sizeof(T) = 4
sizeof(T*) = 4
insertion order = sequential
dataset size = 1000000 elements
name insert access
std::hash 8945 32801
reinterpret_cast 8796 33251
djb2 11139 54855
djb2_mod 11041 54831
sdbm 11459 36849
yet_another_lc 14258 57350
murmur2 16300 39024
murmur3 16572 39221
simple_xorshift 14930 38509
double_xorshift 16192 38762
right_shift_2 8843 33325
right_shift_3 8791 32979
right_shift_4 8818 32510
right_shift_5 8775 30436
right_shift_8 10505 35960
right_shift_12 30481 91350
MyTemplatePointerHash1 8800 33287
BasileStarynkevitch 12885 37829
--------------------------------
sizeof(T) = 4
sizeof(T*) = 4
insertion order = random
dataset size = 1000000 elements
name insert access
std::hash 12183 33424
reinterpret_cast 12125 34000
djb2 22693 51255
djb2_mod 22722 51266
sdbm 15160 37221
yet_another_lc 24125 51850
murmur2 16273 39020
murmur3 16587 39270
simple_xorshift 16031 38628
double_xorshift 16233 38757
right_shift_2 11181 33896
right_shift_3 10785 33660
right_shift_4 10615 33204
right_shift_5 10357 38216
right_shift_8 15445 100348
right_shift_12 73773 1044919
MyTemplatePointerHash1 11091 33883
BasileStarynkevitch 15701 38092
--------------------------------
sizeof(T) = 64
sizeof(T*) = 4
insertion order = sequential
dataset size = 50000 elements
name insert access
std::hash 415 8243
reinterpret_cast 422 8321
djb2 445 8730
djb2_mod 449 8696
sdbm 460 9439
yet_another_lc 455 9003
murmur2 475 9109
murmur3 482 9313
simple_xorshift 463 8694
double_xorshift 465 8900
right_shift_2 416 8402
right_shift_3 418 8405
right_shift_4 423 8366
right_shift_5 421 8347
right_shift_8 453 9195
right_shift_12 666 18008
MyTemplatePointerHash1 433 8191
BasileStarynkevitch 466 8443
--------------------------------
sizeof(T) = 64
sizeof(T*) = 4
insertion order = random
dataset size = 50000 elements
name insert access
std::hash 450 8135
reinterpret_cast 457 8208
djb2 470 8736
djb2_mod 476 8698
sdbm 483 9420
yet_another_lc 476 8953
murmur2 481 9089
murmur3 486 9283
simple_xorshift 466 8663
double_xorshift 468 8865
right_shift_2 456 8301
right_shift_3 456 8302
right_shift_4 453 8337
right_shift_5 457 8340
right_shift_8 505 10379
right_shift_12 1099 34923
MyTemplatePointerHash1 464 8226
BasileStarynkevitch 466 8372
--------------------------------
sizeof(T) = 64
sizeof(T*) = 4
insertion order = sequential
dataset size = 1000000 elements
name insert access
std::hash 9548 35362
reinterpret_cast 9635 35869
djb2 10668 37339
djb2_mod 10763 37311
sdbm 11126 37145
yet_another_lc 11597 39944
murmur2 16296 39029
murmur3 16432 39280
simple_xorshift 16066 38645
double_xorshift 16108 38778
right_shift_2 8966 35953
right_shift_3 8916 35949
right_shift_4 8973 35504
right_shift_5 8941 34997
right_shift_8 9356 31233
right_shift_12 13831 45799
MyTemplatePointerHash1 8839 31798
BasileStarynkevitch 15349 38223
--------------------------------
sizeof(T) = 64
sizeof(T*) = 4
insertion order = random
dataset size = 1000000 elements
name insert access
std::hash 14756 36237
reinterpret_cast 14763 36918
djb2 15406 38771
djb2_mod 15551 38765
sdbm 14886 37078
yet_another_lc 15700 40290
murmur2 16309 39024
murmur3 16432 39381
simple_xorshift 16177 38625
double_xorshift 16073 38750
right_shift_2 14732 36961
right_shift_3 14170 36965
right_shift_4 13687 37295
right_shift_5 11978 35135
right_shift_8 11498 46930
right_shift_12 25845 268052
MyTemplatePointerHash1 10150 32046
BasileStarynkevitch 15981 38143
--------------------------------
sizeof(T) = 256
sizeof(T*) = 4
insertion order = sequential
dataset size = 50000 elements
name insert access
std::hash 432 7957
reinterpret_cast 429 8036
djb2 462 8970
djb2_mod 453 8884
sdbm 460 9110
yet_another_lc 466 9015
murmur2 495 9147
murmur3 494 9300
simple_xorshift 479 8792
double_xorshift 477 8948
right_shift_2 430 8120
right_shift_3 429 8132
right_shift_4 432 8196
right_shift_5 437 8324
right_shift_8 425 8050
right_shift_12 519 11291
MyTemplatePointerHash1 425 8069
BasileStarynkevitch 468 8496
--------------------------------
sizeof(T) = 256
sizeof(T*) = 4
insertion order = random
dataset size = 50000 elements
name insert access
std::hash 462 7956
reinterpret_cast 456 8046
djb2 490 9002
djb2_mod 483 8905
sdbm 482 9116
yet_another_lc 492 8982
murmur2 492 9120
murmur3 492 9276
simple_xorshift 477 8761
double_xorshift 477 8903
right_shift_2 458 8116
right_shift_3 459 8124
right_shift_4 462 8281
right_shift_5 463 8370
right_shift_8 458 8069
right_shift_12 662 16244
MyTemplatePointerHash1 459 8091
BasileStarynkevitch 472 8476
--------------------------------
sizeof(T) = 256
sizeof(T*) = 4
insertion order = sequential
dataset size = 1000000 elements
name insert access
std::hash 9756 34368
reinterpret_cast 9718 34897
djb2 10935 36894
djb2_mod 10820 36788
sdbm 11084 37857
yet_another_lc 11125 37996
murmur2 16522 39078
murmur3 16461 39314
simple_xorshift 15982 38722
double_xorshift 16151 38868
right_shift_2 9611 34997
right_shift_3 9571 35006
right_shift_4 9135 34750
right_shift_5 8978 32878
right_shift_8 8688 30276
right_shift_12 10591 35827
MyTemplatePointerHash1 8721 30265
BasileStarynkevitch 15524 38315
--------------------------------
sizeof(T) = 256
sizeof(T*) = 4
insertion order = random
dataset size = 1000000 elements
name insert access
std::hash 14169 36078
reinterpret_cast 14096 36637
djb2 15373 37492
djb2_mod 15279 37438
sdbm 15531 38247
yet_another_lc 15924 38779
murmur2 16524 39109
murmur3 16422 39280
simple_xorshift 16119 38735
double_xorshift 16136 38875
right_shift_2 14319 36692
right_shift_3 14311 36776
right_shift_4 13932 35682
right_shift_5 12736 34530
right_shift_8 9221 30663
right_shift_12 15506 98465
MyTemplatePointerHash1 9268 30697
BasileStarynkevitch 15952 38349
--------------------------------
sizeof(T) = 1024
sizeof(T*) = 4
insertion order = sequential
dataset size = 50000 elements
name insert access
std::hash 421 7863
reinterpret_cast 419 7953
djb2 457 8983
djb2_mod 455 8927
sdbm 445 8609
yet_another_lc 446 8892
murmur2 492 9090
murmur3 507 9294
simple_xorshift 467 8687
double_xorshift 472 8872
right_shift_2 432 8009
right_shift_3 432 8014
right_shift_4 435 7998
right_shift_5 442 8099
right_shift_8 432 7914
right_shift_12 462 8911
MyTemplatePointerHash1 426 7744
BasileStarynkevitch 467 8417
--------------------------------
sizeof(T) = 1024
sizeof(T*) = 4
insertion order = random
dataset size = 50000 elements
name insert access
std::hash 452 7948
reinterpret_cast 456 8018
djb2 489 9037
djb2_mod 490 8992
sdbm 477 8795
yet_another_lc 491 9179
murmur2 502 9078
murmur3 507 9273
simple_xorshift 473 8671
double_xorshift 480 8873
right_shift_2 470 8105
right_shift_3 470 8100
right_shift_4 476 8333
right_shift_5 468 8065
right_shift_8 469 8094
right_shift_12 524 10216
MyTemplatePointerHash1 451 7826
BasileStarynkevitch 472 8419
--------------------------------
sizeof(T) = 1024
sizeof(T*) = 4
insertion order = sequential
dataset size = 1000000 elements
name insert access
std::hash 10910 38432
reinterpret_cast 10892 38994
djb2 10499 38985
djb2_mod 10507 38983
sdbm 11318 37450
yet_another_lc 11740 38260
murmur2 16960 39544
murmur3 16816 39647
simple_xorshift 16096 39021
double_xorshift 16419 39183
right_shift_2 10219 38909
right_shift_3 10012 39036
right_shift_4 10642 40284
right_shift_5 10116 38678
right_shift_8 9083 32914
right_shift_12 9376 31586
MyTemplatePointerHash1 8777 30129
BasileStarynkevitch 16036 38913
--------------------------------
sizeof(T) = 1024
sizeof(T*) = 4
insertion order = random
dataset size = 1000000 elements
name insert access
std::hash 16304 38695
reinterpret_cast 16241 39641
djb2 16377 39533
djb2_mod 16428 39526
sdbm 15402 37811
yet_another_lc 16180 38730
murmur2 16679 39355
murmur3 16792 39586
simple_xorshift 16196 38965
double_xorshift 16371 39127
right_shift_2 16445 39263
right_shift_3 16598 39421
right_shift_4 16378 39839
right_shift_5 15517 38442
right_shift_8 11589 33547
right_shift_12 11992 49041
MyTemplatePointerHash1 9052 30222
BasileStarynkevitch 16163 38829
T
在unordered_set<T>
中的对齐方式。例如,当T
是一个 32 位的int
时,在 32 位和 64 位机器上只有最低的 2 位是 0。 - Maxim Egorushkinint
不是指针。由malloc
/new
返回的32位指针有1个零LSB,64位指针有3个零LSB。当然,您可以拥有不是malloc
/new
结果的指针,因此如果对象足够小,则会发生一些冲突。 - egurunordered_set<int*>
。那些'int'可以被存储在其他位置的数组中,因此自然情况下,在32位和64位平台上,'int*'将只有2个零LSB。 - Maxim Egorushkin