Skip to content

Custom hash algorithm used by rustc (plus hashmap/set aliases): fast, deterministic, not secure

License

Apache-2.0, MIT licenses found

Licenses found

Apache-2.0
LICENSE-APACHE
MIT
LICENSE-MIT
Notifications You must be signed in to change notification settings

rust-lang/rustc-hash

rustc-hash

crates.io Documentation

A speedy, non-cryptographic hashing algorithm used by rustc. The hash map in std uses SipHash by default, which provides resistance against DOS attacks. These attacks aren't a concern in the compiler so we prefer to use a quicker, non-cryptographic hash algorithm.

The original hash algorithm provided by this crate was one taken from Firefox, hence the hasher it provides is called FxHasher. This name is kept for backwards compatibility, but the underlying hash has since been replaced. The current design for the hasher is a polynomial hash finished with a single bit rotation, together with a wyhash-inspired compression function for strings/slices, both designed by Orson Peters.

For rustc we have tried many different hashing algorithms. Hashing speed is critical, especially for single integers. Spending more CPU cycles on a higher quality hash does not reduce hash collisions enough to make the compiler faster on real-world benchmarks.

Usage

This crate provides FxHashMap and FxHashSet as collections. They are simply type aliases for their std::collection counterparts using the Fx hasher.

use rustc_hash::FxHashMap;

let mut map: FxHashMap<u32, u32> = FxHashMap::default();
map.insert(22, 44);

no_std

The std feature is on by default to enable collections. It can be turned off in Cargo.toml like so:

rustc-hash = { version = "2.0", default-features = false }

About

Custom hash algorithm used by rustc (plus hashmap/set aliases): fast, deterministic, not secure

Resources

License

Apache-2.0, MIT licenses found

Licenses found

Apache-2.0
LICENSE-APACHE
MIT
LICENSE-MIT

Code of conduct

Security policy

Stars

Watchers

Forks

Packages

No packages published

Languages