Rust HashMap Performance: Why the Default Hasher Can Be 2× Slower

A small Rust optimization that can make a surprisingly large difference.

This project explores Two Sum implemented with Rust's HashMap, comparing the default hasher against a custom integer hasher.

The algorithm stays the same. The complexity stays the same. The difference is the hasher.

The Problem

Two Sum is typically solved in O(n) using a hash map:

For each number:
    target = complement
    if target exists in the map:
        return the two indices
    insert the current number

In Rust, the straightforward implementation uses HashMap with its default hasher.

That solution is perfectly valid — but for integer keys, the hashing itself can become a significant part of the runtime.

Why Is Rust's HashMap Slower?

Rust's standard HashMap uses SipHash 1-3 by default.

This is intentional.

SipHash provides strong protection against HashDoS (Hash Denial of Service) attacks. The hasher is randomly seeded, making it much harder for an attacker to deliberately construct keys that cause pathological hash-table behavior.

That's an important property for things such as web servers processing untrusted input.

But a competitive programming problem such as Two Sum has a very different threat model.

Your integer keys are not coming from an attacker trying to break your hash table.

For a small integer key, the cost of performing a relatively expensive hash function can become noticeable compared with the actual hash-table lookup.

So the question becomes:

What if we use a much cheaper hasher specifically for integer keys?

Custom Integer Hasher

This project implements a minimal integer hasher using only the Rust standard library.

No external crate is required.

This is particularly useful in environments such as LeetCode where adding arbitrary dependencies isn't always possible.

The basic idea is simple:

use std::hash::{BuildHasherDefault, Hasher};

#[derive(Default)]
struct IntHasher(u64);

impl Hasher for IntHasher {
    fn finish(&self) -> u64 {
        self.0
    }

    fn write_u64(&mut self, i: u64) {
        self.0 = i;
    }
}

type IntHashMap<K, V> =
    std::collections::HashMap<K, V, BuildHasherDefault<IntHasher>>;

For integer keys, this avoids the heavier SipHash computation and allows the integer itself to effectively become the hash value.

Benchmark

The benchmark compares the default HashMap hasher with the custom integer hasher.

Environment:

• Rust
• opt-level = 2
• Worst-case input
• Best result from multiple runs

Input size	SipHash	IntHasher	Speedup
10,000	550 µs	266 µs	2.07×
100,000	6,009 µs	3,080 µs	1.95×
1,000,000	118 ms	76 ms	1.55×
10,000,000	2.08 s	1.99 s	1.05×

The important observation is that this is a constant-factor optimization, not an algorithmic improvement.

Both implementations remain:

Time:  O(n)
Space: O(n)

The custom hasher simply reduces the constant cost of each hash operation.

As the dataset becomes extremely large, other costs — particularly memory access and cache behavior — become more significant, so the relative advantage decreases.

Why Does the Advantage Disappear?

At around 10 million elements, the difference becomes very small.

That's expected.

The optimization isn't changing the underlying algorithm. We're not turning O(n) into O(log n) or O(1).

We're simply making one operation inside the O(n) loop cheaper.

At smaller and medium input sizes, hashing can represent a meaningful portion of the total runtime.

At much larger sizes, memory traffic and hash-table behavior start dominating.

So:

Better hashing ≠ better asymptotic complexity

Better hashing = lower constant factor

Security Trade-off

This optimization should not be blindly applied everywhere.

The default hasher exists for a reason.

A custom trivial hasher can make a hash table more predictable and faster, but it may also make it easier for an attacker who can control keys to construct collisions.

That's exactly the type of situation SipHash is designed to mitigate.

Good use cases

• Competitive programming
• LeetCode
• Benchmarks
• Trusted integer data
• Performance-sensitive internal code where the input is controlled

Be careful with

• Web servers
• Public APIs
• User-controlled keys
• Hash tables exposed to adversarial input

The correct hasher depends on the threat model.

What This Project Demonstrates

This isn't really about Two Sum.

Two Sum is just a convenient benchmark.

The bigger lesson is:

Big-O complexity doesn't tell the whole performance story.

Two implementations can have:

Same algorithm
Same complexity
Same data structure
Same number of operations

and still have dramatically different runtimes because of the cost hidden inside those operations.

In this case, that hidden cost is hashing.

Project Structure

.
├── src/
│   └── main.rs
├── Cargo.toml
└── README.md

Running the Project

Clone the repository:

git clone [<repository-url>](https://github.com/ITASE-Dev/RustHashMap.git)
cd RustHashMap

Run:

cargo run --release

For benchmarking, make sure you're using an optimized build:

cargo bench

or:

cargo run --release

depending on how the benchmark is implemented.

Important Note

The custom hasher shown here is intentionally minimal.

It is designed for the specific case of integer keys with trusted input.

It should not be considered a general-purpose replacement for Rust's default hashing strategy.

The performance numbers are also hardware- and workload-dependent. Treat them as a demonstration of the effect rather than universal guarantees.

Sources

• The Rust Performance Book — Hashing
• rustc-hash
• LeetCode Language Environments
• Rust Internals — Help wanted: fast hash maps in std

---