Build a hash table in C#

How it works and why

A hash table needs an array of buckets. In separate chaining, each bucket holds zero or more entries. Each entry stores both the key and its value. During Put, calculate the index, check if that key already exists, then update or append the entry. During TryGetValue and Remove, inspect only that candidate bucket.

Our downloadable EducationalHashMap<TKey,TValue> implements Put, TryGetValue, Remove, Count and automatic resizing. It accepts an IEqualityComparer<TKey>, masks negative hash codes, and rehashes entries when a projected load threshold is crossed. It is deliberately simpler than the production .NET Dictionary. Read the full source and trace every operation.

C# and C++ examples

C#

C# | Example.cs

// EducationalHashMap.cs must be in the same .NET project.
var scores = new EducationalHashMap<string, int>(5);
scores.Put("Ada", 10);
scores.Put("Grace", 20);
scores.Put("Ada", 15); // replace by equal key, not duplicate
if (scores.TryGetValue("Ada", out int value))
    Console.WriteLine(value); // 15
Console.WriteLine(scores.Remove("Grace")); // True
Console.WriteLine(scores.Count); // 1

C++

C++ | Example.cpp

#include <unordered_map>
#include <string>
#include <iostream>

// C++ standard-library map, NOT a port of EducationalHashMap.
std::unordered_map<std::string, int> scores;
scores["Ada"] = 10;
scores["Grace"] = 20;
scores["Ada"] = 15; // update an existing key
if (auto it = scores.find("Ada"); it != scores.end())
    std::cout << it->second << '\n'; // 15
std::cout << scores.erase("Grace") << '\n'; // 1
std::cout << scores.size() << '\n'; // 1

C++ distinction: The C++ tab uses the standard std::unordered_map, not the downloadable custom chaining implementation. To study internal bucket handling, read the C# source and compare the concepts rather than assuming equivalent internal implementations.

When and why to use it

Trace: Identify the bucket using the comparer hash; compare keys in that bucket; check load factor before appending; if resizing, allocate more buckets and reassign entries using the new modulus. Average operation cost is expected O(1) under suitable hashing; worst case O(n) is possible. Try: Change the initial bucket count and verify that lookups still work after resizing.

Download the complete EducationalHashMap.cs

This class is educational code, not a replacement for Dictionary<TKey,TValue> in production systems.

Interactive hash table · HashSet and Dictionary