Is it possible to modify a mutable vector when it is a key in HashMap?

Question

Here is my example:

use std::collections::HashMap;

fn main() {
    let mut my_map = HashMap::new();
    let mut my_vec = vec![5,6,7];    
    my_map.insert(my_vec, 4);

    // This part is fine, so I can create HashMap
    // with mutable Vector as key.

    my_vec.push(8);
}

However, I cannot actually modify the vector! my_vec.push(8); causes the following error:

post_test_19.rs:14:5: 14:11 error: use of moved value: `my_vec` [E0382]
post_test_19.rs:14     my_vec.push(8);
                       ^~~~~~
post_test_19.rs:7:19: 7:25 note: `my_vec` moved here because it has type `collections::vec::Vec<i32>`, which is non-copyable
post_test_19.rs:7     my_map.insert(my_vec, 4);
                                    ^~~~~~
error: aborting due to previous error

Now the HashMap owns the Vec, so I cannot modify it.

As far as I understand, you cannot modify a Vec if it is used as key in HashMap even though it is technically mutable. Is my understanding correct? Is there a trick or a corner case that I am missing?

Answer 1

No, you cannot modify it, and even if you could, you absolutely should never do such a thing.

In your example, the reason you cannot modify the vector is because you no longer own it. You've transferred ownership of it to the map. That's what "use of moved value" means.

Let's say you had some way of modifying the key of the map (I'm not going to provide any examples to help prevent people from doing this). The main problem is that you'd be breaking an invariant of the HashMap:

It is a logic error for a key to be modified in such a way that the key's hash, as determined by the Hash trait, or its equality, as determined by the Eq trait, changes while it is in the map.

The reason for this is simple once you understand how hashmaps work. When you add a key, an algorithm is run that converts the key into an integer (the key is hashed). Then, this integer is used to find a space in an array to store the value.

If you changed the key, then the value would be stored in the wrong spot in the array. As a simple example, imagine that the hashing algorithm for vectors was simply the number of items in the vector. If you added vec![1] as a key, it would be stored in array slot 1. If you then change the key, it should hash to 2, but would still be stored in slot 1!

Answer 2

I am afraid this all stems from a misunderstanding about what mut means.

You need to distinguish two terms:

• vec![5, 6, 7] produces an instance of the Vec type
• my_vec is a binding, that is to say, a name given to an instance of a type, because it's easier to manipulate instances by name (but not necessary, cue Forth)

When you declare let mut my_vec, you are:

• declaring a mutable binding
• to which an instance of Vec is bound

The instance itself cannot be called mutable, it is meaningless as illustrated by the following valid snippet:

let mut my_vec = vec![5, 6, 7];
let     other = my_vec;          // ownership transfer
let mut yac   = other;           // ownership transfer

In this snippet, we see:

• an instance of Vec type being bound to a mutable binding my_vec
• then being bound to an immutable binding other
• then being bound to a mutable binding yac

which hopefully showcases that mutability is a property not of the instance but the binding.

This is where inherited mutability comes into play:

• If you are in possession of a mutable binding to an instance of T (let mut x: T = ...;), or binding to a mutable reference to an instance of T (let x: &mut T = ...;), then you can not only mutate its fields, but also obtain mutable references to these fields to modify their own fields... recursively.
• And conversely, if all you hold is an immutable reference to an instance of type T (let x: &T = ...;), then all you can do is read its fields or obtain immutable references to these fields to read their own fields... recursively (*).

(*) Ok, Ok, it's a simplification, the cell types for example can be modified via immutable references; that's for another day!