Hash Tables - potatoscript/dsa GitHub Wiki

🧩 What is a Hash Table?

Imagine you have a super-fast address book 📒. You want to quickly look up someone's phone number, but you don't want to search through the whole book! Instead, you use a unique identifier (like a name) to instantly find the number, no matter how big the book is.

A hash table works in a similar way. It stores data using a hash function, which is like a magical formula that converts a key (like a person's name) into an address or location (like a phone number). The hash table then uses that address to store or retrieve the data super quickly.

🖼️ Visual Example:

Imagine you're organizing a group of friends by their names and assigning them a phone number.

Hash Table:
  Key          -> Value
  "Alice"      -> 123-456-7890
  "Bob"        -> 987-654-3210
  "Charlie"    -> 555-555-5555

Now, when you search for "Alice", you don’t have to go through all the names in the list. You can directly go to Alice's spot using her hash (like a special key).

🧠 Why Use a Hash Table?

Super Fast Lookups: You can find things almost instantly, even in huge data sets.
Efficient Insertion and Deletion: You can add or remove data just as quickly.
Key-Value Pairs: It stores data as pairs, where each key is mapped to a value.

In simple terms, hash tables are perfect when you need to access data quickly and don't want to waste time searching through long lists. 🏃‍♀️

🧃 Real-World Analogy

Situation	Hash Table Comparison
🏠 House Directory	The house number is the key, and the address is the value.
🎒 School Locker	The locker number is the key, and the contents are the value.
🏢 Office Desk	The employee name is the key, and the desk location is the value.

💻 C# Code: Simple Hash Table (Dictionary)

In C#, we can use the Dictionary<TKey, TValue> class to implement a hash table.

Define a Hash Table (Dictionary):

Dictionary<string, string> phoneBook = new Dictionary<string, string>();

Add Items (Insert Data):

phoneBook.Add("Alice", "123-456-7890");
phoneBook.Add("Bob", "987-654-3210");
phoneBook.Add("Charlie", "555-555-5555");

Retrieve Data (Look Up):

string phoneNumber = phoneBook["Alice"];
Console.WriteLine("Alice's Phone Number: " + phoneNumber);

Remove Items (Delete Data):

phoneBook.Remove("Bob");

Check if Key Exists:

if (phoneBook.ContainsKey("Charlie"))
{
    Console.WriteLine("Charlie's Phone Number: " + phoneBook["Charlie"]);
}

🧩 Operations in a Hash Table

Operation	Description	Time Complexity
`Add`	Add a key-value pair to the hash table	O(1)
`Retrieve`	Retrieve a value based on its key	O(1)
`Remove`	Remove a key-value pair from the hash table	O(1)
`ContainsKey`	Check if a key exists in the hash table	O(1)

In most cases, these operations are super fast because they are done in constant time, meaning no matter how big the hash table is, the time it takes to do these operations is the same.

🧃 How Does a Hash Table Work?

Hash Function:
A hash function takes the key (like "Alice") and returns a hash code, which is a unique number. This number is then used to find a location in the hash table where the value (like "123-456-7890") is stored.
Collision:
Sometimes, two different keys can produce the same hash code (this is called a collision). To handle this, hash tables use techniques like chaining (storing multiple values in the same location) or open addressing (finding a new location).

🧩 Example with Hashing

Let’s say we have a hash function that gives us the following hash codes for names:

"Alice" → 3
"Bob" → 1
"Charlie" → 5

Now we insert them into a hash table:

Hash Table:
  Index  0  -> 
  Index  1  -> Bob -> "987-654-3210"
  Index  2  -> 
  Index  3  -> Alice -> "123-456-7890"
  Index  4  -> 
  Index  5  -> Charlie -> "555-555-5555"

🚨 Pitfalls to Avoid

❌ Collisions: Two keys might end up with the same hash. Make sure to handle this properly to avoid overwriting data.
❌ Resizing: If your hash table gets too full, you may need to resize it to keep operations fast. This is known as rehashing.

🧠 Time Complexity (Big O)

Insertion (Add): O(1) — Constant time to add a new item.
Lookup (Retrieve): O(1) — Instant access to data.
Deletion (Remove): O(1) — Fast removal.
Search (ContainsKey): O(1) — Super fast search.

📚 Real-World Example: Grocery Store

Let’s say we’re creating a grocery store inventory system using a hash table. Each item (like "Apple") will be the key, and the quantity of the item (like 50) will be the value.

Dictionary<string, int> groceryInventory = new Dictionary<string, int>();

// Add items
groceryInventory.Add("Apple", 50);
groceryInventory.Add("Banana", 30);
groceryInventory.Add("Carrot", 100);

// Lookup the quantity of an item
int appleQuantity = groceryInventory["Apple"];
Console.WriteLine("Apple Quantity: " + appleQuantity);

// Remove an item
groceryInventory.Remove("Banana");

// Check if an item exists
if (groceryInventory.ContainsKey("Carrot"))
{
    Console.WriteLine("Carrot Quantity: " + groceryInventory["Carrot"]);
}

🚨 Hash Table Challenges

🍎 Challenge 1: Simple Phonebook

Create a phonebook system where you add people's names and phone numbers to a hash table. Then, search for someone's phone number by their name.

🧠 Challenge 2: Grocery Inventory

Simulate a grocery store inventory. Add items like "Apple" and "Banana" to a hash table, then find out how many apples you have.

🧹 Challenge 3: Employee Directory

Write a system to store employee names and IDs in a hash table. Check if a particular employee is in the directory by their name.

🧩 Types of Hash Tables

Open Addressing: If a spot in the hash table is taken, find another spot using a probing technique.
Chaining: Use a linked list to store multiple values at the same index in the hash table.

🎓 Summary Time!

✅ Hash Tables store data in key-value pairs for fast access.
✅ You can add, remove, and retrieve data super quickly with a hash table.
✅ The hash function maps a key to an index where the value is stored.
✅ Big O for hash table operations is O(1) — fast, fast, fast!