remove a random entry from HashMap in rust

user_9970386 0
Viewed 200

I would like to remove a random element from a HashMap. However, I kept getting this error.

error[E0502]: cannot borrow `self.map` as mutable because it is also borrowed as immutable
  --> src/main.rs:23:9
   |
21 |         let key_to_delete = self.map.keys().skip(x).next().unwrap();
   |                             -------- immutable borrow occurs here
22 |         println!("key_to_delete: {:?}", key_to_delete);
23 |         self.map.remove(&key_to_delete);
   |         ^^^^^^^^^------^^^^^^^^^^^^^^^^
   |         |        |
   |         |        immutable borrow later used by call
   |         mutable borrow occurs here

error: aborting due to previous error

For more information about this error, try `rustc --explain E0502`.

However, if I add a .clone() at the end of that line, the error is gone. While I fixed this problem (mostly by trials and errors), I still don't understand why it works. Specifically, why does this error showed up in the first place? Shouldn't the immutable reference to self.map get dropped after the line

let key_to_delete = self.map.keys().skip(x).next().unwrap()

finish executing? In this example, the key is of type i32, which only takes 4 byte. Therefore, it's OK to clone. But what if the key is some large struct or clone is not desirable for other reasons? How then should I solve this problem?

Another observation is that my IDE (Intellij with rust plugin) showed that the type of key_to_delete is &i32 if I don't have .clone() and i32 if I do. I am not sure if this matters.

Any clarification is appreciated.

Here is my code.

use std::collections::HashMap;
use rand::{Rng, thread_rng};

#[derive(Debug)]
struct MyStruct {
    map: HashMap<i32, i32>,
}

impl MyStruct {
    fn new() -> Self {
        MyStruct { map: HashMap::new() }
    }

    fn add(&mut self, key: i32, value: i32) {
        self.map.insert(key, value);
        println!("after add: {:?}", self.map);
    }

    fn delete(&mut self) {
        let x: usize = thread_rng().gen_range(0..self.map.len());
        let key_to_delete = self.map.keys().skip(x).next().unwrap().clone(); // this "clone" is critical
        println!("key_to_delete: {:?}", key_to_delete);
        self.map.remove(&key_to_delete);
        println!("map after delete: {:?}", self.map);
    }
}

fn main() {
    let mut c = MyStruct::new();
    c.add(1, 2);
    c.add(3, 4);
    c.add(5, 6);
    c.delete();
}
rust
2 Answers

When you call self.map.keys().skip(x).next().unwrap() you don't get a key - you get a reference to a key.

Rust guarantees that this reference stays valid for as long as it lives - that's the whole idea behind Rust's borrow checker and memory safety in general. In our case, this it means that Rust guarantees that the key inside the map (alongside the associated value) will be present in the map as long as your reference to the key lives.

But the way the Rust compiler enforces it is rather brutal - it just disallows you to change the state of the map in any way as long as your reference to the key lives. Unfortunately, as a result, you cannot use your reference to remove its corresponding entry from the map.

To illustrate this point, let's look at a slightly modified version of your code:

fn delete(&mut self) { //not really a delete at this point
    let x: usize = thread_rng().gen_range(0..self.map.len());
    let key_to_delete = self.map.keys().skip(x).next().unwrap(); // this "clone" is gone
    self.map.insert(123, 456); // <- this will cause a compiler error
    println!("key_to_delete: {:?}", key_to_delete);
    // self.map.insert(123, 456);  // <- this will not cause a compiler error as the reference to the key no longer exists
    println!("map after delete: {:?}", self.map);
}

Here I've changed the remove to insert so that we know we aren't risking that our key might be deleted. And yet the code doesn't compile for exactly the same reason as you originally reported.

user_57698820

It’s at least possible to remove an arbitrary entry from a HashMap whose keys don’t implement Clone, in a somewhat roundabout way, on current Nightly using the experimental hash_raw_entry feature:

#![feature(build_hasher_simple_hash_one)]
#![feature(hash_raw_entry)]

use std::collections::hash_map::{HashMap, RawEntryMut};
use std::hash::{BuildHasher, Hash};

fn pop<K: Hash, V>(m: &mut HashMap<K, V>) -> Option<(K, V)> {
    let hash = m.hasher().hash_one(m.keys().next()?);

    match m.raw_entry_mut().from_hash(hash, |_| true) {
        RawEntryMut::Occupied(entry) => Some(entry.remove_entry()),
        RawEntryMut::Vacant(_) => unreachable!("no entry with hash of first key"),
    }
}
user_7071110
Related