rust-lang / rust-lang/hashbrown

What happens when calling `HashTable::insert_unique` multiple times with the same value?

Open
#744 4 comments 0 reactions 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

The HashMap::insert_unique_unchecked() and HashSet::insert_unique_unchecked() methods are marked as unsafe, because calling them multiple times to insert the same value causes unspecified behavior (without violating memory safety).

However, the HashTable::insert_unique() method is safe. What kind of guarantees does it make about calling it multiple times with the same value?

pub fn insert_unique(
    &mut self,
    hash: u64,
    value: T,
    hasher: impl Fn(&T) -> u64,
) -> OccupiedEntry<'_, T, A>

Given that the hash is u64, hash collisions can obviously not be excluded (even if using a cryptographic hash function). And given that nothing in the signature imposes constraints such as T: Eq, the hash table has no way to know if two values that evaluate to the same hash are the same or not. So I assume it's safe to insert twice the same value, and that one of them will be returned upon lookup?

Note: find does know about the equality constraint, so maybe the question is rather: what happens if find gets multiple equality matches for the given hash value?

pub fn find(&self, hash: u64, eq: impl FnMut(&T) -> bool) -> Option<&T>

(Likewise .entry(...).remove() knows about equality, but my use case is insert-only so I don't care about removals misbehaving).

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 with the documented HashTable::insert_unique, HashTable::find, and related HashMap and HashSet insert_unique_unchecked methods. Determine the guarantees when duplicate values or equal matches share a hash, then document the behavior and safety expectations clearly for callers.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
backend
Issue type
Documentation
Difficulty
3/5
Estimated time
1-2 days
Activity status
Quiet
Clarity
Needs clarification
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.