I am trying to create a hash map that must not exceed a max heap size given by the user. I have tried implementing a custom structure backed by a fixed vector, with a custom replacing schema. Even if there are no collisions, my implementation is obviously slower than the one in the std, since I'm not using quadratic probing or SIMD. Without having to reinvent the wheel, what would the idiomatic way to ensure a hashmap does not exceed x bytes, and have a custom replacement schema for allowing insertions if the map is full?
You could just wrap HashMap and take care not to increase capacity. You could also drop down to hashbrown::raw::RawTable if you want to be even more sure about never resizing.
You'll still be subject to the load factor though, where the capacity is limited to 7/8 the raw heap capacity. If that matters to you, maybe wrapping IndexMap will be better -- that uses a RawTable<usize> so the load factor waste is only in usizes, and then the keys and values are in a Vec.
How would I know that a new insert won't increase capacity, if I choose to go down the std HashMap route?
It should never resize if len() < capacity() before the insert.
There are also cases where the reported capacity may be less than the originally allocated capacity, when tombstone markers are left at removals, but I don't remember off-hand the exact semantics whether those may get reclaimed. Those are internal details anyway.
1 Like
You check the length before every insertion and refuse it if it's already at the permissible maximum.
This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.