Hash Table — Explained with Examples

A hash table is a key-value data structure using a hash function to compute indices, enabling O(1) average-time insertions, deletions, and lookups.

Hash tables (hash maps, dictionaries) map keys to values using a hash function that converts a key into an array index. Collisions — when two keys hash to the same index — are handled via chaining (linked list per bucket) or open addressing (probing for the next empty slot). A good hash function distributes keys uniformly.

Think of a hash table like a library with a catalog system. Instead of searching every shelf (O(n)), you look up the book’s subject code in the catalog (hash function), which tells you exactly which aisle and shelf (index). Occasionally, two books have the same code, so you check a small list at that location.

Most programming languages provide built-in hash tables: {} objects and Map in JavaScript, dict in Python, HashMap in Java, and {} in Ruby. These underpin databases, caches, symbol tables, and language runtimes.

# Python dictionary (hash table)
phonebook = {}
phonebook["Alice"] = "555-1234"
phonebook["Bob"] = "555-5678"

# O(1) lookup
print(phonebook["Alice"])  # 555-1234

# Handling collisions
# Two keys may hash to same slot; linked list stores both

# Custom hash function (simplified)
def simple_hash(key, table_size):
    return sum(ord(c) for c in str(key)) % table_size

Hash tables excel at membership testing, deduplication, caching, and counting frequencies. They trade memory for speed — storing extra data to enable fast access.

Big O, Binary Search Tree, Trie, Heap

BST vs Hash Table