Hash Tables

Hash Tables (Hash Maps)

If you want to find a specific item in an Array or a Linked List, you normally have to search through it one by one (O(n) time).

What if there was a data structure that magically knew exactly where your data was stored instantly? That is exactly what a Hash Table does, and it is arguably the most important data structure used in modern software engineering.

1. What is a Hash Table?

A Hash Table (also called a Hash Map or Dictionary) stores information using a Key and a Value.

Instead of asking the computer for "the item at Index 2," you ask the computer for "the item associated with the key 'Alice'."

Real-Life Analogy

Think of a Coat Check at a fancy restaurant.

1. You hand the attendant your coat (the Value).
2. The attendant hangs it up and gives you a numbered ticket (the Key).
3. When you want your coat back, you don't search through 500 coats. You just hand the attendant your ticket, and they instantly grab your exact coat!

2. The Magic: The Hash Function

How does the Hash Table instantly know where "Alice" is stored without searching? It uses a mathematical algorithm called a Hash Function.

Under the hood, a Hash Table is actually just a standard Array. But instead of you picking the index, the Hash Function picks it for you!

1. You provide a Key (like "Alice").
2. The Hash Function converts the text "Alice" into a seemingly random number (like 4291).
3. It uses a modulo operator (%) to shrink that number to fit inside the Array (e.g., Index 0).
4. It stores the data at Index 0.

When you want to find "Alice" later, the Hash Function runs the exact same math, spits out Index 0 again, and grabs your data instantly!

Hash Table: The Hash Function translates your Key into an exact memory Array Index.

3. Dealing with Collisions

What happens if the Hash Function calculates the exact same Index for two completely different Keys? This is called a Collision.

For example, both "Alice" and "Dan" might mathematically hash to Index 1.

There are two common ways to handle this:

1. Chaining: Instead of storing just one value at Index 1, the Hash Table stores a Linked List at Index 1. Both "Alice" and "Dan" are added to the chain.
2. Open Addressing: If Index 1 is full, the Hash Table simply looks for the very next empty slot (like Index 2) and puts "Dan" there instead.

4. Time Complexity

Because the Hash Function calculates the exact memory address instantly via math, Hash Tables are incredibly fast.

• Insert: O(1) Constant Time.
• Lookup / Search: O(1) Constant Time.
• Delete: O(1) Constant Time.

The Worst Case: If you have a terrible Hash Function that puts every single item into the exact same Index, you get a massive Collision chain. Your O(1) Hash Table degrades into an O(n) Linked List. Fortunately, modern programming languages have highly optimized hash functions to prevent this!

5. Code Example (Python Dictionaries)

You don't usually have to build Hash Tables from scratch. Almost every programming language has them built-in!

In Python, Hash Tables are called Dictionaries. In JavaScript, they are called Objects or Maps. In Java, they are HashMaps.

# Create a Hash Table (Dictionary in Python)
phone_book = {}
# 1. INSERT (O(1) time)
phone_book["Alice"] = "555-0199"
phone_book["Bob"] = "555-0288"
phone_book["Charlie"] = "555-0377"
print("Phone Book:", phone_book)
# 2. LOOKUP / SEARCH (O(1) time)
# No loop required! We just ask for "Bob" directly.
print("Bob's Number:", phone_book["Bob"])
# 3. DELETE (O(1) time)
del phone_book["Alice"]
print("After deleting Alice:", phone_book)