I am not having much luck with finding a clean way to search for an unused key in a HashMap.
To clarify with an example, if I have a HashMap<u8, _>, then there are 256 possible keys from 0 through to 255. I would like to write a function that outputs Some(u8) if there is an available key and None otherwise, i.e.:
fn find_unused_key(map: &HashMap<u8, _>) -> Option<u8>
How would one do this?
Depending on why you're doing this, you might consider using BTreeMap instead. A BTreeMap is sorted by key, so you can simply iterate over it in order and look for gaps in the sequence, which is O(n log n).
If you can simply write a function to map from "key" to a small integer, you can do better by storing them all in a Vec<(K, V)> which brings it down further to O(n).
In this particular case, performance was not as important as clarity, so I went with the following solution:
let my_map = HashMap::new();
/* ... some code that adds items to the map ... */
let unused_key = (0..u8::MAX)
.into_iter()
.find(|key| !my_map.contains_key(key));
If the key is a u8, it may make sense to just use Vec<Option<T>> or even [Option<T>;256] to store the values and not use a HashMap at all. You would then just do lookups using the key as the index. This solution doesn’t scale well with larger integer types and also may be less space efficient if your values are large and you’re map is most empty. But it would perform better in general and looking up empty values becomes a trivial loop over the vec checking for None
In case you're asking about the syntax, the correct way to "ignore" a type is:
fn find_unused_key<V>(map: &HashMap<u8, V>) -> Option<u8>
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.