Struct MediumSizeHashTable

pub struct MediumSizeHashTable<Key, Value, Hash: FastHash> { /* private fields */ }

Implementations

impl<Key, Value, Hash: FastHash + Default> MediumSizeHashTable<Key, Value, Hash>

where Key: Copy + Default + PartialEq + TryInto<u32>, Value: Copy + Default,

pub fn new() -> Self

Creates a new hash table with capacity for MAX_ELEMENTS items.

Implementation Details

• Initializes empty table with default hash cells
• Creates tabulation hasher for index computation
• Sets initial timestamp to 0

pub fn get_mut(&mut self, key: Key) -> &mut Value

Gets or creates a mutable reference to a hash cell for the given key.

Algorithm

1. Computes initial position using tabulation hash
2. Uses linear probing to handle collisions
3. Updates timestamp and key on access

Arguments

• key - identifier

Returns

Mutable reference to the hash cell

Panics

Panics if Key cannot be converted to u32

pub fn insert(&mut self, key: Key, value: Value)

Inserts a value into the hash table at the specified key.

This is a convenience wrapper around get_mut() that handles the assignment. It uses linear probing for collision resolution and automatically handles timestamp-based cell invalidation.

Arguments

• key - The key to insert the value at
• value - The value to insert

Examples

Basic insertion:

use toolbox_rs::medium_size_hash_table::MediumSizeHashTable;
use toolbox_rs::tabulation_hash::TabulationHash;

let mut table = MediumSizeHashTable::<u32, u32, TabulationHash>::new();
table.insert(1, 42);
assert_eq!(table.peek_value(1), Some(&42));

Updating existing values:

use toolbox_rs::medium_size_hash_table::MediumSizeHashTable;
use toolbox_rs::tabulation_hash::TabulationHash;

let mut table = MediumSizeHashTable::<u32, u32, TabulationHash>::new();
table.insert(1, 42);
table.insert(1, 43);  // Updates the existing value
assert_eq!(table.peek_value(1), Some(&43));

Multiple insertions:

use toolbox_rs::medium_size_hash_table::MediumSizeHashTable;
use toolbox_rs::tabulation_hash::TabulationHash;

let mut table = MediumSizeHashTable::<u32, u32, TabulationHash>::new();
table.insert(1, 10);
table.insert(2, 20);
table.insert(3, 30);

assert_eq!(table.peek_value(1), Some(&10));
assert_eq!(table.peek_value(2), Some(&20));
assert_eq!(table.peek_value(3), Some(&30));

Panics

Panics if Key cannot be converted to u32

pub fn peek_value(&self, key: Key) -> Option<&Value>

Looks up the value associated with a key without modifying the timestamp.

Arguments

• key - key identifier to look up

Returns

• Some(value) - If the key exists in the current timestamp
• None - If the key doesn’t exist or was cleared

Panics

Panics if Key cannot be converted to u32

pub fn contains_key(&self, key: Key) -> bool

Checks if a key exists in the hash table.

This method performs a read-only lookup that doesn’t modify the table’s state. It uses the same linear probing strategy as other operations but doesn’t update timestamps or modify any values.

Arguments

• key - The key to check for existence

Returns

• true if the key exists in the current timestamp
• false if the key doesn’t exist or was cleared

Examples

Basic usage:

use toolbox_rs::medium_size_hash_table::MediumSizeHashTable;
use toolbox_rs::tabulation_hash::TabulationHash;

let mut table = MediumSizeHashTable::<u32, u32, TabulationHash>::new();
assert!(!table.contains_key(1), "Empty table should not contain any keys");

*table.get_mut(1) = 42;
assert!(table.contains_key(1), "Key should exist after insertion");

Behavior after clear:

use toolbox_rs::medium_size_hash_table::MediumSizeHashTable;
use toolbox_rs::tabulation_hash::TabulationHash;

let mut table = MediumSizeHashTable::<u32, u32, TabulationHash>::new();
*table.get_mut(1) = 42;
table.clear();
assert!(!table.contains_key(1), "Key should not exist after clear");

Panics

Panics if Key cannot be converted to u32

pub fn clear(&mut self)

Clears the hash table by incrementing the timestamp.

If the timestamp would overflow, reallocates the table instead. This provides an efficient O(1) clear operation in most cases.

pub fn len(&self) -> usize

Returns the number of elements currently in the hash table.

This method returns the actual number of key-value pairs stored in the table, not the capacity. The count is maintained efficiently during insertions and clear operations.

Examples

use toolbox_rs::medium_size_hash_table::MediumSizeHashTable;
use toolbox_rs::tabulation_hash::TabulationHash;

let mut table = MediumSizeHashTable::<u32, u32, TabulationHash>::new();
assert_eq!(table.len(), 0);

table.insert(1, 42);
assert_eq!(table.len(), 1);

// Update existing key doesn't change length
table.insert(1, 43);
assert_eq!(table.len(), 1);

table.insert(2, 100);
assert_eq!(table.len(), 2);

table.clear();
assert_eq!(table.len(), 0);

pub fn is_empty(&self) -> bool

Returns true if the hash table contains no elements.

Examples

use toolbox_rs::medium_size_hash_table::MediumSizeHashTable;
use toolbox_rs::tabulation_hash::TabulationHash;

let mut table = MediumSizeHashTable::<u32, u32, TabulationHash>::new();
assert!(table.is_empty());

table.insert(1, 42);
assert!(!table.is_empty());

table.clear();
assert!(table.is_empty());

pub fn capacity(&self) -> usize

Returns the total capacity of the hash table.

The capacity is fixed at MAX_ELEMENTS (65536) and represents the maximum number of elements that can be stored in the table. This is different from len() which returns the current number of elements.

Examples

use toolbox_rs::medium_size_hash_table::MediumSizeHashTable;
use toolbox_rs::tabulation_hash::TabulationHash;

let table = MediumSizeHashTable::<u32, u32, TabulationHash>::new();
assert_eq!(table.capacity(), 65536);
assert!(table.capacity() >= table.len());

Trait Implementations

impl<Key: Debug, Value: Debug, Hash: Debug + FastHash> Debug for MediumSizeHashTable<Key, Value, Hash>

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

Formats the value using the given formatter.

impl<Key, Value, Hash: FastHash + Default> Default for MediumSizeHashTable<Key, Value, Hash>

where Key: Copy + Default + PartialEq + TryInto<u32>, Value: Copy + Default,

fn default() -> Self

Returns the “default value” for a type.