Struct HashMap

pub struct HashMap<K, V> {
    pub data: Vec<Option<Entry<K, V>>>,
    pub ctrl: Vec<u8>,
    /* private fields */
}

Fields

data: Vec<Option<Entry<K, V>>>

ctrl: Vec<u8>

Implementations

impl<K, V> HashMap<K, V>

where K: Debug + Eq + Hash + PartialEq, V: Debug,

pub fn new() -> Self

Constructor for an empty map with a default capacity of 2.

pub fn new_with_capacity(size: usize) -> Self

Constructor for an empty map with a given capacity.

pub fn len(&self) -> usize

Returns the number of active entries in the map in O(1) time.

pub fn occupied(&self) -> usize

Returns the total number of entries in the map (active + deleted entries) in O(n) time.

pub fn deleted(&self) -> usize

Returns the total number of deleted entries in the map in O(n) time.

pub fn capacity(&self) -> usize

Returns the total number of available slots in the map in O(1) time.

NOTE: The load factor is the quotient of len() / capacity().

pub fn is_empty(&self) -> bool

Returns true if the map is either empty or contains only empty slots and deleted entries.

pub fn contents(&self)

Pretty-prints the map’s contents.

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

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

Takes a key as a reference and returns a Boolean indicating whether its in the map. The expected temporal complexity is O(1), as the map maintains a laod factor of <=.5.

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

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

Returns a reference to the value associated with a key, if the key exists.

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

Adds entry (k, v), overwriting any value v associated with an existing key k, returns old value. If a new addition increases the map’s load factor above the designated threshhold of 0.5 the map resizes.

pub fn try_put(&mut self, key: K, value: V)

pub fn mut_val_or<F>(&mut self, key: K, f: F, default: V)

where F: FnOnce(&mut V), K: Default,

Takes a key, a closure, and a default value. If the key is in the map, applies the closure to the corresponding entry’s value. If the key is not in the map, creates a new entry with the provided value.

Example:

use dsa_rust::associative::probing_hash_table::HashMap;
let mut count: HashMap<char, u32> = HashMap::new();
let word: &str = "Hello";
for k in word.chars() {
    count.mut_val_or(k, |x| *x += 1, 1);
}

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

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

Removes and returns an entry from the map for a given key, if it exists in the map.

pub fn rehash(self) -> Self

Consumes self and returns a new map of the same size, but without any tombstones. Works like a cleanup operation in O(capacity) time because into_iter checks all positions.

pub fn shrink_to_fit(self) -> Self

Rebuilds the map to eliminate accumulated tombstones thereby reducing spatial bloat. This operation runs in O(n) time and is intended for long-lived maps that have undergone many deletions.

The operation consumes the existing map and returns a new HashMap with the same live entries.

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

Returns an iterator over borrowed values. The resulting values appear in random order.

Example use:

use dsa_rust::associative::probing_hash_table::HashMap;
let mut count: HashMap<char, u8> = HashMap::new();
let mut v = Vec::new();
for e in count.iter() {
    v.push(*e.0);
}

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

Returns an iterator over borrowed keys only. The keys appear in random order.

Example use:

for e in map.keys() {
    println!("{e}");
}

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

Returns an iterator over borrowed values only. The values appear in random order.

Example use:

for e in map.values() {
    println!("{e}");
}

Trait Implementations

impl<K: Debug, V: Debug> Debug for HashMap<K, V>

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

Formats the value using the given formatter.

impl<K, V> Default for HashMap<K, V>

where K: Debug + Default + Eq + Hash + PartialEq, V: Default + PartialEq + Debug,

fn default() -> Self

Returns the “default value” for a type.

impl<K, V> IntoIterator for HashMap<K, V>

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.