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 via separate chaining, where each bucket holds a linked list of entries that hash to the same index.

Time complexity:
Insert: O(1) (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 hash to the same bucket, degrading every operation to a linear scan of that bucket.

Constructors¶

ctor¶

1

public p HashTable.ctor(unsigned long bucketCount = 100l)

Construct an empty hash table with the given number of buckets

Parameters

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 Optional. If the key is not found, return an empty optional.

Parameters

Returns: Result<V> — Optional, containing the value associated with the key or empty 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 inline p HashTable.clear()

Clear the hash table, removing all key-value pairs.

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

Returns: bool — true or false

next¶

1

public inline p HashTableIterator.next()

Moves the cursor to the next key/value pair

Functions¶

ctor¶

1

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

Construct a hash entry as a copy of another hash entry

Parameters