Class CuckooHashTable<TKey, TValue>

Namespace

AlgorithmsSW.HashTable

Assembly

AlgorithmsSW.dll

Represents a Cuckoo hash table implementation that stores key-value pairs.

public class CuckooHashTable<TKey, TValue> : ISymbolTable<TKey, TValue>, IReadOnlySymbolTable<TKey, TValue>

Type Parameters

TKey

The type of keys in the hash table.

TValue

The type of values in the hash table.

Inheritance

object

CuckooHashTable<TKey, TValue>

Implements

ISymbolTable<TKey, TValue>

IReadOnlySymbolTable<TKey, TValue>

Inherited Members

object.Equals(object)

object.Equals(object, object)

object.GetHashCode()

object.GetType()

object.MemberwiseClone()

object.ReferenceEquals(object, object)

object.ToString()

Extension Methods

Applications.ApplyInterpolationRule<T, TBuffer>(TBuffer, Func<T, T, T>)

Applications.ApplyInterpolationRule<T, TBuffer>(TBuffer, Func<T, T, T>, int)

Applications.Interpolate<T, TBuffer>(TBuffer, Func<T, T, T>, int)

Applications.Substitute<T, TBuffer>(TBuffer, (T input, T[] output)[])

Comparable.ToComparable<T>(T, IComparer<T>)

Formatter.AsText<T>(T?)

Formatter.Describe<TLabel, TDescription>(TLabel, TDescription, string)

Formatter.Log<T>(T)

Formatter.Pretty<T>(T, params int[])

SymbolTableAlgorithms.CountKeysWithValue<TKey, TValue>(IReadOnlySymbolTable<TKey, TValue>, IComparer<TValue>)

SymbolTableAlgorithms.Invert<TKey, TValue>(IReadOnlySymbolTable<TKey, TValue>, IComparer<TValue>)

Remarks

Cuckoo hashing allows for constant time complexity in the average case for search, insert, and delete operations. It uses two hash functions and two tables to resolve collisions. This implementation provides methods for adding, removing, and checking the presence of keys.

Constructors

CuckooHashTable(IComparer<TKey>)

Initializes a new instance of the CuckooHashTable<TKey, TValue> class with the specified comparer.

public CuckooHashTable(IComparer<TKey> comparer)

Parameters

comparer IComparer<TKey>

The IComparer<T> to use for comparing keys.

CuckooHashTable(int, IComparer<TKey>)

Initializes a new instance of the CuckooHashTable<TKey, TValue> class with the specified table size and comparer.

public CuckooHashTable(int tableSize, IComparer<TKey> comparer)

Parameters

tableSize int

The initial size of the table.

comparer IComparer<TKey>

The IComparer<T> to use for comparing keys.

Properties

Comparer

public IComparer<TKey> Comparer { get; }

Property Value

IComparer<TKey>

Count

Gets the number of key/value pairs contained in the symbol table.

public int Count { get; }

Property Value

int

Keys

Gets an IEnumerable<T> containing the keys of the symbol table.

public IEnumerable<TKey> Keys { get; }

Property Value

IEnumerable<TKey>

Methods

Add(TKey, TValue)

Adds the specified key and value to the symbol table.

public void Add(TKey key, TValue value)

Parameters

key TKey

The key of the element to add.

value TValue

The value of the element to add.

ContainsKey(TKey)

Determines whether the symbol table contains a specific key.

public bool ContainsKey(TKey key)

Parameters

key TKey

The key to locate in the symbol table.

Returns

bool

true if the symbol table contains an element with the specified key; otherwise, false.

RemoveKey(TKey)

Removes the element with the specified key from the symbol table.

public void RemoveKey(TKey key)

Parameters

key TKey

The key of the element to remove.

TryGetIndex(TKey, out ParallelArrays<TKey?, TValue?>?, out int)

Tries to get the index and corresponding table where the specified key is stored.

public bool TryGetIndex(TKey key, out ParallelArrays<TKey?, TValue?>? table, out int index)

Parameters

key TKey

The key to locate in the cuckoo hash table.

table ParallelArrays<TKey, TValue>

When this method returns, contains the ParallelArrays<TKey, TValue> table in which the key is potentially stored, if the key is found; otherwise, null. This parameter is passed uninitialized.

index int

When this method returns, contains the index at which the key is potentially stored in the table, if the key is found; otherwise, the default value for the type of the index parameter. This parameter is passed uninitialized.

Returns

bool

true if the cuckoo hash table contains an element with the specified key; otherwise, false.

Remarks

This method is a key part of the cuckoo hashing algorithm, which involves using two hash functions and two tables. It attempts to find the specified key by checking both tables with respective hash functions. If the key is found, the method returns true, and outputs the table and index where the key is stored. If the key is not found, the method returns false, and the output parameters are set to their default values.

TryGetValue(TKey, out TValue?)

Tries to get the value associated with the specified key from the symbol table.

public bool TryGetValue(TKey key, out TValue? value)

Parameters

key TKey

The key of the value to get.

value TValue

When this method returns, contains the value associated with the specified key, if the key is found; otherwise, the default value for the type of the value parameter. This parameter is passed uninitialized.

Returns

bool

true if the symbol table contains an element with the specified key; otherwise, false.