HashMap

This is a non-exhaustive non-academic, example-driven, rather-practical guide on how to use the HashMap in Rust. As a side effect of working on the HashMap some hands-on examples of Rust's unique concepts of ownership and borrowing references will be demonstrated.

Prelude

Before we get to the real stuff, here's is something which is not directly HashMap, but more Rust pointer and friends stuff, however got me stuck for some time.

fn add_map(map: &mut HashMap<~str, uint>, k: &str, v: uint) {
  map.insert(k.to_owned(), v); 
}

In order to be able to modify, make sure the map is mutable both in the add_map method as in the declaration of the HashMap. If you don't you will get an error saying error: cannot borrow immutable dereference of & pointer as mutable.

let mut map: HashMap<~str, uint> = HashMap::new();
let key = ~"key string";
let val = 1;

add_map(&map, key, val);
println!("{:?}", key);

Notice that by using &map, we pass a reference to our map to the function add_map, in rust terms we borrow the map, but we remain the owner of it.

The key gets passed to add_map as a reference, too, hence you need to_owned() in order to copy it into the key field of the map. The map now owns its own copy of key.

If you don't need to access the key after adding to the map, you could move it into the map. This will be more efficient, no memory copying, but trying to access key afterwards will result in a error: use of moved value: key:

fn add_map_move(map: &mut HashMap<~str, uint>, k: ~str, v: uint) {
  map.insert(k, v); 
}

let mut map: HashMap<~str, uint> = HashMap::new();
let key = ~"key string";
let val = 1;

add_map_move(&map, key, val);
println!("{:?}", key);          // -> error: use of moved value: `key`

Save yourself some sorrow and do not do this (unless you know exactly what you're doing)

// DON'T!
let mut map: HashMap<&str, uint> = HashMap::new();

Creating and inserting

Boring...

let mut map = HashMap::<~str, uint>::new();
map.insert(~"foo", 1);
// or

let mut map: HashMap<~str, uint> = HashMap::new();
map.insert(~"bar", 2);

An immutable HashMap

You can create a HashMap as mutable and then freeze it (by assigning without mut), to prevent further modification:

fn create_immutable() -> HashMap<~str, uint> {
  let mut map = HashMap::<~str, uint>::new();
  map.insert(~"foo", 1);
  map // insert returns whether the key was already present in the map, hence returns the map
}

let imap = create_immutable(); // without the mut it is immutable
imap.insert(~"foo", 1); // -> error: cannot borrow immutable local variable as mutable

Another option to create an immutable HashMap would be to use HashMap::from_iterator

Inserting and modifying at the same time

For the definitions of those functions see std::hashmap::HashMap

Most straightforward insert

let mut map = HashMap::<~str, uint>::new();
map.insert(~"foo", 1);

doing a find, and an insert if the searched key does not exist

let mut map = HashMap::<~str, uint>::new();
assert!(!map.contains_key(&~"foo"));

map.find_or_insert(~"foo", 1);
assert!(map.contains_key(&~"foo"));

Doing a find, inserting with a proc(), using the key to construct the value

let mut map = HashMap::<~str, ~str>::new();
assert!(!map.contains_key(&~"foo"));

map.find_or_insert_with(~"foo", |k| *k + ~"bar");
assert_eq!(*map.get(&~"foo"), ~"foobar");

Love this one - insert a new one if the current isn't present, update if it is present

let mut map = HashMap::<~str, uint>::new();
assert!(!map.contains_key(&~"foo"));

// running this for the first time, will add "foo" with the value 1
map.insert_or_update_with(~"foo", 1, |_k, v| *v += 1);
assert_eq!(*map.get(&~"foo"), 1);

// running the same for the second time, will add +1 to "foo"
map.insert_or_update_with(~"foo", 1, |_k, v| *v += 1);
assert_eq!(*map.get(&~"foo"), 2);

and last but not least the almighty mangle. I had a couple of serious struggles with mangle.

let mut map = HashMap::<~str, uint>::new();
assert!(!map.contains_key(&~"foo"));

// for key "foo", take the initial value 1 and add +10
map.mangle(~"foo", 1,         // take this value as a
           |_k, a| a + 10,    // apply this function on a
           |_k, v, a| *v -= 2
          ); 
assert_eq!(*map.get(&~"foo"), 11);

let x = *map.mangle(~"foo", 1,
           |_k, a| a + 10,
           |_k, v, _a| *v -=  2 // take the current value in ~"foo" and apply the function on it
          );

assert_eq!(*map.get(&~"foo"), 9);

The first mangle does not assign the return value, it just inserts into the map under the key ~"foo" the value of a + 10, where a is the seconed parameter of the function.

The second mangle fires the second proc passed, which subtracts 2 from the value stored under ~"foo". Notable here is, that the return value of the mangle function is dereferenced with *, thus a copy of the value is created. The mangle returns a reference into the map, to the value stored under ~"foo" and therefor borrows the whole map! Any further operations on map wouldn't be possible.

Getting it back

The basic get gets the value, but fails if the value isn't present. To get back a mutable version use get_mut instead.

fn test_get(){
  let mut map = HashMap::<~str, uint>::new();
  map.insert(~"foo", 1);

  let r = *map.get(&~"foo");

  map.insert(~"bar", 2); // works!
}

As in the previous example with mangle, make sure you dereference the returned value to make a copy if you want to be able to access the map afterwards.

Instead of the dereference, you can make your intent more expclicit and use get_copy

let mut map = HashMap::<~str, uint>::new();
map.insert(~"foo", 1);

let r = map.get_copy(&~"foo");
assert_eq!(r, 1);

map.insert(~"bar", 2); // works!

Fun stuff about get_mut is that once you got the reference to the value, you can modify the value inside the map directly!

let mut map = HashMap::<~str, uint>::new();
map.insert(~"foo", 1);

{
  let mut r = map.get_mut(&~"foo");
  *r += 1;
}
assert_eq!(*map.get(&~"foo"), 2);    // Look Ma, I updated the map!

The curlies around the mutation operation allow us to introduce a new lifetime, and at the end of it we return the borrow for r (and the map along with it), so we can again access the map to get the value one more time.

Failsafe getting

Now find which returns None if the key could not be found and Some if it was found. Again, substitute for find_mut to get back a mutable version. This should be the preferred way of retrieving data from a hash.

let mut map = HashMap::<~str, uint>::new();
map.insert(~"foo", 1);

let s = match map.find(&~"foo") {
  None      => 0,
  Some(v)   => *v
};

As in get_copy you can use find_copy instead of find

let mut map = HashMap::<~str, uint>::new();
map.insert(~"foo", 1);

let r = match map.find_copy(&~"foo") {
  None      => 0,
  Some(v)   => v    // no derference needed here
};

assert_eq!(r, 1);

Pop

This comes in handy sometimes - getting a value from the hash and at the same time removing it from the hash

let mut map = HashMap::<~str, uint>::new();
map.insert(~"foo", 1);

let r = match map.pop(&~"foo") {
  None      => 0,
  Some(v)   => v
};

assert_eq!(r, 1);
assert!(!map.contains_key(&~"foo")); // ~"foo" is gone

Iterating

You can also walk over the key - value pairs in a hash

let mut map = HashMap::<~str, uint>::new();
map.insert(~"foo", 1);
map.insert(~"bar", 2);

let mut numbers = ~[];
for (_k,v) in map.iter() {
  numbers.push(*v);         // copying the values
}

assert!(numbers.contains(&2));
assert!(numbers.contains(&1));

//assert_eq!(numbers, ~[2, 1]); // beware, order might change, so this would fail randomly

To simultaneously iterate over the hash and remove the values at the same time, use iter_move.

As an aside, a more functional way - instead of pushing to the numbers vector, to get the values would be

let v = map.values().map(|v| v.clone()).to_owned_vec();

Preserving Order

Be cautious, you cannot rely on the order in which the pairs are coming to your iterator! If you need a specific order use a collections::TreeMap instead:

extern mod extra;
use collections::TreeMap;

#[test]
fn test_treemap() {
  let mut map = TreeMap::<~str, uint>::new();
  map.insert(~"foo", 1);
  map.insert(~"boo", 2);

  let mut numbers = ~[];
  for (_k,v) in map.iter() {
    numbers.push(v.clone());
  }
  assert_eq!(numbers, ~[2, 1]);
}

Version

The examples run on rustc head

% rustc -v
rustc 0.10-pre (47e1445 2014-02-09 20:41:27 -0800)

For more discussion head over to Reddit