Caching a hash value

help
#1

Consider the following situation:

  1. We have a hash map from a generic key type K, to some value type V that we control.
  2. The value type V is some type of reference counted pointer.
  3. All keys map to different pointers, that is, given two different keys k1, k2, the values map[k1] and map[k2] are also different.

Given the above, is it possible to store a clone of the reference counted value and some extra information such that you can find the value in the hash map and remove it? Obviously, you can do this by just storing a clone of the key, but this requires that K is clone. If we could somehow store a copy of the hash of K instead, then we should still be able to look up in the map - equality comparison can be done on the pointers of the reference counted values to resolve hash collisions.

Note that a HashMap is internally implemented as a HashSet of tuples where only the first half of the tuple is used for equality or hashing. I was imagining that we could write a wrapper struct with a custom Eq/Hash impl such that this could be done with the HashSet type.

#2

Looking through the raw APIs of hashbrown, well… if you used a RawTable directly, then there’s a fully general method for removal that supports this kind of use-case. HashMap<K, V> itself has a raw entry API, but that features only access to the key, not the value, while building the entry.

Following the HashSet-of-tuples approach… HashSet doesn’t have raw APIs, but HashMap has, as noted above, so a HashMap<Key<K, V>, ()> could work, where Key<K, V> is a custom type with a Eq + Hash implementation that delegates to the first component. And perhaps a Key<K, V>: Borrow<K> implementation helps, too. Then the raw entry API should allow for your operation. Maybe add a convenience wrapper around the thing to give it a more map-like API to the degrees that you need it.

For demonstration purposes, I’ve implemented a few methods of such a wrapper type (untested) here: Rust Playground

6 Likes