Hashing in C#: Concepts, Hash Functions, HashTable, Dictionary, and Custom HashMap

Hashing is the secret sauce behind fast lookups. Whether you’re building a compiler, a caching system, or a URL shortener—hashing is your friend. In this article, we’ll go under the hood of hashing in C# with real-world examples and step-by-step custom implementation.

What is Hashing?

Hashing is a technique that maps data (like a string or number) to a fixed-size value using a hash function. This value is called a hash code or hash key, and it’s used to index into a data structure (like an array).

Real-World Use Cases

• Password storage (with secure hashes)
• Caching web responses
• Detecting duplicate files (hash of contents)
• Hash-based data structures (Dictionary, HashSet, HashTable)

Built-In Hashing in C#

1. GetHashCode()

Every object in C# has a GetHashCode() method. You can override it in your custom classes:

public class User
{
    public string Name;
    public int Age;

    public override int GetHashCode()
    {
        return HashCode.Combine(Name, Age);
    }
}

2. Using Dictionary (HashMap)

Dictionary<string, int> dict = new();
dict["apple"] = 1;
dict["banana"] = 2;
Console.WriteLine(dict["apple"]); // Output: 1

3. HashSet (For Uniqueness)

HashSet<string> set = new();
set.Add("apple");
set.Add("apple"); // won’t be added again

Custom HashMap in C#

Let’s build a simple HashMap from scratch using chaining to handle collisions:

public class HashNode
{
    public string Key;
    public int Value;
    public HashNode Next;

    public HashNode(string key, int value)
    {
        Key = key;
        Value = value;
        Next = null;
    }
}

public class CustomHashMap
{
    private int size = 10;
    private HashNode[] buckets;

    public CustomHashMap() => buckets = new HashNode[size];

    private int GetIndex(string key)
    {
        int hash = key.GetHashCode();
        return Math.Abs(hash % size);
    }

    public void Put(string key, int value)
    {
        int index = GetIndex(key);
        HashNode head = buckets[index];

        while (head != null)
        {
            if (head.Key == key)
            {
                head.Value = value;
                return;
            }
            head = head.Next;
        }

        HashNode newNode = new(key, value) { Next = buckets[index] };
        buckets[index] = newNode;
    }

    public int? Get(string key)
    {
        int index = GetIndex(key);
        HashNode head = buckets[index];

        while (head != null)
        {
            if (head.Key == key) return head.Value;
            head = head.Next;
        }

        return null;
    }
}

Collision Handling Techniques

• Chaining: Store multiple entries at the same index using a linked list
• Open Addressing: Find another empty slot (Linear/Quadratic Probing)

Practice Problems

1. Design a phone book with string -> number mapping
2. Find first non-repeating character in a string using a hash map
3. Group anagrams using hashing
4. Count number of distinct elements in an array
5. Implement an LRU Cache using Dictionary + Linked List

Hashing is foundational for performance. It powers everything from database indexing to spell checkers. Master it, and you level up as a problem solver.