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
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...
Except that, is there another good solution for my problem?
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.
Your desire to look up entries in a map by prefixes of their keys suggests to me qp-trie, which specifically supports this: https://lib.rs/crates/qp-trie
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
I'll try those solutions