# HashMap.insert without overwriting?

**URL:** <https://users.rust-lang.org/t/hashmap-insert-without-overwriting/107064>\
**Category:** uncategorized\
**Created:** [February 19, 2024, 6:16pm UTC](https://users.rust-lang.org/t/hashmap-insert-without-overwriting/107064 "2024-02-19T18:16:53Z")\
**Posts on this page:** 16\
**Page:** 1

<div class="post-metadata">

**Author:** ![T4r4sB](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/t4r4sb/32/30131_2.png) [@T4r4sB](https://users.rust-lang.org/u/T4r4sB)\
**Post date:** [February 19, 2024, 6:16pm UTC](https://users.rust-lang.org/t/hashmap-insert-without-overwriting/107064/1 "2024-02-19T18:16:53Z")

</div>

Acording to my experience in C++, I often need the behaviour, when Im trying to insert, and if element exists, old value remains, and I can check it using a flag:

```rust
if (table.insert({key, value}).second) {
   ... some C++ code
}

```

Is Rust I wrote this:

```rust
if table.insert(key, value).is_none {
   ... Rust code
}

```

but this code makes anothier thing: it change value if it is exists.

Alternative way1:

```rust
if !table.contains_key(key) {
  table.insert(key, value);
   ... Rust code
}

```

But it is bad because here there are 2 table lookups

Alternative way2:

```rust
if match table.entry(key, value) {
                    std::collections::hash_map::Entry::Vacant(v) => {
                        v.insert(value);
                        true
                    }
                    std::collections::hash_map::Entry::Occupied(_) => false,
                } {
 ... Rust code
}

```

But it is a madness. Too many lines to emulate the single line C++ behaviour.

What is the best way to insert without overwrite?

---

<div class="post-metadata">

**Author:** ![jumpnbrownweasel](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/jumpnbrownweasel/32/17403_2.png) [@jumpnbrownweasel](https://users.rust-lang.org/u/jumpnbrownweasel)\
**Post date:** [February 19, 2024, 6:25pm UTC](https://users.rust-lang.org/t/hashmap-insert-without-overwriting/107064/2 "2024-02-19T18:25:30Z")

</div>

> [@T4r4sB](#):
>
> But it is a madness. Too many lines to emulate the single line C++ behaviour.

If you don't need the true/false result, you can use

```rs
table.entry(key, value).or_insert(value);

```

---

<div class="post-metadata">

**Author:** ![dheijl](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/dheijl/32/37229_2.png) [@dheijl](https://users.rust-lang.org/u/dheijl)\
**Post date:** [February 19, 2024, 6:27pm UTC](https://users.rust-lang.org/t/hashmap-insert-without-overwriting/107064/3 "2024-02-19T18:27:05Z")

</div>

You're not specifying what "table" is, but should it be a hashmap, would try\_insert() suit you?

---

<div class="post-metadata">

**Author:** ![jumpnbrownweasel](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/jumpnbrownweasel/32/17403_2.png) [@jumpnbrownweasel](https://users.rust-lang.org/u/jumpnbrownweasel)\
**Post date:** [February 19, 2024, 6:31pm UTC](https://users.rust-lang.org/t/hashmap-insert-without-overwriting/107064/4 "2024-02-19T18:31:42Z")

</div>

Good point. If nightly Rust can be used, that's the best option.

They're using a HashMap (in the title).

---

<div class="post-metadata">

**Author:** ![cuviper](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/cuviper/32/3156_2.png) [@cuviper](https://users.rust-lang.org/u/cuviper)\
**Post date:** [February 19, 2024, 6:34pm UTC](https://users.rust-lang.org/t/hashmap-insert-without-overwriting/107064/5 "2024-02-19T18:34:34Z")

</div>

> [@T4r4sB](#):
>
> Alternative way2:
> 
> ```rust
> if match table.entry(key, value) {
> std::collections::hash_map::Entry::Vacant(v) => {
> v.insert(value);
> true
> }
> std::collections::hash_map::Entry::Occupied(_) => false,
> } {
> ... Rust code
> }
> 
> ```

If you don't want to do anything in the occupied case, you can just write it like this:

```rust
if let Entry::Vacant(v) = table.entry(key) {
    v.insert(value);
    // ... followup code
}

```

---

<div class="post-metadata">

**Author:** ![jendrikw](https://avatars.discourse-cdn.com/v4/letter/j/e274bd/32.png) [@jendrikw](https://users.rust-lang.org/u/jendrikw)\
**Post date:** [February 19, 2024, 6:47pm UTC](https://users.rust-lang.org/t/hashmap-insert-without-overwriting/107064/6 "2024-02-19T18:47:38Z")

</div>

I'd simply write a small helper function, like this:

```rust
pub fn insert_new<K, V>(map: &mut HashMap<K, V>, key: K, value: V) -> bool
where
    K: Eq + Hash,
{
    match map.entry(key) {
        Occupied(_) => false,
        Vacant(entry) => {
            entry.insert(value);
            true
        }
    }
}

```

---

<div class="post-metadata">

**Author:** ![culebron](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/culebron/32/23502_2.png) [@culebron](https://users.rust-lang.org/u/culebron)\
**Post date:** [February 19, 2024, 7:27pm UTC](https://users.rust-lang.org/t/hashmap-insert-without-overwriting/107064/7 "2024-02-19T19:27:37Z")

</div>

You can just make a `HashMap` of `Vec` if you want to see all older versions, or make a custom type with just 2 fields:

```rust
struct MyEntry<T> {
    pub value: T,
    pub second: Option<T>
}

impl<T> MyEntry<T> {
    pub fn update(&mut self, other: T) {
        self.second = Some(self.value);
        self.value = other;
    }
}

fn main() {
    let x: HashMap<i64, MyEntry> = HashMap::new();
    ...
    let data_entry = x.entry(key).and_modify(|v| v.update(new_value)).or_insert_with(|| MyEntry { value: new_value, second: None });
    println!("{:?}", data_entry.second);
}

```

Or use a `Vec` if you want to keep all old versions. Current value will be `.last()` here:

```rust

fn main() {
    let x: HashMap<i64, Vec<MyDataValue>> = HashMap::new();
    ...
    let data_entry = x.entry(key).and_modify(|v| v.push(new_value)).or_insert_with(|| vec![new_value]);
    println!("{:?}", data_entry.last().unwrap());
}

```

---

<div class="post-metadata">

**Author:** ![steffahn](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/steffahn/32/47569_2.png) [@steffahn](https://users.rust-lang.org/u/steffahn)\
**Post date:** [February 19, 2024, 11:01pm UTC](https://users.rust-lang.org/t/hashmap-insert-without-overwriting/107064/8 "2024-02-19T23:01:39Z")

</div>

> [@T4r4sB](#):
>
> But it is bad because here there are 2 table lookups

And might also still do multiple lookups. (I’d have to double check whether or not entry-API contains any optimization to reduce the number of lookups; if I recall correctly its main purpose was to help with some borrow-checking issues that otherwise occur, and that it’s sometimes a convenient API).

_(2 mins later)_ okay, checked it, occupied entries have some direct access to the contained element, vacant entries [are just](https://docs.rs/hashbrown/0.14.3/src/hashbrown/map.rs.html#4313-4317)

```rust
pub struct VacantEntry<'a, K, V, S = DefaultHashBuilder, A: Allocator = Global> {
    hash: u64,
    key: K,
    table: &'a mut HashMap<K, V, S, A>,
}

```

so all it saves you is re-calculating the hash. Which, well…, is like “half” of the lookup, I suppose.

---

<div class="post-metadata">

**Author:** ![CAD97](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/cad97/32/5076_2.png) [@CAD97](https://users.rust-lang.org/u/CAD97)\
**Post date:** [February 19, 2024, 11:55pm UTC](https://users.rust-lang.org/t/hashmap-insert-without-overwriting/107064/9 "2024-02-19T23:55:39Z")

</div>

> [@steffahn](#):
>
> whether or not entry-API contains any optimization to reduce the number of lookups

The entry API was in fact created in part to remove the _requirement_ of repeated lookup for `or_insert`, and IIRC the original hashmap implementation did use this to skip a repeated lookup. However, because the insertion algorithm for the current hashmap involves potential reordering of other entries, the full walk must be performed from the starting lookup position. (This process exchanges a small amount of additional work on insertion to keep entries closer to their ideal position and reduce the work done by get overall.)

Somewhat importantly, this results in that were the entry API to do a full "for insert" lookup immediately, it could require dropping the vacant entry handle without doing an insert to fix up invariants (logically, to `remove` the entry again). Rather than make no-insert entry lookup pay for insert+delete (~2 units), it was chosen to make or-insert pay for get+insert (~1½ units). Oh, and relying on `Drop` like that is a bad idea (it requires "PPYP" leak amplification in the face of leaks/forget for soundness), and adding such now would be API breaking (change drop timing / impede NLL).

And for historical note, the lifetime limitations that helped birth the entry API are _mostly_ not an issue anymore due to NLL. While temporaries are still live across the problematic region (thus the similar footgun with holding scrutinee locks), NLL allows their loan to expire before it actually drops.

---

<div class="post-metadata">

**Author:** ![SkiFire13](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/skifire13/32/17959_2.png) [@SkiFire13](https://users.rust-lang.org/u/SkiFire13)\
**Post date:** [February 19, 2024, 11:58pm UTC](https://users.rust-lang.org/t/hashmap-insert-without-overwriting/107064/10 "2024-02-19T23:58:15Z")

</div>

It should be noted that `HashMap` using open addressing makes it harder to reduce the number of lookups, since searching for the entry corresponding to a given key is a bit different than searching for an empty bucket for its key (while searching for the entry you want to skip tombstones, but while searching for an empty bucket you want to consider them, and you also need to account for potentially having to resize the map).

Edit: and to be clear, the `Entry` API does have a small optimization in that when inserting on a vacant entry it doesn't check it the entry is already in the map, so it only needs to do a single scan for a tombstone/empty bucket. In comparison a normal insert even though it does a single scan, it needs to look for both an insert slot and an occupied entry for the given key.

---

<div class="post-metadata">

**Author:** ![steffahn](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/steffahn/32/47569_2.png) [@steffahn](https://users.rust-lang.org/u/steffahn)\
**Post date:** [February 19, 2024, 11:58pm UTC](https://users.rust-lang.org/t/hashmap-insert-without-overwriting/107064/11 "2024-02-19T23:58:41Z")

</div>

Thanks for the context!

---

<div class="post-metadata">

**Author:** ![T4r4sB](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/t4r4sb/32/30131_2.png) [@T4r4sB](https://users.rust-lang.org/u/T4r4sB)\
**Post date:** [February 20, 2024, 5:19pm UTC](https://users.rust-lang.org/t/hashmap-insert-without-overwriting/107064/12 "2024-02-20T17:19:10Z")

</div>

Oh, its very sad.  
Why can Vacant entry hold a pointer to a place for new element?  
I know about map-rebuilding, but entry can hold a special flag for this case

---

<div class="post-metadata">

**Author:** ![CAD97](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/cad97/32/5076_2.png) [@CAD97](https://users.rust-lang.org/u/CAD97)\
**Post date:** [February 20, 2024, 5:34pm UTC](https://users.rust-lang.org/t/hashmap-insert-without-overwriting/107064/13 "2024-02-20T17:34:47Z")

</div>

Because as mentioned, the swiss table implementation uses open addressing, meaning that lookup for get and lookup for insert are different operations. There isn't any extra work being done; the only (and entirely negligible) difference is that the get-search and insert-search are done in two separate passes, instead of _potentially_ being fused into one pass. In fact, I believe hashbrown still does a "double lookup" for normal `insert` because the `get` lookup is SIMD accelerated in ways the `insert` lookup can't. If you even sometimes try to `insert` with a preexisting key, the "double lookup" has better amortized performance characteristics. (Which, if you're using a hashmap, is your primary metric of concern.)

---

<div class="post-metadata">

**Author:** ![T4r4sB](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/t4r4sb/32/30131_2.png) [@T4r4sB](https://users.rust-lang.org/u/T4r4sB)\
**Post date:** [February 20, 2024, 8:47pm UTC](https://users.rust-lang.org/t/hashmap-insert-without-overwriting/107064/14 "2024-02-20T20:47:43Z")

</div>

For `get` we are scanning cells is some specific order (with linear probing of square probing or some other way), skipping tombstones, and stop when we meet first "empty" or "valid and equals" cell.  
For `insert` we are scannin cells in the same order, and stop when we meet first "tombstone" cell.

Yes, these operations are different. But why cant we save first tombstone pointer while making `get` scan? Is scan restarting faster than saving one extra field?

---

<div class="post-metadata">

**Author:** ![CAD97](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/cad97/32/5076_2.png) [@CAD97](https://users.rust-lang.org/u/CAD97)\
**Post date:** [February 21, 2024, 12:21am UTC](https://users.rust-lang.org/t/hashmap-insert-without-overwriting/107064/15 "2024-02-21T00:21:36Z")

</div>

I went and looked at the implementation. The reason appears ultimately to be such that finding an occupied `entry` does not cause table growth when at the load factor.

`entry` is roughly

```rust
if let Some(bucket) = map.table.find(hash, eq) {
    Entry::Occupied(..)
} else {
    map.reserve(1);
    Entry::Vacant(..)
}

```

The `reserve` call (and thus potential grow) must happen as a part of `entry`, as `VacantEntry::insert` does not have access to the `impl BuildHasher`. The implementation choice might make more sense with hashbrown's entry API which does fully defer the grow until `VacantEntry::insert`; note that attempting to find an insert slot when there isn't capacity will cause an infinite loop!

Compare [`find`](https://github.com/rust-lang/hashbrown/blob/274c7bbd79398881e0225c0133e423ce60d7a8f1/src/raw/mod.rs#L2166), [`find_insert_slot`](https://github.com/rust-lang/hashbrown/blob/274c7bbd79398881e0225c0133e423ce60d7a8f1/src/raw/mod.rs#L2109),  
[`find_or_find_insert_slot`](https://github.com/rust-lang/hashbrown/blob/274c7bbd79398881e0225c0133e423ce60d7a8f1/src/raw/mod.rs#L1952). Also relevant: [`fix_insert_slot`](https://github.com/rust-lang/hashbrown/blob/274c7bbd79398881e0225c0133e423ce60d7a8f1/src/raw/mod.rs#L1867), which is potentially yet another table scan and a portion of the additional lookup cost to `insert` I've alluded to.

It _could_ make sense for the `rustc_entry` path to do `find_or_find_insert_slot` eagerly, but there's also merit to keeping the two entry paths roughly parallel. A full context would probably only been known by Amanieu. (Really, though, the cost difference of splitting `insert`'s double lookup into two passes isn't significant, and if it is, the problematic part is your hash, not the lookup.)

I recall the potential for table modification to reposition buckets to keep the average distance from ideal lower overall, but didn't see any evidence of this while scanning the implementation just now; hashbrown may have stopped doing this or I might've crossed some wires.

---

<div class="post-metadata">

**Author:** ![system](https://sea1.discourse-cdn.com/flex019/user_avatar/users.rust-lang.org/system/32/51372_2.png) [@system](https://users.rust-lang.org/u/system)\
**Post date:** [May 21, 2024, 12:22am UTC](https://users.rust-lang.org/t/hashmap-insert-without-overwriting/107064/16 "2024-05-21T00:22:06Z")

</div>

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.