What happens when calling `HashTable::insert_unique` multiple times with the same value?

[gendx]

The HashMap::insert_unique_unchecked() and HashSet::insert_unique_unchecked() methods are marked as unsafe, because calling them multiple times to insert the same value causes unspecified behavior (without violating memory safety).

However, the HashTable::insert_unique() method is safe. What kind of guarantees does it make about calling it multiple times with the same value?

pub fn insert_unique(
    &mut self,
    hash: u64,
    value: T,
    hasher: impl Fn(&T) -> u64,
) -> OccupiedEntry<'_, T, A>

Given that the hash is u64, hash collisions can obviously not be excluded (even if using a cryptographic hash function). And given that nothing in the signature imposes constraints such as T: Eq, the hash table has no way to know if two values that evaluate to the same hash are the same or not. So I assume it's safe to insert twice the same value, and that one of them will be returned upon lookup?

Note: find does know about the equality constraint, so maybe the question is rather: what happens if find gets multiple equality matches for the given hash value?

pub fn find(&self, hash: u64, eq: impl FnMut(&T) -> bool) -> Option<&T>

(Likewise .entry(...).remove() knows about equality, but my use case is insert-only so I don't care about removals misbehaving).

[clarfonthey]

I believe that inserting multiple times just does that: insert multiple times. It may degrade the performance of the table, but it'll still be inserted into the table, it'll still show up on iteration, and when you try to remove it once, I believe that the first copy will be removed, and then the second copy will still be there.

[gendx]

Thank you for the answer. Ultimately Hyrum's Law applies, but I'd be nice to document it more explicitly if the behavior isn't expected to change. (The Swiss Tables algorithm is frozen as far as the hashbrown crate is concerned, right?)

Basically, given the absence of unsafe, there isn't much find() could do if a value was inserted (and/or removed) several times:

1. return one of the matching values (currently observed, at least in an insert-only scenario),
2. return None,
3. return an unrelated value Some(&T),
4. panic, don't terminate, etc.

Explicitly documenting that 2, 3 and 4 don't happen would be useful.

---

And I suppose that the same behavior applies to insert_unique_unchecked() on HashMap and HashSet, but there it has to be unspecified because these APIs are mirrored as-is in the Rust standard library, which doesn't commit to using the hashbrown backend / Swiss Tables algorithm forever.

[cuviper]

and when you try to remove it once, I believe that the first copy will be removed, and then the second copy will still be there.

I think "first" and "second" will also be unspecified, not necessarily insertion order. e.g. if there's any erasures, the later insertion could fill a tombstone that puts it earlier in the probe sequence than the other. Resizing could also perturb this in interesting ways, even if we may be somewhat deterministic in that now.

[clarfonthey]

Yeah, to be clear, the "first" and "second" being actually anywhere located in the table reasonably is probably only true if the only sequence of actions is two inserts, and anything else can completely mess that up. I wasn't thinking too hard about whether other non-resizing inserts after the fact could mess it up (I don't think so) but regardless it's not something we'd want to guarantee.

The only guarantee would be that the data actually is inside the table, and you could obtain it via iteration, but the order is totally unspecified, and the table will probably do things you don't expect (like remove only removing one copy, instead of both), even if there's no UB.