Hash Tables & Dictionaries

A Hash Table is a data structure that maps "Keys" to "Values." It is the most powerful tool for performance because it provides O(1) average search time. In .NET, this is implemented as Dictionary<K, V>.

1. The Hashing Process

When you add a key (e.g., "Sandeep"), the table runs a Hash Function that converts the string into an integer (e.g., index 4). It then stores the value at that specific array index. This is why lookup is instant—you don't search; you jump directly to the index.

2. Handling Collisions

What if two different strings (e.g., "Sandeep" and "Admin") produce the same hash index? This is a Collision.

• Chaining: Each array index contains a small Linked List. If multiple keys hit the same index, they are added to the list. (.NET uses this).
• Open Addressing: If index 4 is full, find the next empty spot (index 5) and put it there.

4. Interview Mastery

Q: "Why should you NEVER use a mutable object (like a List) as a Dictionary Key?"

Architect Answer: "Because if the object changes while it is in the dictionary, its **Hash Code** will also change. When you try to look up the key later, the dictionary will look at the *new* hash index, find nothing (or someone else), and tell you the key doesn't exist. You have effectively 'lost' the data in memory. ALWAYS use **Immutable** types like Strings or Records as dictionary keys."