A vital piece of technologies in modern days is the hashing function, a function that takes in some input and returns a non-meaningful and unique output.
(As you can see, there’s no pattern)
As hash functions just take a sequence of bits, they are used in lots of scenarios. From vital (mostly builtin) structures like the HashMap, to authenticating users without storing their plain-text password, to detecting if a file has changed by storing its hash and checking it continuously.
So yeah, their useful. But I’m focused on performance, I’m the kind of person that obsesses with numbers, that tries to use the least number of electrons to perform a task, that values user’s time and computer resources more than gold. So…
What hashing algorithm is the best?
There are lots of hashing algorithms, some (like blake3) are secure in the cryptographic sense, meaning that they can be used for encryption without worrying about your data being unencrypted by a malicious actor. While others (like MD5) are not suitable for those purposes but excel in their ease of implementation.
As I wanted to check if the hashing algorithm used in the Rust compiler was optimal, I didn’t care for security, just speed. After publishing about my efforts, Ed Page reached to me about adding these benchmarks to his the rosetta-rs project
OK but where are the numbers
These benchmarks were measured on Wikipedia articles, for the full Criterion benchmark see here.
(Click for a zoomable SVG version)
Specific benchmarks:
Comparisons:
Ahash
Additional Statistics:
| Lower bound | Estimate | Upper bound | |
|---|---|---|---|
| Slope | 338.81 µs | 340.25 µs | 342.02 µs |
| R² | 0.9585102 | 0.9606761 | 0.9574668 |
| Mean | 338.14 µs | 339.03 µs | 340.11 µs |
| Std. Dev. | 2.9573 µs | 5.0396 µs | 7.3343 µs |
| Median | 337.89 µs | 338.44 µs | 339.14 µs |
| MAD | 2.0893 µs | 2.8450 µs | 3.6274 µs |
Blake3
Additional Statistics:
| Lower bound | Estimate | Upper bound | |
|---|---|---|---|
| R² | 0.0011350 | 0.0011688 | 0.0011170 |
| Mean | 4.4504 ms | 4.4721 ms | 4.4993 ms |
| Std. Dev. | 59.649 µs | 126.51 µs | 187.84 µs |
| Median | 4.4300 ms | 4.4365 ms | 4.4482 ms |
| MAD | 29.871 µs | 44.864 µs | 60.767 µs |
Cityhasher
Additional Statistics:
| Lower bound | Estimate | Upper bound | |
|---|---|---|---|
| Slope | 687.10 µs | 689.90 µs | 693.80 µs |
| R² | 0.9634161 | 0.9654814 | 0.9614887 |
| Mean | 686.78 µs | 688.14 µs | 689.85 µs |
| Std. Dev. | 3.7982 µs | 7.9376 µs | 11.973 µs |
| Median | 686.49 µs | 687.83 µs | 688.52 µs |
| MAD | 2.9458 µs | 3.9158 µs | 4.8434 µs |
Rust’s default hasher (SipHasher)
The hasher in the standard library :)
Additional Statistics:
| Lower bound | Estimate | Upper bound | |
|---|---|---|---|
| R² | 0.0083939 | 0.0086935 | 0.0083511 |
| Mean | 2.1699 ms | 2.1747 ms | 2.1799 ms |
| Std. Dev. | 19.351 µs | 25.374 µs | 30.680 µs |
| Median | 2.1668 ms | 2.1718 ms | 2.1753 ms |
| MAD | 13.096 µs | 16.616 µs | 22.484 µs |
Fasthash
Additional Statistics:
| Lower bound | Estimate | Upper bound | |
|---|---|---|---|
| Slope | 351.77 µs | 353.82 µs | 357.12 µs |
| R² | 0.9077995 | 0.9117375 | 0.9015936 |
| Mean | 351.74 µs | 353.01 µs | 354.57 µs |
| Std. Dev. | 3.8843 µs | 7.2967 µs | 10.761 µs |
| Median | 351.06 µs | 351.67 µs | 352.46 µs |
| MAD | 2.3063 µs | 2.9218 µs | 4.0742 µs |
FNV
Additional Statistics:
| Lower bound | Estimate | Upper bound | |
|---|---|---|---|
| R² | 0.0017676 | 0.0018353 | 0.0017671 |
| Mean | 8.9217 ms | 8.9375 ms | 8.9534 ms |
| Std. Dev. | 71.171 µs | 81.234 µs | 90.136 µs |
| Median | 8.9249 ms | 8.9456 ms | 8.9589 ms |
| MAD | 62.277 µs | 85.589 µs | 111.14 µs |
GxHash
Additional Statistics:
| Lower bound | Estimate | Upper bound | |
|---|---|---|---|
| Slope | 341.59 µs | 344.24 µs | 347.77 µs |
| R² | 0.8757005 | 0.8822405 | 0.8707313 |
| Mean | 340.64 µs | 342.00 µs | 343.66 µs |
| Std. Dev. | 4.3321 µs | 7.7920 µs | 11.196 µs |
| Median | 340.11 µs | 340.60 µs | 341.45 µs |
| MAD | 2.2106 µs | 3.0310 µs | 3.8211 µs |
Highway
Additional Statistics:
| Lower bound | Estimate | Upper bound | |
|---|---|---|---|
| Slope | 806.07 µs | 809.13 µs | 812.91 µs |
| R² | 0.9606204 | 0.9624894 | 0.9596294 |
| Mean | 804.24 µs | 806.99 µs | 810.29 µs |
| Std. Dev. | 8.8662 µs | 15.629 µs | 22.160 µs |
| Median | 802.98 µs | 804.86 µs | 806.18 µs |
| MAD | 4.2856 µs | 5.5378 µs | 7.3743 µs |
Hud Slice By 8
Additional Statistics:
| Lower bound | Estimate | Upper bound | |
|---|---|---|---|
| R² | 0.0494594 | 0.0512050 | 0.0493473 |
| Mean | 3.6245 ms | 3.6294 ms | 3.6345 ms |
| Std. Dev. | 20.855 µs | 25.670 µs | 30.210 µs |
| Median | 3.6201 ms | 3.6273 ms | 3.6336 ms |
| MAD | 16.777 µs | 23.124 µs | 29.173 µs |
Meowhash
Additional Statistics:
| Lower bound | Estimate | Upper bound | |
|---|---|---|---|
| Slope | 331.04 µs | 333.22 µs | 336.03 µs |
| R² | 0.8450817 | 0.8495119 | 0.8421135 |
| Mean | 331.04 µs | 333.00 µs | 335.38 µs |
| Std. Dev. | 5.2511 µs | 11.249 µs | 15.575 µs |
| Median | 330.02 µs | 330.46 µs | 331.54 µs |
| MAD | 2.1435 µs | 2.6588 µs | 3.8049 µs |
rustc_hash
Additional Statistics:
| Lower bound | Estimate | Upper bound | |
|---|---|---|---|
| Slope | 467.44 µs | 468.62 µs | 470.30 µs |
| R² | 0.9811459 | 0.9820067 | 0.9802488 |
| Mean | 467.07 µs | 468.03 µs | 469.09 µs |
| Std. Dev. | 3.6312 µs | 5.2018 µs | 6.7921 µs |
| Median | 466.40 µs | 467.22 µs | 467.95 µs |
| MAD | 2.1162 µs | 2.7135 µs | 3.8039 µs |
wyhash
Additional Statistics:
| Lower bound | Estimate | Upper bound | |
|---|---|---|---|
| Slope | 655.64 µs | 659.54 µs | 666.00 µs |
| R² | 0.8464213 | 0.8499268 | 0.8403519 |
| Mean | 657.05 µs | 660.88 µs | 665.86 µs |
| Std. Dev. | 6.0535 µs | 22.966 µs | 34.402 µs |
| Median | 655.55 µs | 656.90 µs | 658.31 µs |
| MAD | 3.7501 µs | 5.2448 µs | 6.9104 µs |
xxh3
Additional Statistics:
| Lower bound | Estimate | Upper bound | |
|---|---|---|---|
| Slope | 659.17 µs | 661.56 µs | 664.04 µs |
| R² | 0.9671966 | 0.9688139 | 0.9670582 |
| Mean | 657.86 µs | 660.22 µs | 662.85 µs |
| Std. Dev. | 9.2149 µs | 12.866 µs | 16.513 µs |
| Median | 654.77 µs | 656.81 µs | 658.52 µs |
| MAD | 5.5970 µs | 8.1636 µs | 10.199 µs |
xxhash-rust (“xxh3” feature enabled)
Additional Statistics:
| Lower bound | Estimate | Upper bound | |
|---|---|---|---|
| Slope | 576.27 µs | 587.61 µs | 602.06 µs |
| R² | 0.4793268 | 0.4937587 | 0.4707473 |
| Mean | 572.73 µs | 579.09 µs | 586.57 µs |
| Std. Dev. | 20.630 µs | 35.637 µs | 49.651 µs |
| Median | 567.49 µs | 569.11 µs | 570.92 µs |
| MAD | 6.1172 µs | 7.5161 µs | 12.285 µs |
General
These are the general comparisons between all hashing algothims on several benches.
3 Bytes
10 Bytes
100 Bytes
Hashing a “short” Wikipedia article
Hashing a “long” Wikipedia article
