Listen, I've seen this a dozen times when mentoring junior devs: there's this persistent belief that a Hash Table is just a magic black box where GetHashCode() tells you exactly which slot in an array to put your data. People think that if "Apple".GetHashCode() returns 1,234,567, then the item just goes into index 1,234,567.

Here is why that is fundamentally wrong: your computer doesn't have infinite memory. If you tried to initialize an array with a size large enough to accommodate every possible 32-bit integer returned by GetHashCode(), your program would crash with an OutOfMemoryException before it even started. Furthermore, GetHashCode() can return negative numbers. You can't have an index of -482,910.

The "GetHashCode is the Index" Myth vs. The Modulo Reality

To make a hash table actually work, we have to map that massive hash code into a range that our array can actually handle. This is where the modulo operator (%) comes in. We pick a fixed size for our internal array—say, 100 slots—and we take the remainder of the hash code divided by that size.

int hash = key.GetHashCode();
int index = Math.Abs(hash) % _buckets.Length;

Now, suddenly, no matter how huge the hash code is, our index will always be between 0 and 99. It's a simple trick, but it's the heartbeat of every dictionary implementation you've ever used in C#.

Handling the Inevitable Collision

Once you start modulo-ing your hashes, you run into a new problem: collisions. Two different keys—say, "Apple" and "Banana"—might happen to produce hash codes that, when divided by 100, both result in index 42. If you just overwrite the value at index 42, you've just deleted your "Apple" data. This is the part most people skip when they first try to build this from scratch.

The most robust way to handle this is called "Chaining." Instead of the array holding the value directly, the array holds a list (or a linked list) of entries. If two keys land in the same bucket, we just append the second one to the list. When we want to retrieve the value, we go to the bucket and then loop through that small list, checking the actual Equals() method of the key to find the right match.

Putting the Pieces Together

I like to implement this using a simple KeyValuePair style struct to keep the data tidy. Here is how the internal logic looks when you combine the modulo mapping with the chaining strategy.

public class SimpleHashTable<TKey, TValue>
{
    private class Entry
    {
        public TKey Key { get; set; }
        public TValue Value { get; set; }
    }

    private readonly List<Entry>[] _buckets;

    public SimpleHashTable(int size = 100)
    {
        _buckets = new List<Entry>[size];
    }

    public void Add(TKey key, TValue value)
    {
        int index = Math.Abs(key.GetHashCode()) % _buckets.Length;
        
        if (_buckets[index] == null)
            _buckets[index] = new List<Entry>();

        // Check if key already exists to update it
        var existing = _buckets[index].FirstOrDefault(e => e.Key.Equals(key));
        if (existing != null)
        {
            existing.Value = value;
        }
        else
        {
            _buckets[index].Add(new Entry { Key = key, Value = value });
        }
    }

    public TValue Get(TKey key)
    {
        int index = Math.Abs(key.GetHashCode()) % _buckets.Length;
        var bucket = _buckets[index];

        if (bucket == null) throw new KeyNotFoundException();

        var entry = bucket.FirstOrDefault(e => e.Key.Equals(key));
        if (entry == null) throw new KeyNotFoundException();

        return entry.Value;
    }
}

You'll notice I used Math.Abs(). I mentioned earlier that hashes can be negative, and in C#, the result of a modulo on a negative number is still negative. Without Math.Abs(), your code will throw an IndexOutOfRangeException the moment a negative hash comes along.

📋 Practical Task

Implementing a High-Performance User Session Cache

In a real-world scenario, you might use a hash table to store temporary session tokens for users to avoid hitting a database on every single request. Your task is to extend the basic hash table concept to create a SessionCache class.

Requirements:

• Create a class SessionCache that maps a string (the Session Token) to an int (the User ID).
• Implement an AddSession(string token, int userId) method.
• Implement a GetUserId(string token) method.
• The Twist: Implement a RemoveSession(string token) method. This must correctly find the token within the specific bucket and remove only that entry without clearing the entire bucket (which would delete other users' sessions!).
• Initialize the cache with a fixed size of 50 buckets to ensure you are actively handling collisions during your own testing.