foldhash

Foldhash is a fast, non-cryptographic, and minimally DoS-resistant hashing algorithm implemented in Rust. It is specifically designed for computational tasks such as:

• Hash maps
• Bloom filters
• Count sketching

Foldhash provides two distinct variants:

1. Speed-optimized: Ideal for data structures like hash maps and bloom filters.
2. Quality-optimized: Ideal for statistical algorithms like HyperLogLog and MinHash.

Hashers with random state can increase the memory size of your HashMap. When choosing a hasher, consider the std::mem::size_of impact on your collection:

• foldhash::HashMap<u32, u32> (both variants): 40 bytes
• std::collections::HashMap<u32, u32> (default): 48 bytes
• ahash::HashMap<u32, u32>: 64 bytes
• fxhash::FxHashMap<u32, u32>: 32 bytes

// Example of memory footprint comparison
std::mem::size_of::<foldhash::HashMap<u32, u32>>() // 40
std::mem::size_of::<ahash::HashMap<u32, u32>>()   // 64
std::mem::size_of::<fxhash::FxHashMap<u32, u32>>() // 32
std::mem::size_of::<std::collections::HashMap<u32, u32>>() // 48

The foldhash crate provides two variants optimized for different needs:

1. foldhash::fast (also known as foldhash-f): Designed as the default choice for hash tables. It strikes a balance between performance and quality, though it has measurable biases.
2. foldhash::quality (also known as foldhash-q): Provides higher quality hashing but incurs a small, non-negligible computational overhead compared to the fast variant.

Benchmarks suggest that for general hash table performance, the extra quality provided by foldhash::quality is rarely worth the performance cost over foldhash::fast.

Foldhash provides two variants depending on your requirements for speed versus statistical quality:

• foldhash-f (Fast): Optimized for performance. It is a strong hash in terms of collisions on its full 64-bit output and is suitable for hash table performance. However, it may fail certain statistical tests (like SMHasher3) regarding bit-level avalanche properties.
• foldhash-q (Quality): A post-processed version of foldhash-f designed to ensure all bits properly avalanche. It passes the SMHasher3 test suite without failures. Use this variant for algorithms that require unbiased, random-like bit distributions, such as HyperLogLog or MinHash.

Foldhash is not suitable for the following use cases:

• Security/Cryptography: Foldhash is not appropriate for any cryptographic purpose. Do not use it for security-sensitive operations.
• Cross-platform/Version consistency: Do not use Foldhash if you require consistent output across different versions of the library or different platforms (e.g., for persistent file formats or communication protocols).
• High-security DoS resistance: If you are concerned about attackers reverse-engineering the internal random state of a long-running program to create colliding inputs for computational complexity attacks, Foldhash may not be sufficient. See the "HashDoS resistance" section for details.

The core of foldhash is the folded multiply technique. It compresses two 64-bit words into a single 64-bit word by performing a 64x64 bit -> 128 bit multiplication and then XORing the high and low 64-bit halves of the result together. This ensures that the output bits are affected by a wide range of input bits.

Example implementation of the folded multiply logic:

let full = (x as u128) * (y as u128);
let lo = full as u64;
let hi = (full >> 64) as u64;
let folded = lo ^ hi;

Foldhash is described as "minimally DoS-resistant" because it uses secret values in its folded multiply operations (folded_multiply(input1 ^ secret1, input2 ^ secret2)) to prevent trivial collision attacks and ensure different seeds result in different access patterns.

CRITICAL SECURITY NOTE: Foldhash does not provide resistance against interactive attackers. The secret values used in the hashing process can potentially be derived through direct observation of hash outputs or indirect methods like timing attacks or hash table iteration. Once the secrets are known, an attacker can easily generate infinite collisions.

Foldhash can be used in no_std environments by disabling its default "std" feature in your Cargo.toml.

# Example Cargo.toml configuration
foldhash = { version = "0.2.0", default-features = false }

Foldhash provides two distinct variants optimized for different use cases:

1. fast module: Optimized for maximum speed. Ideal for data structures like HashMap and Bloom filters. It has known statistical imperfections.
2. quality module: Optimized for statistical quality. Ideal for algorithms that rely on hash properties for correctness, such as HyperLogLog and [MinHash].

Foldhash uses an 8-byte per-hasher seed and a larger SharedSeed. To manage overhead, it provides three types of BuildHashers (available for both fast and quality modules):

• RandomState: Generates a random per-hasher seed and implicitly uses SharedSeed::global_random.
• FixedState: Uses a fixed per-hasher seed and implicitly uses SharedSeed::global_fixed.
• SeedableRandomState: Works like RandomState but allows explicit seeding. It requires an explicit reference to a SharedSeed and is 16 bytes in size.

The easiest way to use foldhash with Rust's std::collections::HashMap or HashSet is to use the convenience types provided by the crate. This automatically handles the random state generation for you.

Note: This requires the std feature to be enabled (which is the default).

use foldhash::{HashMap, HashMapExt};

let mut hm = HashMap::new();
hm.insert(42, "hello");

Foldhash supports the following features:

• std (default): Provides convenient aliases for std containers. Disable this for #![no_std] environments.
• nightly: Enables slightly better string hashing performance using the unstable hasher_prefixfree_extras feature.