Retrieve entries from a (prehashed) hashmap with the leading bytes of the hash

#1

Hi,

I have a use case where I have a map that use his builder, and the keys are prehashed. I want to share only a part of that hash, ideally the leading bytes of that hash. The idea is simply to reduce my bandwidth, so if I can retrieve a key-value in my hashmap from a "truncated" hash, I would be happy :smile:

My high level solution to retrieve the key-value is to store in another structure the full hashes corresponding to the truncated. I don't really care about conflicts, if I get multiple possible hash I simply process each entry. Classic.

I wondered why I can't find all entries with hashes that start with the given leading bytes. Another find_like function in hashbrown could easily do the job, right? And implementing my high level solution would be a waste of memory. Is that a very stupid idea? I can't figure out what I really think about it... :thinking:

Except that, is there another good solution for my problem?

Thanks all!

#2

Technically it should be possible to iterate over a range of buckets, but use of keys with specific and meaningful hashes is a pretty creative and unusual use of a hash map. You will probably need to fork and modify hashbrown to expose this.

Alternatively, use BTreeMap that can iterate over a range of keys. Or use HashMap<prefix, HashMap<suffix, val>> as your data structure.

2 Likes
#3

Thanks, :slight_smile: I'll try those solutions

#4

Your desire to look up entries in a map by prefixes of their keys suggests to me qp-trie, which specifically supports this:

QP-tries, like all radix tries, are extremely efficient when dealing with anything related to prefixes. This extends to iteration over [entries with keys that have common] prefixes