2

While trying to solve a LeetCode problem with Rust, I encountered a strange issue: it looks like I can't create a HashMap with primitive types:

use std::collections::HashMap;

fn two_sum(nums: &Vec<i32>, target: i32) -> (usize, usize) {
    let mut map = HashMap::new();
    for (i, x) in nums.iter().enumerate() {
        match map.get(target - x) {
            Some(k) => return (k, i),
            None => map.insert(x, i)
        };
    }
    return (0, 0);
}

fn main() {
    let ret = two_sum(&vec![1,2,3], 4);
    println!("{}, {}", ret.0, ret.1);
}

The compiler complains:

error[E0308]: mismatched types
 --> two_sum.rs:6:23
  |
6 |         match map.get(target - x) {
  |                       ^^^^^^^^^^ expected reference, found i32
  |
  = note: expected type `&_`
  = note:    found type `i32`

error[E0308]: mismatched types
 --> two_sum.rs:7:32
  |
7 |             Some(k) => return (k, i),
  |                                ^ expected usize, found reference
  |
  = note: expected type `usize`
  = note:    found type `&_`

Is it necessary to always use reference with HashMap in Rust?

EDIT:

Looks like it is necessary... The solution looks a bit ugly but works anyway.

use std::collections::HashMap;

fn two_sum(nums: &[i32], target: i32) -> (usize, usize) {
    let mut map = HashMap::new();
    for (i, x) in nums.iter().enumerate() {
        let df = target - x;
        if map.contains_key(&df) {
            return (*map.get(&df).unwrap(), i);
        }
        map.insert(x, i);
    }
    return (0, 0);
}

fn main() {
    let ret = two_sum(&vec![1,2,3], 4);
    println!("{}, {}", ret.0, ret.1);
}

I wonder if there is a better solution or some best practice to use HashMaps with primitive types?

2
  • The signature of std::collections::HashMap::get says yes, use a reference.
    – ljedrz
    Jan 2, 2017 at 9:05
  • Note: it is more idiomatic for two_sum to take a &[i32] argument (as it is allows for a strict superset of possible arguments). Jan 2, 2017 at 9:05

1 Answer 1

6

If you check the signature of the get method, you will realize that:

  • it accepts an argument &Q bounded by K: Borrow<Q>, Q: Hash + Eq
  • it returns Option<&V>

So, while the hash map itself will contain primitives, the interface of get requires a reference and returns a reference.

This means:

fn two_sum(nums: &Vec<i32>, target: i32) -> (usize, usize) {
    let mut map = HashMap::new();
    for (i, x) in nums.iter().enumerate() {
        match map.get(&(target - x)) {
            //        ^~~~~~~~~~~~~
            Some(k) => return (*k as usize, i),
            //                 ^~~~~~~~~~~
            None => map.insert(x, i)
        };
    }
    return (0, 0);
}

Where I (1) pass a reference to get and (2) dereference the result I get (and convert it from i32 to usize).

However, this does not yet work because map.get(&a) borrows the map for the duration of the map block, so you cannot also insert into it. This in turns is solved by moving the insertion after the match block:

fn two_sum(nums: &Vec<i32>, target: i32) -> (usize, usize) {
    let mut map = HashMap::new();
    for (i, x) in nums.iter().enumerate() {
            let a = target - x;
            match map.get(&a) {
                Some(k) => return (*k as usize, i),
                None => (),
            };
            map.insert(x, i);
    }
    return (0, 0);
}

That's it. Hashmap with primitives types.

Side note: unlike some other languages, primitive types are nigh indistinguishable from other types in Rust.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.