Why do I need to dereference HashMap's key twice?

Question

I've only been learning Rust for a few days. I think that these two code samples are the same, but the compiler disagrees. Can you explain what happens in part II? Why do I need to dereference key twice, but value once?

Part I

use std::collections::HashMap;

let mut h = HashMap::new();   
h.insert(1, 1);
h.insert(2, 2);

let mut keys: Vec<i32> = Vec::new();
let mut values: Vec<i32> = Vec::new();

for (k, v) in &h {
    keys.push(**k);
    values.push(*v);
}

Part II

fn main() {
    let mut v = vec![2, 3, 5, 1, 2, 3, 8, 6, 3, 1, 4, 6, 7];

    use std::collections::HashMap;

    let mut h = HashMap::new();

    for element in &v {
        let count = h.entry(element).or_insert(0);

        *count += 1;
    }

    let mut keys: Vec<i32> = Vec::new();
    let mut values: Vec<i32> = Vec::new();

    for (k, v) in &h {
        keys.push(**k);
        values.push(*v);
    }

    println!("{:?}", keys);
}

Answer 1

Since you didn't specify the type of your HashMap, the compiler inferred it.

let v = vec![1i32, 2, 3];
let mut h = HashMap::new();
for i in &v {
    h.insert(i, ());
}

The type of h here is HashMap<&i32, ()>, and the type of i is &i32. Why does i have the type &i32? Because that's how IntoIterator on &Vec is implemented. In general, when you iterate over a reference, you get references.

If you want a HashMap with a key type that isn't a reference, you can say so. Then you'll get a different error message when you attempt to insert the reference.

let v = vec![1i32, 2, 3];
let mut h: HashMap<i32, ()> = HashMap::new();
for i in &v {
    h.insert(i, ());
}

error[E0308]: mismatched types
 --> src/main.rs:6:18
  |
6 |         h.insert(i, ());
  |                  ^ expected i32, found &i32
  |
  = note: expected type `i32`
             found type `&i32`

And then you can replace the key to be inserted with *i.

Answer 2

The full type of your HashMap is inferred as HashMap<&i32, i32>. This can be verified by using the following trick:

let () = h;

to trigger a type error:

error[E0308]: mismatched types
  --> src/main.rs:17:9
   |
17 |     let () = h;
   |         ^^ expected struct `std::collections::HashMap`, found ()
   |
   = note: expected type `std::collections::HashMap<&{integer}, {integer}>`
              found type `()`

(at this point the compiler was not yet sure the final type will be HashMap<&i32, i32>, hence the {integer}s in the type signature)

When you are iterating over &h, the (k, v) tuple has type (&&i32, &i32) (which can also be confirmed with the aforementioned trick), which is why you need a double dereference for k and only one for v.

Answer 3

You only need to dereference once

Here's an example of your code working