Hash Table¶

1

import "std/data/hash-table";

HashTable<K, V> struct¶

Implements: IIterable<Pair<K, V>>

A hash table in Spice is a commonly used data structure, which stores key-value pairs and allows fast access to a value by its key. Collisions are resolved by open addressing with linear probing over a contiguous slot array, and the table grows once it reaches its maximum load factor.

Time complexity:
Insert: O(1) (amortized average case), O(n) (worst case)
Delete: O(1) (average case), O(n) (worst case)
Lookup: O(1) (average case), O(n) (worst case)

The average case assumes a good hash distribution. In the worst case, all keys probe the same chain of slots, degrading every operation to a linear scan.

The entries themselves live in their own allocations and are never relocated, only the slot array is rebuilt when the table grows. A reference obtained from get() therefore stays valid until that particular key is removed, the table is cleared or the table is destructed - inserting other keys never invalidates it.

Constructors¶

ctor¶

1

public p HashTable.ctor(unsigned long initialCapacity = 0l)

Construct an empty hash table with room for the given number of entries. Passing 0 keeps the hash table in an unallocated state; the slot array is materialized lazily on the first insertion.

Parameters

ctor¶

1

public p HashTable.ctor(const HashTable<K, V>& original)

Construct a hash table as a deep copy of another hash table

Parameters

dtor¶

1

public p HashTable.dtor()

Destructs the hash table, destructing all entries and freeing the slot array

Methods¶

upsert¶

1

public p HashTable.upsert(const K& key, const V& value)

Insert a key-value pair into the hash table. If the key already exists, the value is updated.

Parameters

get¶

1

public f<V&> HashTable.get(const K& key)

Retrieve the value associated with the given key. If the key is not found, panic.

Parameters

Returns: V& — The value associated with the key

getSafe¶

1

public f<Result<V>> HashTable.getSafe(const K& key)

Retrieve the value associated with the given key as Result. If the key is not found, return an error.

Parameters

Returns: Result<V> — Result, containing the value associated with the key or an error if the key is not found

remove¶

1

public p HashTable.remove(const K& key)

Remove the key-value pair associated with the given key. If the key is not found, do nothing.

Parameters

contains¶

1

public f<bool> HashTable.contains(const K& key)

Check if the hash table contains the given key.

Parameters

Returns: bool — True if the key is found, false otherwise

getSize¶

1

public inline f<unsigned long> HashTable.getSize()

Get the size of the hash table.

Returns: unsigned long — The number of key-value pairs in the hash table

isEmpty¶

1

public inline f<bool> HashTable.isEmpty()

Checks if the hash table is empty.

Returns: bool — True if empty, false otherwise.

clear¶

1

public p HashTable.clear()

Clear the hash table, removing all key-value pairs. The slot array is kept for reuse.

getIterator¶

1

public f<HashTableIterator<K, V>> HashTable.getIterator()

Retrieve a forward iterator for the hash table

Returns: HashTableIterator<K, V>

HashTableIterator<K, V> struct¶

Implements: IIterator<Pair<const K&, V&>>

Iterator to iterate over a hash table data structure

Constructors¶

ctor¶

1

public p HashTableIterator.ctor<K, V>(HashTable<K, V>& hashTable)

Construct a hash table iterator over the given hash table

Parameters

Methods¶

get¶

1

public inline f<Pair<const K&, V&>&> HashTableIterator.get()

Returns the current key-value pair of the hash table

Returns: Pair<const K&, V&>& — Current key/value pair

getIdx¶

1

public inline f<Pair<unsigned long, Pair<const K&, V&>&>> HashTableIterator.getIdx()

Returns the current index and the current item of the hash table

Returns: Pair<unsigned long, Pair<const K&, V&>&> — Pair of current index and current key/value pair

isValid¶

1

public inline f<bool> HashTableIterator.isValid()

Check if the iterator is valid

The iterator maintains the invariant that its slot index either addresses an occupied slot or has run past the last one, so validity is a single comparison.

Returns: bool — true or false

next¶

1

public inline p HashTableIterator.next()

Moves the cursor to the next key/value pair

Operators¶

operator=¶

1

public p operator=<K, V>(HashTable<K, V>& this, const HashTable<K, V>& newValue)

Copy-assign the contents of another hash table into this one

Parameters