HashMap - rust-course

The HashMap structure is a map that uses a hashing algorithm to store key/value pairs. A map is a data structure that stores key/value pairs. Each key has a value associated to it, and is unique inside the map. In a HashMap, the key of each pair is processed through the hashing algorithm in order to generate a hash value, which is used to store efficiently the key/value pair using an array. See Program 1. The hashing algorithm has for goal to associate a bucket to each key, by computing the bucket index from the key. Possibly, multiple keys will be associated to the same index. Those key/values are stored together in another structure.

Buckets
  │
  ▼
┌────┐
│  0 │
├────┤     ┌──────┬──────┬──────┐
│  1 │ ──> │"a"/13│"g"/77│"z"/48│ key/value pairs
├────┤     └──────┴──────┴──────┘
│  2 │
├────┤
│  3 │
├────┤     ┌──────┐
│  4 │ ──> │"k"/55│ key/value pairs
├────┤     └──────┘
│  5 │
├────┤     ┌──────┬──────┐
│  6 │ ──> │"b"/65│"t"/11│ key/value pairs
├────┤     └──────┴──────┘
│  7 │
└────┘

Program 1:An example of a HashMap

To be usable inside a HashMap the keys must have a type that implements the traits Eq and Hash. Moreover it must verify:

k1 = k2 \Rightarrow hash(k1) = hash(k2)

(2)

The main methods of the HashMap are presented in Table 1.

Table 1:Some methods of HashMap

Method	Description
`clear()`	Removes all elements.
`contains_key(k)`	Returns `true` if this map contains the key `k`. 𝒪(1) time.
`entry(k)`	Gives access to key/value pair. 𝒪(1) time.
`get(k)`	Returns a reference to the value, if any. The returned type is `Option<&V>`. 𝒪(1) time.
`insert(k, v)`	Inserts a new key/value pair. 𝒪(1) time.
`is_empty()`	Returns `true` if this map contains no elements.
`iter()`	Returns an iterator on all key/value pairs.
`keys()`	Returns an iterator over the keys. Order is arbitrary.
`len()`	Returns the number of elements.
`new()`	Creates a new map.
`remove(k)`	Removes the specified key from the map.
`values()`	Returns an iterator over the values. Order is arbitrary.

28.1.1Creating a new instance¶

To create a new hash map HashMap<K, V>, an easy way, like for the Vec type, is to let the compiler infer the type. Inserting at least one key/value pair will give the compiler the information it needs:

use std::collections::HashMap;

let mut scores = HashMap::new();
scores.insert(String::from("Blue"), 10);
scores.insert(String::from("Yellow"), 50);

Couldn't automatically determine type of variable `scores`.
Please give it an explicit type.

Ownership of keys and values

When inserted inside a map, the keys and values may be copied or moved, depending on their type. Types that implement the Copy trait are copied (e.g.: basic types), other types are moved. For those last types, we may wish to clone them before passing them:

let k = String::from("Red");
scores.insert(k.clone(), 23);
k

It is also possible to construct a HashMap from two vectors of the same length. Here are a vector of string with a vector of integers:

let names = vec!["Paul", "John", "George"];
let values = vec![10, 17, 23];

Using iterators and the zip() method we can combine the iterators and collect the result inside a new HashMap:

let other_scores: HashMap<_, _> =
  names.into_iter().zip(values.into_iter()).collect();

Here is the result:

other_scores

28.1.2Getting a value¶

Getting a value from the map is done using the get() method, which returns an Option<V>:

let team_name = String::from("Blue");
match scores.get(&team_name) {
  Some(score) => println!("The score of team {team_name} is {score}."),
  None => println!("No score for team {team_name}"),
}

HashMap implements the Index trait, and thus provides the indexing operator ([]) for retrieving a value. Example:

scores["Blue"]

28.1.3Iterating¶

Using a for loop we can loop onto the key/value pairs:

for (k, v) in &scores {
  println!("{k}: {v}");
}

28.1.4Replacing an existing value¶

Inserting a key/value pair, replaces the eventual existing key:

scores.insert(String::from("Blue"), 34);
scores

28.1.5Adding a value if no key present¶

The or_insert() of the Entry structure, allows to insert a key/value only if the key is not already defined:

scores.entry(String::from("Green")).or_insert(18)

28.1.6Updating an existing value¶

We suppose we want to increment the score of a team. We retrieve a reference on the current score of team "Red", using the or_insert() method in case the team is not declared, and increment it by dereferencing it with the * operator. The or_insert() method returns a &mut V:

{
  let count = scores.entry("Red".to_string()).or_insert(0);
  *count += 1;
  println!("count is now {count}");
}