rust-lang / rust-lang/hashbrown

Use faster hash function and track collisions?

Open
#370 2 comments 1 reaction 0 assignees View on GitHub

Nobody has claimed this yet.

Dominant language
Rust
Stars
3k
Forks
358
Avg merge
11h 57m
Merged PRs (30d)
2

Description

In this Reddit comment, it is suggested that C#'s hashmap implementation outperforms Rust's on a particular benchmark because C#'s uses a fast-but-dos-vulnerable hash function by default, tracks the number of collisions, and switches to a dos-resistant hash function above a certain threshold of collisions. I am taking the comment author's word for it that this is C#'s behavior (from a brief skim of the source code, it seems like maybe this is where it's implemented?). Regardless, it sounds like a reasonable idea:

  • Roughly speaking, a hash table is DoS resistant if an attacker is not able to significantly alter its performance characteristics (such as making lookup and insertion behave as linear time operations); if an attacker is only able to make hash table operations, say, a few times slower, this is probably fine for most applications - even those that are exposed to untrusted inputs
  • The overhead of tracking the number of collisions is likely small compared to the performance gains of a non-dos-resistant hash function
  • This is just speculation, but intuition tells me that it ought to be possible to choose a collision threshold that is both fairly low (and thus doesn't allow an attacker to pessimize hashmap performance that significantly) and is still higher than the number of collisions that will be encountered during most non-malicious workloads

Has an approach like this ever been considered for hashbrown? Given that both hashbrown and the standard library make no stability guarantees about their default hash function, this ought to be a backwards-compatible change. Finally, users who are especially concerned with DoS resistance could still pick a specific hash function in order to retain today's DoS resistance behavior.

Contributor guide

No contributing guide indexed for this repository

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by reviewing the linked .NET Dictionary.cs implementation and hashbrown's current default-hashing behavior. Determine whether collision counting and switching hash functions can be specified safely, then define benchmarks and tests that establish acceptable performance and DoS resistance before implementation.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
performance, security
Issue type
Feature
Difficulty
5/5
Estimated time
Over a week
Activity status
Stale
Clarity
Needs clarification
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.