These are benchmarks of how the different Rust hashing algorithm implementations compare. In particular, they are using the Hasher interface, which may not be optimal for all algorithms. Implementation quality may also vary.

Variance bars excluded because this dang charting library was absolutely freaking out with them. Note also that both axes are on a log-scale, so small vertical differences may actually represent a large difference.

Source Can be Found Here

The hash functions on display are:

SipHash 1-3 (sip): This is the state-of-the-art for hashing that is completely resistant against even theoretical hash flooding DDOS attacks when paired with a random seed. While most applications probably do not require this, it's important for some usecases (for instance, many webservers can be completely locked up by POST requests with colliding keys). Since this is a relatively obscure attack, but quite costly when applicable, we believe that it's important to default to such a hash function. As such, this is the default hasher used by Rust's HashMap, but another hasher can be substituted as needed. SipHash's performance is really good for medium input lengths.

SipHash 2-4 (sip): Similar to SipHash 1-3, SipHash 2-4 has more robust cryptanalysis but is still not suitable for cryptographic purposes. SipHash 1-3 is perfectly adequate for solving the hash flooding DDOS problem at hand. SipHash 2-4 is a common hashing algorithm in many languages.

Fowler-Noll-Vo (fnv): A hash function with excellent distribution, but no particular cryptographic properties. FNV is the best at small inputs, but does terribly on large inputs. Since small inputs are much more common, it's the Rust community's most popular override for SipHash where security doesn't matter. The Rust compiler itself uses this function.

xxHash (xx): Like fnv, a hash function with good distribution, but no crypto. It's our best performer for large inputs, and performs strongly on small ones.

Horner (horner): A universal hash function without the full cryptographic strength of SipHash. It defends against all hash flooding attacks that have been demonstrated in practice, but is theoretically vulnerable to a timing attack if the attacker is allowed to continuously query against maps with the same seed. It's unclear how practical this attack is under ideal conditions for the attacker, but for most situations this hasher is likely sufficient. Performance is roughly on-par with xxHash.

btree is not a hash function at all, but rather feeding the same inputs into Rust's BTreeMap, which is based on comparisons instead of hashing. This serves as a baseline, as well as a demonstration of how ordered data structures can completely stomp unordered data structures under particular workloads, even when not used for their ordering properties.

The deliberately excluded hash functions are:

FarmHash (farm): Another decent distribution, but no crypto. This algorithm is intended to perform excellently on all sizes of input, but is massively pessimized by Rust's streaming hashing architecture, as it's designed to process the input in one shot, forcing the entire input to be buffered in a growable array. In order for it to compete, Rust needs to adopt a solution that allows the top-level type in a hashing to identify whether it can be hashed in a one-shot manner, for a specialized result. However this can lead to confusing or inconsistent results, particularly if hashing derivation is done incorrectly.