Tracking issue for HashMap OccupiedEntry::{replace_key, replace_entry}

[Binero]

At the moment the only way to replace a map entry with a new one, swallows the old key. In cases the user wants to keep the old key, the only way to do so is to first remove_entry and to then insert a new one. This requires two map look-ups.

As the Entry API aims to make operations that would otherwise require two look-ups into operations that require only one, the replacing of an entry is an obvious hole in the API.

• Implemented in Allow replacing HashMap entries #44278
• Tweaked in Addressed issues raised in #44286. (OccupiedEntry::replace_entry) #45152

[stepancheg]

While it is indeed a missing API, there are several issues with this new API implemented in PR #44278:

• it seems to panics if take_key was called before (it is not public API)
• it replaces both key and value, so
• • is not possible to replace only key or only value (there's insert function which replaces only value)
• • it does do completely independent things in one operation
• it is not possible to replace key in VacantEntry (it is pointless)
• it takes self, while it could take &mut self, so replace could be called again if it is needed for some reason
• key replacement it is against least surprise principle

I think HashMap::replace should be different:

impl OccupiedEntry<...> {
    fn replace_value(&mut self, new_value: V) -> V {
        replace value with new value, do not touch the key.
    }
}

And probably that's it.

If we need to replace key for some reason, replace_key operation needs to be added to both OccupiedEntry and VacantEntry.

[Binero]

• take_key cannot be called before, all functions that call it consume the entry.
• The point is to be able to swap out the key without multiple lookups. replace_value beats the point.
• A VacantEntry does not have a key, so it's unclear how the function would work.

[stepancheg]

take_key cannot be called before, all functions that call it consume the entry.

Oh, it is not public API, thanks.

The point is to be able to swap out the key without multiple lookups. replace_value beats the point.

But this function does not allow to replace key without replacing value.

BTW, there's already a function to replace value, it's called insert.

So if we had replace_key instead of current replace, then current replace could be emulated as:

occupied_entry.insert(new_value);
occupied_entry.replace_key()

replace_key is not possible now, and replace is redundant if we had replace_key.

A VacantEntry does not have a key, so it's unclear how the function would work.

Please ignore that.

[Binero]

I will take a look at replace_key when I have time, probably next week.

[Binero]

@stepancheg I think it's probably better to have replace_key consume the entry, because the semantics of the function would otherwise change after the first call.

[SimonSapin]

This has been in Nightly for long enough that I’m inclined to stabilize, but I don’t quite understand the use case. @Binero, can you explain some more why it can be important to recover the old key rather than the new one (passed to HashMap::entry() which hashes and compares equal?

[Binero]

@SimonSapin

It is quite a niche function, so it's certainly not instantly obvious where this would be useful.

That said, it has some uses when you want to for example lower the memory footprint of a HashMap by swapping out an Rc<T> with another, equivalent, Rc<T> that you are already using elsewhere.

If either T or the HashMap is large enough, this could reduce the memory footprint of the application by quite a lot.

[joshlf]

Not sure if this was the original intent, but I have a use case for replace_key where I need the key back (by value) in certain failure conditions. I have code like:

match map.entry(key) {
    Entry::Occupied(entry) => 
        entry.into_mut().do_thing_which_can_fail().map_err(|_| entry.replace_key()),
    Entry::Vacant(entry) => ...,
}

Without replace_key, I'd need to do map.entry(key.clone()) instead so that I could still have key around by value.

[jonhoo]

I may be off-base here, but I feel like there is a requirement for these methods that the key continue to have the same hash? If so, that should almost certainly be stated in the documentation.

[Amanieu]

That is correct.

[jonhoo]

Ah, reading it again, I guess the reason this is okay is because you can only get an OccupiedEntry in the first place if the provided key already hashes to the appropriate value. Not mentioning it in the docs seems fine then!

[KodrAus]

It's not super easy to spot from this issue alone, but the replace_key method is incompatible with another unstable Entry::insert method. See: #65225 (comment)

[joshlf]

Would somebody mind providing a short status update on what's left before stabilization?

[qm3ster]

Maybe it should at least return (K, &mut V), since it will consume the entry? (Which it has to, in order to return the key.)

My ideal API would be:

impl OccupiedEntry {
    fn swap_keys(&mut self);
    // +
    fn into_key(self) -> K;
}

It allows the most flexibility and I don't see an immediate drawback.
e.replace_key() is then just e.swap_keys(); e.into_key()
The latter can also be substituted for

fn into_inner(self) -> (K, &mut V);

Which is a little less ergonomic since we could already get that &mut with the HashMap's lifetime.
Edit: Ah, only into_mut(self) gives us the HashMap's lifetime, so maybe this is valuable.

Basically, I really want my K back :)

[cuviper]

These methods will currently unwrap-panic if the OccupiedEntry was created by VacantEntry::insert_entry or a vacant Entry::insert_entry, both of which will be stable in Rust 1.59. In this case we no longer have a key because it was used for the new insertion.

edit: that's #65225, as mentioned already in #44286 (comment)

[qm3ster]

This is actually really wild.
It looks like OccupiedEntry.key has always been an Option<K>, but it was always constructed as a Some(key) and unwraped everywhere.
Was entry_insert planned from the initial commit of hashbrown?

[Amanieu]

I believe that part of hashbrown was just copied from the standard library when it was first implemented.

[eaglgenes101]

The entry_insert feature, as implemented and heading towards stabilization, clashes with this feature. (Specifically, using the entry replacement API after insert_entry causes a panic, since the entry replacement API relies on the entry key being present, while insert_entry will remove it.)

[Amanieu]

I think we should remove this feature because it requires OccupiedEntry to hold the key that was used when searching for the entry. This conflicts with other was that OccupiedEntry can be used, such as the insert_entry API which allows converting a VacantEntry to an OccupiedEntry by inserting a value.

While there are valid use cases for modifying the key of an existing entry in a HashMap, these use cases usually involve the key type holding additional data in addition to the key itself and are better addressed by using the HashTable API in hashbrown instead.

@rfcbot fcp close

[rfcbot]

Team member @Amanieu has proposed to close this. The next step is review by the rest of the tagged team members:

• @Amanieu
• @BurntSushi
• @dtolnay
• @joshtriplett
• @m-ou-se

No concerns currently listed.

Once a majority of reviewers approve (and at most 2 approvals are outstanding), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

[rfcbot]

🔔 This is now entering its final comment period, as per the review above. 🔔

[rfcbot]

The final comment period, with a disposition to close, as per the review above, is now complete.

As the automated representative of the governance process, I would like to thank the author for their work and everyone else who contributed.

[71]

Note for anyone hit by the removal of these functions: the same result can be achieved with raw_entry_mut() and insert_key():

match map.raw_entry_mut().from_key(&key) {
    hash_map::RawEntryMut::Occupied(mut occupied) => occupied.insert_key(key),
    hash_map::RawEntryMut::Vacant(_) => {}
}

Playground.

[Amanieu]

The raw entry API is also slated for removal. Can you have a look at hashbrown's entry_ref API instead to see if it solves your use cases? That is important information as to whether it's worth upstreaming to the standard library.

[71]

@Amanieu Oh, I wasn't aware. In my particular case I also make use of other more "exotic" features of raw entries (supplying hashes, custom comparison functions), so I will likely need to go for hashbrown anyway. I don't think entry_ref would have helped me either because Borrow<Q> doesn't seem to apply to my case (I don't have &Q, I have impl Deref<Target = Q>), although I could see entry_ref being useful to others who have less "exotic" keys.

[constituent]

@Amanieu hashbrown's entry_ref API is itself very useful. Usually with a HashMap<String, T>, I'd like to entry it with &str, only to_owned() while necessary.
However, replace_key is another unrelated ergonomic tool IMHO. If it has to be removed due to implementation reasons, a similar API of maybe HashMap would be much appreciated.

[Amanieu]

@constituent If you need to mess with keys in ways where "equivalent" keys actually carry additional data then the correct tool to use is hashbrown's HashTable type which gives you all the low-level control you need. However this is not planned for inclusion in the standard library at this time: if you need it then you should use it from the hashbrown crate.