Hash Tables 

Definition

A Hash Table (or Hash Map) is a data structure that stores data in “key-value” pairs. It is designed to find specific items instantly, without searching through the entire list.

How it Works

1. The Key: You have a piece of data you want to store (e.g., a username “Alice”).
2. The Hash Function: This is a mathematical formula that converts the key (“Alice”) into a specific number (an index), like 42.
3. Storage: The value associated with “Alice” is stored at index 42 in an array.
4. Collisions: Sometimes, two different keys might generate the same index number. Hash tables handle this using techniques like “Chaining” (storing a list of items at that index).

Real-World Analogy:

Think of a public library. If you want a specific book, you don’t check every shelf. You look up the “Call Number” in the computer (the Hash Function). That number tells you exactly which shelf and row the book is on (the Index), so you can go straight there.

Example

Task: Store and retrieve phone numbers.

• Insert: Key=”John”, Value=555-0100. Hash(“John”) $\rightarrow$ Index 3. Store at Index 3.
• Search: Get number for “John”. Hash(“John”) $\rightarrow$ Index 3. Retrieve value.

Code Example (Python)

Python

# Python Dictionaries are Hash Tables implementation
phone_book = {}

# Insert
phone_book[“John”] = “555-0100”
phone_book[“Alice”] = “555-0101”

# Search / Access
print(“John’s Number:”, phone_book[“John”]) # Output: 555-0100

# Check existence
if “Bob” in phone_book:
    print(“Bob is here”)
else:
    print(“Bob not found”) # Output: Bob not found

Complexity Analysis

• Time Complexity:

• Average Case: O(1) (Instant access)
• Worst Case: O(n) (If many collisions occur—rare with good implementation)

• Space Complexity: O(n)

Use Cases

• Databases: Indexing data for fast retrieval.
• Caching: Storing recent web requests to load pages faster.
• Counting Frequencies: Counting how many times words appear in a text.