Can hashbrown Make Quant System HashMaps 5× Faster Than std?

Quant trading systems rely heavily on hash maps for symbol snapshots, order lookups, and market quotes. The standard library HashMap uses SipHash-1-3 for security, which is slower than hash functions optimized for speed.

Why replace the standard HashMap

The default SipHash protects against hash collision attacks, but in a quant system the keys (symbols, order IDs, price levels) are internally generated and trusted, so the security cost is unnecessary. hashbrown uses foldhash, a faster hash, resulting in benchmark differences on an Apple M4 Pro for 1 M u64 keys:

Insert 1 M: std 31.6 ms vs hashbrown 17.7 ms (1.8× faster)

Hit lookup 1 M: std 25.0 ms vs hashbrown 5.14 ms (4.9× faster)

Miss lookup 1 M: std 4.95 ms vs hashbrown 1.68 ms (2.9× faster)

Delete 100 k: std 765 µs vs hashbrown 415 µs (1.8× faster)

1. Usage

hashbrown’s API mirrors the standard library, so a simple import change is enough:

use hashbrown::HashMap;
let mut quotes = HashMap::new();
quotes.insert("BTCUSDT", 95_000.0);
quotes.insert("ETHUSDT", 3_200.0);
if let Some(px) = quotes.get("BTCUSDT") {
    println!("{px}");
}
// entry API works the same
*quotes.entry("BTCUSDT").or_insert(0.0) += 100.0;

Most projects replace std::collections::HashMap with hashbrown::HashMap and compile without further changes.

Hash function selection

hashbrown defaults to foldhash, suitable for trusted internal data. If a table’s keys come from external input, switch back to a DoS‑resistant hash (e.g., SipHash) for that table only:

use std::hash::RandomState; // standard SipHash
use hashbrown::HashMap;
let mut m: HashMap<String, u64, RandomState> = HashMap::default();

In practice, ahash is a common compromise, offering speed between foldhash and SipHash while retaining some collision resistance.

Raw table API: HashTable

hashbrown provides a low‑level HashTable<T> that does not require T: Hash + Eq. It is useful when the hash value is expensive to compute or when the value already contains the key:

use hashbrown::HashTable;
struct Order { id: u64, px: f64, qty: f64 }
let mut orders: HashTable<Order> = HashTable::new();
let hash = |id: u64| id.wrapping_mul(0x9E3779B97F4A7C15);
orders.insert_unique(hash(1001), Order { id: 1001, px: 95_000.0, qty: 0.5 }, |o| hash(o.id));
let found = orders.find(hash(1001), |o| o.id == 1001);

The standard library would need the nightly RawEntry API for comparable functionality.

2. Source: Why SwissTable is fast

hashbrown implements Google’s SwissTable algorithm. Its key ideas are:

Separate metadata (control bytes) from data and store a 1‑byte control per bucket.

The high 7 bits of the hash are placed in the control byte, enabling SIMD‑parallel pre‑filtering of 16 buckets at once.

Only when the control byte matches does the algorithm perform the full key comparison.

Control bytes

Each bucket has a control byte whose high bits indicate state (empty, tombstone, occupied) and whose low 7 bits store the high part of the hash:

pub struct Tag(pub u8);
impl Tag {
    const EMPTY: Tag = Tag(0b1111_1111); // empty bucket
    const DELETED: Tag = Tag(0b1000_0000); // tombstone
    fn full(hash: u64) -> Tag { /* store top 7 bits */ }
}

One SIMD instruction per 16 buckets

Loading a 16‑byte group of control bytes and comparing them with the target tag using _mm_cmpeq_epi8 yields a bitmask; _mm_movemask_epi8 compresses the result into a 16‑bit integer, allowing the algorithm to skip 16 buckets with a single instruction.

Triangular probing

On a collision the probe sequence jumps by increasing group widths (1, 2, 3 … groups) instead of linear stepping, reducing primary clustering while preserving cache‑friendly group scans.

Load factor 7/8

SwissTable tolerates up to 87.5 % occupancy. For 1 M elements the required bucket count is 1_000_000 * 8 / 7 ≈ 1_142_857, rounded up to the next power of two (2²¹ ≈ 2.1 M buckets). The control‑byte area adds only bucket_count + group_width bytes.

Single‑allocation memory layout

Control bytes and data share a single allocation; data grows toward lower addresses, control bytes toward higher addresses. This layout enables a single realloc on growth and cache‑friendly sequential scans.

Deletion and tombstones

Deletion marks a bucket as EMPTY if the containing group already has an empty slot; otherwise it becomes a DELETED tombstone to preserve probe chains. Excess tombstones trigger a rehash that can flip states in place without extra allocation.

3. A common misconception

hashbrown is not a separate faster hash map; since Rust 1.36 the standard library’s std::collections::HashMap is actually a thin wrapper around hashbrown. The performance gap observed earlier stems from the default hash function: SipHash vs. foldhash.

When the standard library is configured to use the same fast hash (e.g., ahash), its performance matches hashbrown’s, confirming that the underlying table implementation is identical.

4. Practical engineering tips

For internal, trusted keys, switch to a fast hash (foldhash or ahash) to gain several‑fold lookup speed.

If a table receives external keys, keep SipHash only for that table.

Pre‑allocate with with_capacity to avoid costly rehashes; inserting 1 M pre‑reserved entries drops from ~31 ms to ~9 ms.

When the value already contains the key, consider using HashTable to eliminate the redundant key storage.

hashbrown’s extra features—stable HashTable, entry_ref, custom allocators, and no_std support—are the real reasons to depend on it.