CODEWITHSUNDEEP
rust
Tim Diekmann
Tim Diekmann

Reputation: 8466

Can I use the hashes in a HashMap directly?

Is it possible to insert and get values into/from a HashMap directly with a Hash provided, so I can cache the hashes?

I want to do something like this:

map.insert(key, "value");

let hashed_key = {
    let mut hasher = map.hasher().build_hasher();
    key.hash(&mut hasher);
    hasher.finish()
};

assert_eq!(map.get(key).unwrap(), map.get_by_hash(hashed_key).unwrap());

playground

Upvotes: 5

Views: 1711

Answers (1)

Matthieu M.
Matthieu M.

Reputation: 299750

No.

This is fundamentally impossible at the algorithmic level.

By design, a hash operation is surjective: multiple elements may hash to the same value. Therefore, any HashMap implementation can only use the hash as a hint and must then use a full equality comparison to check that the element found by the hint is the right element (or not).

At best, a get_by_hash method would return an Iterator of all possible elements matching the current hash.

For a degenerate case, consider a hashing algorithm which always returns 4 (obtained by the roll of a fair dice). Which element would you expect it to return?

Work-around

If caching is what you are after, the trick in languages with no HashBuilder is to pre-hash (and cache) the hash inside the key itself.

It requires caching the full key (because of the equality check), but hashing is then a very simple operation (return the cached value).

It does not, however, speed up the equality check, which depending on the value may be quite expensive.

You could adapt the pattern to Rust, although you would lose the advantage of using a HashBuilder.

Upvotes: 12

Related Questions