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)

Ahash

Ahash crate

Ahash benchmark graph made in Criterion

Additional Statistics:

Lower boundEstimateUpper bound
Slope338.81 µs340.25 µs342.02 µs
R²0.95851020.96067610.9574668
Mean338.14 µs339.03 µs340.11 µs
Std. Dev.2.9573 µs5.0396 µs7.3343 µs
Median337.89 µs338.44 µs339.14 µs
MAD2.0893 µs2.8450 µs3.6274 µs

Blake3

blake3 crate

Blake3 benchmark graph made in Criterion

Additional Statistics:

Lower boundEstimateUpper bound
R²0.00113500.00116880.0011170
Mean4.4504 ms4.4721 ms4.4993 ms
Std. Dev.59.649 µs126.51 µs187.84 µs
Median4.4300 ms4.4365 ms4.4482 ms
MAD29.871 µs44.864 µs60.767 µs

Cityhasher

cityhasher crate

Cityhasher benchmark graph made in Criterion

Additional Statistics:

Lower boundEstimateUpper bound
Slope687.10 µs689.90 µs693.80 µs
R²0.96341610.96548140.9614887
Mean686.78 µs688.14 µs689.85 µs
Std. Dev.3.7982 µs7.9376 µs11.973 µs
Median686.49 µs687.83 µs688.52 µs
MAD2.9458 µs3.9158 µs4.8434 µs

Rust’s default hasher (SipHasher)

The hasher in the standard library :)

Rust’s SipHasher benchmark graph made in Criterion

Additional Statistics:

Lower boundEstimateUpper bound
R²0.00839390.00869350.0083511
Mean2.1699 ms2.1747 ms2.1799 ms
Std. Dev.19.351 µs25.374 µs30.680 µs
Median2.1668 ms2.1718 ms2.1753 ms
MAD13.096 µs16.616 µs22.484 µs

Fasthash

fasthash crate

Fasthash benchmark graph made in Criterion

Additional Statistics:

Lower boundEstimateUpper bound
Slope351.77 µs353.82 µs357.12 µs
R²0.90779950.91173750.9015936
Mean351.74 µs353.01 µs354.57 µs
Std. Dev.3.8843 µs7.2967 µs10.761 µs
Median351.06 µs351.67 µs352.46 µs
MAD2.3063 µs2.9218 µs4.0742 µs

FNV

FNV crate

FNV benchmark graph made in Criterion

Additional Statistics:

Lower boundEstimateUpper bound
R²0.00176760.00183530.0017671
Mean8.9217 ms8.9375 ms8.9534 ms
Std. Dev.71.171 µs81.234 µs90.136 µs
Median8.9249 ms8.9456 ms8.9589 ms
MAD62.277 µs85.589 µs111.14 µs

GxHash

GxHash crate

GxHash benchmark graph made in Criterion

Additional Statistics:

Lower boundEstimateUpper bound
Slope341.59 µs344.24 µs347.77 µs
R²0.87570050.88224050.8707313
Mean340.64 µs342.00 µs343.66 µs
Std. Dev.4.3321 µs7.7920 µs11.196 µs
Median340.11 µs340.60 µs341.45 µs
MAD2.2106 µs3.0310 µs3.8211 µs

Highway

highway crate

highway benchmark graph made in Criterion

Additional Statistics:

Lower boundEstimateUpper bound
Slope806.07 µs809.13 µs812.91 µs
R²0.96062040.96248940.9596294
Mean804.24 µs806.99 µs810.29 µs
Std. Dev.8.8662 µs15.629 µs22.160 µs
Median802.98 µs804.86 µs806.18 µs
MAD4.2856 µs5.5378 µs7.3743 µs

Hud Slice By 8

hud_slice_by_8 crate

highway benchmark graph made in Criterion

Additional Statistics:

Lower boundEstimateUpper bound
R²0.04945940.05120500.0493473
Mean3.6245 ms3.6294 ms3.6345 ms
Std. Dev.20.855 µs25.670 µs30.210 µs
Median3.6201 ms3.6273 ms3.6336 ms
MAD16.777 µs23.124 µs29.173 µs

Meowhash

meowhash crate

Meowhash benchmark graph made in Criterion

Additional Statistics:

Lower boundEstimateUpper bound
Slope331.04 µs333.22 µs336.03 µs
R²0.84508170.84951190.8421135
Mean331.04 µs333.00 µs335.38 µs
Std. Dev.5.2511 µs11.249 µs15.575 µs
Median330.02 µs330.46 µs331.54 µs
MAD2.1435 µs2.6588 µs3.8049 µs

rustc_hash

rustc_hash crate

Rustc_hash benchmark graph made in Criterion

Additional Statistics:

Lower boundEstimateUpper bound
Slope467.44 µs468.62 µs470.30 µs
R²0.98114590.98200670.9802488
Mean467.07 µs468.03 µs469.09 µs
Std. Dev.3.6312 µs5.2018 µs6.7921 µs
Median466.40 µs467.22 µs467.95 µs
MAD2.1162 µs2.7135 µs3.8039 µs

wyhash

wyhash crate

wyhash benchmark graph made in Criterion

Additional Statistics:

Lower boundEstimateUpper bound
Slope655.64 µs659.54 µs666.00 µs
R²0.84642130.84992680.8403519
Mean657.05 µs660.88 µs665.86 µs
Std. Dev.6.0535 µs22.966 µs34.402 µs
Median655.55 µs656.90 µs658.31 µs
MAD3.7501 µs5.2448 µs6.9104 µs

xxh3

twox-hash crate

twox-hash benchmark graph made in Criterion

Additional Statistics:

Lower boundEstimateUpper bound
Slope659.17 µs661.56 µs664.04 µs
R²0.96719660.96881390.9670582
Mean657.86 µs660.22 µs662.85 µs
Std. Dev.9.2149 µs12.866 µs16.513 µs
Median654.77 µs656.81 µs658.52 µs
MAD5.5970 µs8.1636 µs10.199 µs

xxhash-rust (“xxh3” feature enabled)

xxhash-rust crate

xxhash-rust benchmark graph made in Criterion

Additional Statistics:

Lower boundEstimateUpper bound
Slope576.27 µs587.61 µs602.06 µs
R²0.47932680.49375870.4707473
Mean572.73 µs579.09 µs586.57 µs
Std. Dev.20.630 µs35.637 µs49.651 µs
Median567.49 µs569.11 µs570.92 µs
MAD6.1172 µs7.5161 µs12.285 µs

General

These are the general comparisons between all hashing algothims on several benches.

3 Bytes

Benchmark of all algorithms above on 3 bytes

10 Bytes

Benchmark of all algorithms above on 10 bytes

100 Bytes

Benchmark of all algorithms above on 10 bytes

Hashing a “short” Wikipedia article

Benchmark of all algorithms above on 10 bytes

Hashing a “long” Wikipedia article

Benchmark of all algorithms above on 10 bytes