A .NET implementation of Krapivin's elastic hashing hash table with MurmurHash3 from MurmurHash.Net.
$ dotnet add package KrapivinHashTableA high-performance, segmented hash table implementation for .NET with quadratic probing and efficient collision resolution.
Install-Package KrapivinHashTable
dotnet add package KrapivinHashTable
// Create a new hash table with default settings
var hashTable = new KrapivinHashTable<string, int>();
// Insert key-value pairs
hashTable.Insert("one", 1);
hashTable.Insert("two", 2);
hashTable.Insert("three", 3);
// Retrieve values
int value;
if (hashTable.TryGet("two", out value))
{
Console.WriteLine($"Found: {value}"); // Outputs: Found: 2
}
// Alternative retrieval method
int anotherValue = hashTable.Get("three"); // Returns 3
int notFound = hashTable.Get("four"); // Returns default(int) which is 0
// Delete a key-value pair
bool deleted = hashTable.Delete("one"); // Returns true
The KrapivinHashTable constructor accepts several parameters to customize the table's behavior:
public KrapivinHashTable(
int initialCapacity = 1024, // Total number of slots
int segmentSize = 32, // Size of each segment
IEqualityComparer<TKey>? comparer = null // Custom equality comparer
)
KrapivinHashTable uses a segmented approach where the hash table is divided into segments of fixed size. When searching for a key, the hash function first identifies the appropriate segment, and then the search is initially confined to that segment. This improves cache locality and performance.
Collisions are resolved using quadratic probing with the formula (n² + n)/2, which provides a good distribution and helps avoid clustering. When a segment becomes full, the search extends beyond the segment using the same quadratic probing sequence.
The library uses MurmurHash3, a high-quality non-cryptographic hash function that provides excellent distribution with minimal collisions.
MIT License
Contributions are welcome! Please feel free to submit a Pull Request.
git checkout -b feature/amazing-feature)git commit -m 'Add some amazing feature')git push origin feature/amazing-feature)