Struct HashMap

pub struct HashMap<K: Hash + Eq, V, B: BuildHasher = RandomState> { /* private fields */ }

A map of keys to values which relies on the keys implementing Hash.

A custom load factor is not supported at this point, with the default being 4/5.

It is a logic error for keys in a HashMap to be manipulated in a way that changes their hash. Because of this, HashMap’s API prevents mutable access to its keys.

Time Complexity

For this analysis of time complexity, variables are defined as follows:

• n: The number of items in the HashMap.

Method	Complexity
len	O(1)
insert	O(1)**, O(n)
insert_unchecked	O(1)*
get	O(1)*
remove	O(1)*
contains	O(1)*
reserve	O(n)***, O(1)

* In the event of a has collision, these functions will take additional time, while a valid / correct location is found. This additional time is kept at a minimum and hash collisions are unlikely especially with a large capacity.

** If the HashMap doesn’t have enough capacity for the new element, insert will take O(n). * applies as well.

*** If the HashMap has enough capacity for the additional items already, reserve is O(1).

Implementations

impl<K: Hash + Eq, V, B: BuildHasher + Default> HashMap<K, V, B>

pub fn new() -> HashMap<K, V, B>

Creates a new HashMap with capacity 0 and the default value for B. Memory will be allocated when the capacity changes.

pub fn with_cap(cap: usize) -> HashMap<K, V, B>

Creates a new HashMap with the provided capacity, allowing insertions without reallocation. The default hasher will be used.

impl<K: Hash + Eq, V, B: BuildHasher> HashMap<K, V, B>

pub fn with_hasher(hasher: B) -> HashMap<K, V, B>

Creates a new HashMap with capacity 0 and the provided hasher.

pub fn with_cap_and_hasher(cap: usize, hasher: B) -> HashMap<K, V, B>

Creates a new HashMap with the provided capacity and hasher.

pub const fn len(&self) -> usize

Returns the length of the HashMap (the number of entries it contains).

pub const fn is_empty(&self) -> bool

Returns true if the HashMap contains no entries.

pub const fn cap(&self) -> usize

Returns the current capacity of the HashMap.

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

Inserts the provided key-value pair into the HashMap, increasing its capacity if required. If the key was already associated with a value, the previous value is returned.

As with the standard library, the key isn’t changed if it already exists.

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

Inserts the provided key-value pair without checking if the HashMap has enough capacity. If the key was already associated with a value, the previous value is returned.

As with the standard library, the key isn’t changed if it already exists.

Safety

It is the responsibility of the caller to ensure that the HashMap has enough capacity to add the provided entry, using methods like reserve or with_cap.

Panics

Panics if the HashMap has a capacity of 0, as it isn’t possible to find a bucket associated with the key.

pub fn get_entry<Q>(&self, key: &Q) -> Option<(&K, &V)>

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Returns the entry for the provided key as a key-value pair or None if there is no entry.

pub fn get<Q>(&self, key: &Q) -> Option<&V>

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Returns a reference to the value associated with the provided key or None if the map contains no values for key.

pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Returns a mutable reference to the value associated with the provided key or None if the map contains no values for key.

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

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Removes the entry associated with key, returning it if it exists.

pub fn remove<Q>(&mut self, key: &Q) -> Option<V>

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Removes the entry associated with key, returning the value if it exists.

pub fn contains<Q>(&self, key: &Q) -> bool

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Returns true if there is a value associated with the provided key.

pub fn reserve(&mut self, extra: usize)

Increases the capacity of the HashMap to ensure that len + extra entries will fit without exceeding the load factor.

pub fn iter(&self) -> Iter<'_, K, V>

Returns an iterator over all key-value pairs in the HashMap, as references.

pub fn into_keys(self) -> IntoKeys<K, V>

Consumes self and returns an iterator over all contained keys.

pub fn keys<'a>(&'a self) -> Keys<'a, K, V>

Returns an iterator over all keys in the HashMap, as references.

pub fn into_values(self) -> IntoValues<K, V>

Consumes self and returns an iterator over all contained values.

pub fn values_mut<'a>(&'a mut self) -> ValuesMut<'a, K, V>

Returns an iterator over all values in the HashMap, as mutable references.

pub fn values<'a>(&'a self) -> Values<'a, K, V>

Returns an iterator over all values in the HashMap, as references.

Trait Implementations

impl<K: Hash + Eq + Debug, V: Debug, B: BuildHasher + Debug> Debug for HashMap<K, V, B>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

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

fn default() -> Self

Returns the “default value” for a type.

impl<K: Hash + Eq + Debug, V: Debug, B: BuildHasher> Display for HashMap<K, V, B>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<K: Hash + Eq, V, B: BuildHasher + Default> Extend<(K, V)> for HashMap<K, V, B>

fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T)

Extends a collection with the contents of an iterator.

fn extend_one(&mut self, item: (K, V))

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements.

impl<K, V, B, I> From<I> for HashMap<K, V, B>

where K: Hash + Eq, B: BuildHasher + Default, I: Iterator<Item = (K, V)> + ExactSizeIterator + TrustedLen,

fn from(value: I) -> Self

Converts to this type from the input type.

impl<K: Hash + Eq, V, B: BuildHasher + Default> FromIterator<(K, V)> for HashMap<K, V, B>

fn from_iter<I: IntoIterator<Item = (K, V)>>(value: I) -> Self

Creates a value from an iterator.

impl<Q, K, V> Index<&Q> for HashMap<K, V>

where Q: Hash + Eq + ?Sized, K: Hash + Eq + Borrow<Q>,

type Output = V

The returned type after indexing.

fn index(&self, key: &Q) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<'a, K: Hash + Eq, V, B: BuildHasher> IntoIterator for &'a HashMap<K, V, B>

type Item = (&'a K, &'a V)

The type of the elements being iterated over.

type IntoIter = Iter<'a, K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K: Hash + Eq, V, B: BuildHasher> IntoIterator for HashMap<K, V, B>

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = IntoIter<K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.