Ownership when overwriting values in a map

I am wondering how a map actually "destroys" (what is the proper rust term for this?) its values when its overwritten.

I wrote the following code:

use std::rc::Rc;
use std::collections::HashMap;

fn main() {
    let mut distances: HashMap<i32, Rc<i32>> = HashMap::new();
    let test = Rc::new(1);
    
    for i in 0..5 {
        distances.insert(i, Rc::clone(&test));
    }
    
    println!("{}", Rc::strong_count(&test)); //6
    distances.insert(8, Rc::clone(&test));
    println!("{}", Rc::strong_count(&test)); //7
    distances.insert(3, Rc::clone(&test));
    println!("{}", Rc::strong_count(&test)); //7
}

and it actually does exactly what I would have expected it to do in the sense that overwriting the value at key=3 destroys the previous value.
However I do not quite understand how exactly this works under the hood. I'd imagine that the hashmap knows that there is a value being overwritten, but I don't really see how exactly the hashmap would get rid of the ownership. Does it call some function to explicitly remove ownership or how does this work? Or am I forgetting something really obvious from the ownership rules?

The map knows whether there was a value with the same key and it is actually returned as an Option when you call insert. However even if this didn't happen the map could still call drop (or the unsafer std::ptr::drop_in_place) to destroy the object.

2 Likes

Actually, the HashMap does not drop the value that is previously stored in the referenced entry. It returns it. You drop it, because you don't use the return value of HashMap::insert. You can look at the implementation of HashMap::insert here.

3 Likes

"Drop", which is also the trait you implement if you want something to happen when your value is dropped.

So as jofas pointed out, the value is actually dropped by your code not storing it when insert returns it, but more generally, it's baked in at the statement level - re-assigning a value of a type that implements Drop will implicitly call the drop method on the old value before actually doing the write, so that's how your value would disappear if the hashmap had just overwritten it rather than returned it. It is similarly implicitly called if a Drop value goes out of scope. Both of these rules apply recursively, i.e. if your Drop type is a field of something else that's overwritten or falls out of scope, drop is called on it and its fields.

1 Like

I think you are. Even if the previous value weren't returned (and so the map itself needed to get rid of the value), it could in theory be as easy as:

fn insert(&mut self, key: K, value: V) {
    // compute table index
    let index = calculate_hash(&key) % self.len();
    self.slots[index] = (K, V);
}

which means that it would simply overwrite any pre-existing key-value pair at the given index in some array or table. Overwriting a place with a new value always drops the previous value of that place. This is not "the map" actively doing anything. This is just how the language has to work in order not to leak resources.

This is, conceptually, just the same thing what happens when you write

let mut s = String::from("hello world");
s = String::from("a new string"); // previous value is dropped here

In this much simpler example, there's no collection storing the String. It's simply in a variable s. The language ensures that upon assigning a new value to s, its previous String is correctly deallocated (by automatically invoking its Drop::drop() method).

(Of course, the actual insertion is not nearly as simple as I described in the first snippet, because slots can be uninitialized, so the map needs to check whether it is initialized or not, but you get the idea.)

7 Likes

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.