Struct Hmap 

pub struct Hmap<KT, VT> {
    pub table: Vec<Option<(KT, VT)>>,
    pub count: usize,
    pub maxhashes: Vec<usize>,
    pub keylocs: Vec<usize>,
    pub mask: usize,
    pub hashstate: RandomState,
}

Structure of a HashMap, built from scratch, but which uses Rust’s built-in implmenetations of the Hash trait. This is a closed hash table with a linear probing rehash function. The table is a vector of Option. The vector maxhashes tracks the maximum number of hashes and rehashes required for a given hash slot. keylocs tracks locations of possible keys in the vector, which is important for quick iteration over the structure. The size/capacity of the vector is always set to a power of 2: this means instead of % capacity we can calculate & mask, where mask is always capacity-1; The hashstate is necessary for writing the hash function.

Fields

table: Vec<Option<(KT, VT)>>

count: usize

maxhashes: Vec<usize>

keylocs: Vec<usize>

mask: usize

hashstate: RandomState

Implementations

impl<KT: Hash + Eq, VT> Hmap<KT, VT>

pub fn new() -> Self

Creates new Hmap with default capacity 16

pub fn with_capacity(requested_cap: usize) -> Self

Creates new Hmap with requested capacity. The actual capacity will be the nearest power of two that’s greater than or equal to the requested capacity.

pub fn len(&self) -> usize

returns the number of key-value pairs inside the map

pub fn current_capacity(&self) -> usize

returns the current capacity of the map

pub fn get(&self, key: &KT) -> Option<&VT>

retrieves a borrow of the value associated with the given key, if it exists. Look at the source code to understand how it’s defined. Given an opt:Option, opt.as_ref() will return an Option<&T>.

pub fn get_mut(&mut self, key: &KT) -> Option<&mut VT>

retrieves a mutable borrow of the value associated with the given key, if it exists. Look at the source code. Given a mutable opt:Option, opt.as_mut() will return an Option<&mut T>.

pub fn set(&mut self, key: KT, val: VT) -> Option<(KT, VT)>

add or change the value associated with the key, returns the previous key and value, if it existed. Look at the source code. Note that core::mem::swap is used to assign to the vector while taking the previous value out of the vector.

pub fn remove(&mut self, key: &KT) -> Option<(KT, VT)>

removes the key-value pair given the key, returns the pair if it exists. Note that core::mem::swap is used to take the pair out of the vector.

pub fn add(&mut self, key: KT, val: VT)

Internal function called by resize, assumes that key-value pair is new and that table has enough capacity.

pub fn resize(&mut self, upsize: bool) -> bool

Resizes the hashmap by doubling or halfing the capacity.

pub fn hash(&self, key: &KT) -> usize

hash function steals the Hash trait implementations of Rust

pub fn find_new_slot(&mut self, key: &KT) -> (usize, bool)

This function finds the location where a key is found, or where a new key-value pair can be inserted. It returns an index, paired with a boolean indicating whether the key was found at that index.

pub fn find_slot(&self, key: &KT) -> Option<usize>

This function finds the index of the internal vector where a key is located, if it exists.

pub fn iter<'t>(&'t self) -> HmapIter<'t, KT, VT>

Creates iterator over all key-value pairs

Trait Implementations

impl<KT: Hash + Eq, VT> Index<&KT> for Hmap<KT, VT>

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

Provides ability to use syntax such as map[&key]. Operation will panic if key does not exist

type Output = VT

The returned type after indexing.

impl<KT: Hash + Eq, VT> Index<KT> for Hmap<KT, VT>

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

Provides ability to use syntax such as map[key]. Operation will panic if key does not exist.

type Output = VT

The returned type after indexing.

impl<KT: Hash + Eq, VT: Default> IndexMut<KT> for Hmap<KT, VT>

fn index_mut(&mut self, key: KT) -> &mut Self::Output

Provides ability to use syntax such as map[key] = val. This function will insert a new value into the table if necessary and assumes that the value type VT implements the Default trait.