Fast way to insert or update for HashMap

help
1

I want to search in HashMap<String, Foo> by key, and if key not exists
insert new entry.

I see two ways, the first:

let key: &str = ...;
if map.get(key).is_none() {
   map.insert(key.to_string(), ...);
}

but in this case there are two lookups one for get and one for insert.

So the second:

map.entry(key.to_string()).or_insert_with(...);

Only one lookup in hash table, but I allocate string every search.

So any way to use one lookup and allocate memory only if there are no such key?

2

There's currently no way to do this directly; using only the standard library on stable Rust, your first way is the only way. In nightly Rust, you can use the HashMap::raw_entry_mut() API (Rust Playground):

let key: &str = ...;
map.raw_entry_mut()
    .from_key(key)
    .or_insert_with(|| (key.to_string(), ...));

Or if you want to stick to stable Rust, you can replace the std::collections::HashMap with a hashbrown::HashMap. (The standard library already uses a hashbrown::HashMap under the hood, so it should be pretty solid as a dependency.) With that, you can use the hashbrown::HashMap::entry_ref() API (Rust Playground):

let key: &str = ...;
map.entry_ref(key).or_insert_with(...);
3

If you can use nightly features, try_insert will do what you want with only one lookup, although it will still do a possibly unnecessary allocation

4

... or you also could instead use an HashMap<&str, Foo> and pass your keys via a string interner (a glorified HashSet<String>) so your code becomes:

let key = interner.get_or_intern(...);
map.entry(key).or_insert_with(...);

Basically you traded an allocation for an O(log n) lookup. That's usually a win but you should benchmark with real-life cases.

As a bonus, you'll learn (if you didn't know it already) that nearly all performance tuning is a just a different position on the universal balance between memory footprint (caching) and code complexity (compression).