Exotic use of hashbrown::HashMap; remove entry by cached hash

Are key hashes in HashMap's stable over the lifetime of the HashMap? If I calculate the hash of a key and store it in its value, will that hash be valid for as long as the the key exists in the HashMap?

I'm doing some more porting of C++ code to Rust, and there's a container which is a combination of a map and an lru (implemented as a linked list), where the container keeps track of a timestamp for each map entry, and it has the ability to perform certain operations based on the relative age of the entries.

To mimic this I've created a custom Map which has an inner HashMap<K, *mut LruNode<V>>, where the LruNode is a linked list node which stores the value and timestamp of the entry, and the linked list is kept sorted. This works fine, but there's an annoying case that causes some issues. The Map needs to support a pop(), which takes out the oldest node (i.e. the tail LruNode).

I made a proof-of-concept implementation of pop() which uses drain_filter() on the inner HashMap, which drains all entries with its value equal to the lru_tail (which will always be 1, as long as the container isn't empty). This works, but it needs to scan though all nodes each time.

To improve on this I want to store, at least in principle, the key in the LruNode. I don't want to introduce any Clone trait bounds, so I can't actually store the key in two places.

In the back of my mind, I have been wondering if it is possible to store the key hash in the LruNode, and if there are methods to work with that hash value, so that I don't actually need the key. In another thread the raw_entry() method came up, and it indeed looks like there are some methods for working with key hashes.

However, this presumes that a hash of a key is stable over the HashMap's lifetime. I have other issues I've run into, but they don't matter if the key hash is not invariant.

Yes, AFAIK the hashes should absolutely be stable (of course provided the BuildHasher is well-behaved as well as the Hash implementation of K, but the map would be broken otherwise anyways). HashMap itself is only a wrapper around a RawTable with a S: BuildHasher, it keeps using that same BuildHasher (which you can get a reference to via the HashMap::hasher method).

In particular since essentially all methods are generic over S or S: BuildHasher there isn't really anything the implementation could do to change the hasher's behavior, even if it wanted to.

3 Likes