Hash Table: How to Find Data Instantly Using a Key?

01 What is a Hash Table?

In formal computer science terms:

A Hash Table is organized around two fundamental components:

02 Real-World Example: Student Roll Directory

Consider a classroom directory mapping roll numbers to student names:

If asked: "Who is roll 103?", an unsorted linear scan checks 101, then 102, before reaching Nadia. In contrast, a Hash Table passes 103 into a mathematical equation that instantly evaluates the target memory slot:

03 What is a Hash Function?

The entire power of a Hash Table hinges upon the Hash Function.

Suppose our hash table has a capacity of 10 slots. A simple modulo arithmetic hash function looks like:

04 How Does a Hash Table Look Internally?

Under the hood, a Hash Table is anchored by a contiguous array where each slot is known as a Bucket:

Index    Bucket Content
───────────────────────────────
[ 0 ] →  (Empty)
[ 1 ] →  (Empty)
[ 2 ] →  (Empty)
[ 3 ] →  [ Key: 103  | Value: "Nadia"  ]
[ 4 ] →  [ Key: 124  | Value: "Karim"  ]
[ 5 ] →  (Empty)
[ 6 ] →  (Empty)
[ 7 ] →  (Empty)
[ 8 ] →  [ Key: 208  | Value: "Salim"  ]
[ 9 ] →  (Empty)
        

When requesting key 103, the computer does not traverse slots 0, 1, and 2. It performs the instant calculation 103 % 10 = 3 and jumps straight to Table[3] to retrieve "Nadia".

05 The Miracle of Average O(1) Constant Time

Linear searches over $n$ items scale as $O(n)$. Binary searches over sorted arrays scale as $O(\log n)$.

In a Hash Table, the arithmetic evaluation of the hash function and the direct array indexing take exactly the same number of CPU cycles whether the table holds 10 items or 10 billion items. Thus, under typical conditions:

Notice we emphasize "Average Time". Can a Hash Table strictly guarantee $O(1)$ in all conditions? No! Because every hash table must confront an inescapable mathematical truth: Hash Collisions.

06 What is a Hash Collision?

Consider our modulo hash function hash(key) = key % 10. What happens when three distinct keys arrive?

Three entirely distinct keys hash to the exact same bucket index! This phenomenon is known as a Hash Collision:

07 Why Are Collisions Inevitable? (The Pigeonhole Principle)

Mathematics provides a timeless theorem known as the Pigeonhole Principle:

In the real world, the universe of possible keys (names, strings, emails, UUIDs) is virtually infinite. However, your computer's memory table is finite (e.g., 1,000 or 10,000 buckets). Mapping an infinite set of keys onto a finite range of indices makes collisions mathematically unavoidable. Therefore, collisions are not a bug or error—they are an inherent reality of hash tables that must be gracefully engineered for.

08 Collision Resolution Technique 1: Separate Chaining

The most widely implemented solution is Separate Chaining. Instead of storing a single value in each bucket, every bucket serves as a head pointer to a small Linked List:

Index 0 → NULL
Index 1 → NULL
Index 2 → NULL
Index 3 → [ 103: "Nadia" ] ──→ [ 123: "Karim" ] ──→ [ 143: "Salim" ] ──→ NULL
Index 4 → [ 124: "Tanvir" ] ──→ NULL
Index 5 → NULL
        

When searching for key 123:

09 Why Can a Hash Table Degrade to O(n)?

Now we can understand the worst-case scenario.

If a hash function is poorly designed and directs every single key to the exact same bucket (say, Index 3), that bucket's linked chain grows indefinitely:

At this point, all hash table advantages evaporate; it degenerates into an ordinary slow Linked List with $O(n)$ search complexity! Hence, the performance of a hash table depends fundamentally on how uniformly its hash function distributes keys across buckets.

10 Collision Resolution Technique 2: Open Addressing

Open Addressing avoids linked lists entirely. All data elements reside directly inside the contiguous array slots.

When an insertion collision occurs, the algorithm systematically probes subsequent slots in the table until it discovers an empty bucket:

11 How Linear Probing Operates

The simplest form of Open Addressing is Linear Probing:

During lookups, the search inspects Slot 3, then steps linearly through 4 and 5 until either the target key is found or an empty slot confirms its absence.

12 Quadratic Probing and Double Hashing

Linear probing suffers from primary clustering—adjacent occupied slots merge into long chains that slow down operations. Two alternative probing strategies address this:

13 Step-by-Step Search Algorithm

Every lookup follows a clear algorithmic sequence:

14 Step-by-Step Insertion Algorithm

When inserting a new Key: Value pair:

15 Deletion and The Tombstone Marker

With Separate Chaining, deleting a key is straightforward: simply unlink the node from the linked list.

With Linear Probing, however, simply wiping a slot to EMPTY breaks lookup chains (because searches stop upon encountering an empty slot). To solve this, systems replace deleted entries with a special marker called a Tombstone:

16 What is the Load Factor?

The metric used to gauge how crowded a hash table has become is the Load Factor ($\alpha$):

For instance, if a table has 10 slots and holds 7 items, its Load Factor is $7 \div 10 = 0.70$.

As the load factor creeps higher, collisions surge geometrically and average $O(1)$ performance deteriorates. Most production standard libraries automatically trigger a resize when the load factor exceeds 0.70 to 0.75.

17 How Resizing and Rehashing Occur

When the load factor threshold is breached, the hash table transparently allocates a new backing array—typically double the capacity (e.g., from 8 to 16 slots):

This process of re-evaluating every key's position against the new larger capacity is termed Rehashing. While a single rehashing step takes $O(n)$, amortized across thousands of insertions, individual operations maintain an amortized $O(1)$ cost.

18 Is "Hashing" the Same as Encryption? (A Common Misconception!)

Students frequently confuse hash table hashing with cryptography. It is crucial to distinguish them:

19 Hash Tables and Database Indexing

In relational and NoSQL databases, executing an exact point lookup such as WHERE id = 839271 utilizes a Hash Index to fetch the row instantly in $O(1)$ time.

However, if you execute a range query such as WHERE age BETWEEN 20 AND 30, a hash index is useless! Because hash tables scatter keys pseudo-randomly without sorting, databases must rely on B-Trees or B+ Trees for range-based lookups.

20 Ubiquitous Software Applications of Hash Tables

21 What Data Types Can Serve as a Key?

Keys are not restricted to integers. Any immutable (hashable) data type can serve as a valid key:

Mutable collections (such as Python lists) cannot be used as keys, because modifying their internal contents after insertion alters their hash value, rendering the stored record permanently unretrievable.

22 Three Essential Qualities of a Good Hash Function

23 Are Hash Values Guaranteed Across Program Runs?

In modern languages such as Python and Java, runtime environments randomize internal hash seeds upon startup to defend against Hash-DoS cyberattacks. Consequently, never persist internal in-memory hash values to disk or rely on them as permanent database primary keys!

24 Time Complexity Summary

25 Hash Table vs Array

26 Hash Table vs Linked List

Searching a Linked List requires linear traversal from the head node through the chain ($O(n)$). A Hash Table calculates the destination index mathematically and jumps directly to the target record ($O(1)$).

27 Dictionary, Map, HashMap across Different Languages

This fundamental associative structure takes on various names depending on your programming ecosystem:

28 Complete Architectural Flow

                   KEY
                    │
                    ▼
             ┌──────────────┐
             │ Hash Function│
             └──────┬───────┘
                    │
                    ▼
                  Index
                    │
                    ▼
              ┌────────────┐
              │   Bucket   │
              └─────┬──────┘
                    │
            ┌───────┴────────┐
            │                │
         No Collision     Collision
            │                │
            ▼                ▼
          Value          Chaining (Linked Nodes)
        

29 The Paradigm Shift of Hash Tables

Linear structures taught us about sequential order and positional offsets. Hash Tables introduced a transformative philosophy:

30 Seven Golden Lessons of Hash Tables

31 Can All Real-World Data Be Modeled as Flat Key-Values?

Hash tables deliver unbelievable $O(1)$ speed for flat key-value pairs. But what happens when your data naturally looks like this?

                   Company (CEO)
                  /             \
          Engineering          Sales (VP)
           /       \            /      \
      Backend   Frontend     Region A  Region B
        

Here there are no straight lines, nor single flat keys—instead, we have Parent-Child relationships, ancestry, and structural hierarchy. To model file system folder trees, HTML document object models (DOM), or corporate organograms, we need a structure that branches outward organically. That marvelous non-linear hierarchical structure is: The Tree.