Struct HashMap

Source

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

Expand description

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:

Implementations§

Source §

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

Source

pub fn new() -> Self

Creates an empty map with capacity 0.

The allocation is triggered at the first insertion occurs.

Source

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.

Source

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:

§Complexity

Constant (amortized).

Source

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).

Source

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:

Try to resize hashmap to ensure an appropriate load factor.
Compute hash of the key to get the inner bucket under certain index.
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.

Source

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.

Source

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.

Source

pub fn is_empty(&self) -> bool

Checks whether the container is empty.

§Complexity

Constant.

Source

pub fn len(&self) -> usize

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

§Complexity

Constant.

Source

pub fn bucket_count(&self) -> usize

Gets the number of underlying buckets.

§Complexity

Constant.

Source

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

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

Source

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.

Source

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.