Struct rust_algorithm_club::collections::HashMap

pub struct HashMap<K, V> where
    K: Hash + Eq,  { /* private fields */ }

A hash map implemented with separate chaining collision resolution strategy.

This implementation is focused on hash map functionalities, so we choose to adopt Rust DefaultHasher to avoid avalanche of details, and vectors as the underlying data structure for separate chaining method.

The interface is a simplified version of Rust HashMap.

References:

• Rust Standard Library: std::collections::HashMap
• C++ Container Library: std::unordered_map

Implementations

impl<K, V> HashMap<K, V> where
    K: Hash + Eq, 

pub fn new() -> Self

Creates an empty map with capacity 0.

The allocation is triggered at the first insertion occurs.

pub fn with_capacity(cap: usize) -> Self

Creates a map with a given capacity as the number of underlying buckets.

Parameters

• cap: The number of bucket in the map.

pub fn get<Q>(&self, key: &Q) -> Option<&V> where
    K: Borrow<Q>,
    Q: Hash + Eq + ?Sized, 

Gets a reference to the value under the specified key.

We use Q here to accept any type that K can be borrowed as. For example, given a HashMap m using String as key, both m.get(&String) and m.get(&str) would work because String can be borrow as &str. The same technique is applied for get_mut and remove.

Learn more about Borrow trait:

• Trait std::borrow:Borrow
• TRPL 1st edition: Borrow and AsRef

Complexity

Constant (amortized).

pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V> where
    K: Borrow<Q>,
    Q: Hash + Eq + ?Sized, 

Gets a mutable reference to the value under the specified key.

Complexity

Constant (amortized).

pub fn insert(&mut self, key: K, value: V) -> Option<V>

Inserts key-value pair into the map. Replaces previous value if the same key exists at the same index.

Returns the old value if the key presents. Otherwise returns None.

Steps are described as following:

1. Try to resize hashmap to ensure an appropriate load factor.
2. Compute hash of the key to get the inner bucket under certain index.
3. Find if there is already a pair with identical key.
   1. If yes, substitute for it.
   2. Else, push new value into the bucket.

Parameters

• key - Key of the pair to insert.
• value - Value of the pair to insert.

Complexity

Constant (amortized).

Panics

Panics when either hash map cannot make a hash, or cannot access any available bucket to insert new value. These cases shall not happend under a well-implemented resize policy.

pub fn remove<Q>(&mut self, key: &Q) -> Option<V> where
    K: Borrow<Q>,
    Q: Hash + Eq + ?Sized, 

Removes a pair with specified key.

The caveat is that ordering in the bucket cannot be preserved due to the removal using swap_remove to ensure O(1) deletion.

Parameters

• key - Key of the pair to remove.

Complexity

Constant. This operation won’t shrink to fit automatically.

pub fn clear(&mut self)

Removes all key-value pairs but keeps the allocated memory for reuse.

Complexity

Linear in the size of the container.

pub fn is_empty(&self) -> bool

Checks whether the container is empty.

Complexity

Constant.

pub fn len(&self) -> usize

Gets the number of key-value pairs in the container.

Complexity

Constant.

pub fn bucket_count(&self) -> usize

Gets the number of underlying buckets.

Complexity

Constant.

pub fn iter(&self) -> impl Iterator<Item = (&K, &V)>

Creates an iterator that yields immutable reference of each element in arbitrary order.

pub fn iter_mut(&mut self) -> impl Iterator<Item = (&K, &mut V)>

Creates an iterator that yields mutable reference of each element in arbitrary order.

pub fn into_iter(self) -> impl Iterator<Item = (K, V)>

Creates a consuming iterator yielding elements in arbitrary order. That is, one that moves each value out of the list. The list cannot be used after calling this.

Trait Implementations

impl<K, V> Default for HashMap<K, V> where
    K: Hash + Eq, 

fn default() -> Self

Returns the “default value” for a type.