I've implemented a hash table (also called a hash map) as practice to gain insights on how the std::collections::HashMap
might work under the hood.
I'm going to resolve collisions using linear probing, a form of open addressing where we search (probe) adjacent tables in memory until we find one that's free (when inserting) or contains the key. It's worth noting that linear probing degrades in performance considerably with a high enough load factor, so once we hit 0.75 (about 75% full) we resize the vector.
new()
: Creates a new hash tablelen()
: Returns the number of occupied entriesinsert(key: Key)
: Inserts anEntry
into the hash tableget(key: Key)
: Returns anOption<Entry>
for that keyget_mut(key: Key)
: Returns anOption<&mut Entry>
mutable reference for that keyremove()
: Removes an item from the hash table