Hash Tables

Why should you care?

Imagine you have one million user records and you need to find a user's information using their username.

Searching one record at a time could take a long time.

A hash table can often find the required value in O(1) average time.

Hash tables power many things you use every day:

• Dictionaries and maps
• Database indexing
• Caches
• Symbol tables in compilers
• Counting frequencies
• Duplicate detection
• Sets
• Fast lookups in applications

Understanding hash tables also teaches an important computer science lesson:

You can trade memory for speed.

---

The Problem

Suppose we have these student records:

ID       Name
101      Arun
205      Priya
309      Ravi
412      Kumar

If we store them in an array:

[101, Arun]
[205, Priya]
[309, Ravi]
[412, Kumar]

and someone asks:

"Who is student 309?"

We might have to check:

101 → no
205 → no
309 → found

With a large collection, this can become O(n).

We want a way to take a key such as:

309

and quickly determine where its value should be stored.

That's the problem hash tables solve.

---

The Concept

A hash table is a data structure that stores key-value pairs and uses a hash function to determine where a key should be placed.

For example:

Key → Value

101 → Arun
205 → Priya
309 → Ravi
412 → Kumar

The basic process is:

Key
 ↓
Hash Function
 ↓
Hash Value
 ↓
Array Index
 ↓
Stored Value

For example:

309
 ↓
hash(309)
 ↓
some number
 ↓
index 4
 ↓
"Ravi"

The hash table therefore combines two ideas:

Hash Function + Array

The array provides fast indexed access, while the hash function determines which index to use.

---

Simple Explanation

Imagine you have 10 numbered lockers:

0  1  2  3  4  5  6  7  8  9

You need to store information about different students.

Instead of deciding manually which locker to use, you create a rule:

locker = studentID % 10

For student 123:

123 % 10 = 3

So:

Student 123
     ↓
123 % 10
     ↓
     3
     ↓
Locker 3

Another student:

456 % 10 = 6

So student 456 goes into locker 6.

The hash function essentially acts as a rule for converting a key into an array position.

Real hash functions are more sophisticated than this example, but the basic idea is the same.

---

Real-world Analogy

Imagine a huge library.

Instead of searching every book one by one, each book receives a classification number.

For example:

Book → Classification → Shelf

You don't walk through the entire library looking for a book.

You calculate or look up its classification and go directly to the appropriate area.

A hash table works similarly:

Key
 ↓
Hash
 ↓
Location
 ↓
Value

The goal is to avoid searching through every stored item.

---

Code Example

In Java, HashMap provides a hash-table-based map.

import java.util.*;

public class Main {
    public static void main(String[] args) {

        HashMap<Integer, String> students = new HashMap<>();

        students.put(101, "Arun");
        students.put(205, "Priya");
        students.put(309, "Ravi");

        System.out.println(students.get(309));
    }
}

Output:

Ravi

We inserted:

students.put(309, "Ravi");

and later retrieved it using:

students.get(309);

The important idea is that we don't need to search every student manually.

We give the map the key:

309

and it uses hashing to determine where the corresponding value can be found.

Checking whether a key exists

if (students.containsKey(309)) {
    System.out.println("Student exists");
}

Removing a key

students.remove(309);

Updating a value

students.put(101, "Arun Kumar");

If key 101 already exists, its value is replaced.

---

Common Mistakes

Mistake 1: Assuming hash tables are always O(1)

You will often hear:

"Hash table lookup is O(1)."

That's an oversimplification.

The more accurate statement is:

Hash table lookup is O(1) on average, assuming a good hash function and controlled collisions.

In unfavorable situations, operations can degrade toward O(n) depending on the implementation and collision behavior.

So:

Average: O(1)
Worst case: potentially O(n)

---

Mistake 2: Thinking different keys always produce different indexes

This is false.

Consider:

hash(101) % 10 = 1
hash(111) % 10 = 1

Both keys produce the same index.

This is called a collision.

101 ──┐
      ├──→ Index 1
111 ──┘

A hash table therefore needs a mechanism for handling collisions.

---

Mistake 3: Confusing a hash value with an array index

A hash function might produce a very large integer:

hash(key) = 284739284

But your table might contain only 100 buckets.

You need to map the hash to a valid index, conceptually:

index = hash(key) % tableSize

So:

Hash value ≠ necessarily array index

The hash is used to derive the index.

---

Advanced Notes

1. Hash functions

A hash function converts a key into a numerical hash value.

Conceptually:

h(key) → integer

A good hash function should distribute keys reasonably evenly across the table.

For example:

Keys
 ↓
Hash Function
 ↓
┌────┬────┬────┬────┬────┐
│    │ A  │    │ B  │    │
└────┴────┴────┴────┴────┘

Poor distribution can cause many collisions.

Good distribution helps maintain fast operations.

---

2. Collisions

A collision occurs when different keys map to the same bucket.

For example:

Key A ──┐
        ├──→ Bucket 3
Key B ──┘

There are several ways to handle collisions.

The two major approaches are:

1. Separate chaining
2. Open addressing

---

3. Separate chaining

With separate chaining, each bucket can contain multiple entries.

Conceptually:

Bucket 0 → empty
Bucket 1 → [101, Arun] → [111, Priya]
Bucket 2 → [202, Ravi]
Bucket 3 → empty

The bucket essentially contains a small collection of entries.

When looking for key 111:

111
 ↓
hash
 ↓
Bucket 1
 ↓
Search entries in bucket
 ↓
111 → Priya

This is one common way hash tables handle collisions.

---

4. Open addressing

With open addressing, all entries are stored directly inside the table.

If the calculated position is occupied, the table searches for another available position according to a probing strategy.

For example:

Index:  0    1    2    3    4
       ┌────┬────┬────┬────┬────┐
       │    │101 │    │111 │    │
       └────┴────┴────┴────┴────┘

One common strategy is linear probing:

index
  ↓
3 occupied
  ↓
try 4
  ↓
if occupied, try 5
  ↓
...

Other strategies include quadratic probing and double hashing.

---

5. Load factor

One important concept is the load factor.

It is approximately:

Load Factor = Number of Stored Entries / Number of Buckets

For example:

Entries = 7
Buckets = 10

Load Factor = 7 / 10 = 0.7

As the table becomes more crowded, collisions generally become more likely.

When the load factor becomes too high, implementations may resize and rehash the table.

---

6. Rehashing

Suppose a table has 5 buckets:

0  1  2  3  4

and becomes too full.

The implementation may create a larger table:

0  1  2  3  4  5  6  7  8  9

The entries may need to be hashed again because their indexes depend on the table size.

This process is called rehashing.

Although resizing can be expensive at that moment, it helps maintain efficient average performance over many operations.

---

7. HashSet

A hash table doesn't always need to store a separate value.

Sometimes you only care whether something exists.

For example:

HashSet<Integer> numbers = new HashSet<>();

numbers.add(10);
numbers.add(20);
numbers.add(30);

System.out.println(numbers.contains(20));

Output:

true

A HashSet is useful when the primary requirement is membership testing and uniqueness.

Conceptually:

HashMap:
Key → Value

HashSet:
Key → Exists

---

8. Hashing strings

Hash tables aren't limited to integers.

You can use strings as keys:

HashMap<String, Integer> ages = new HashMap<>();

ages.put("Arun", 21);
ages.put("Priya", 22);

System.out.println(ages.get("Priya"));

Output:

22

The string is passed through a hash function to produce a hash value.

So the same fundamental process applies:

"Priya"
   ↓
hashCode()
   ↓
Hash value
   ↓
Bucket
   ↓
22

---

9. Keys and equality

A subtle but important point is that hashing alone isn't enough.

Two different keys can have the same hash:

hash(A) = 42
hash(B) = 42

That doesn't mean:

A == B

Hash tables generally use both:

Hashing
+
Equality comparison

to correctly identify the requested key.

This is particularly important when creating custom key objects in languages such as Java.

---

The Bigger Picture

Hash tables connect several concepts you've already learned:

Arrays
   ↓
Fast indexed access
   ↓
Hash Function
   ↓
Hash Table
   ↓
Fast Key-Based Lookup

They also connect to other major data structures:

Arrays
  ├── Hash Tables
  ├── Dynamic Arrays
  └── Heaps

Linked Lists
  └── Collision Handling

Hash Tables
  ├── HashMap
  ├── HashSet
  └── Caches

And they appear constantly in algorithms.

For example, suppose you need to determine whether an array contains duplicates:

[4, 7, 2, 4, 9]

A naive approach could compare every pair.

A hash set gives a much faster average approach:

4 → add
7 → add
2 → add
4 → already exists → duplicate

This changes the typical time complexity from O(n²) to O(n) average time, at the cost of additional memory.

That's the memory-for-speed trade-off in action.

---

The Most Important Mental Model

A hash table is an array that uses a hash function to decide where a key should look.

Remember this pipeline:

       Key
        ↓
  Hash Function
        ↓
   Hash Value
        ↓
   Bucket / Index
        ↓
      Value

For example:

"Shankar"
    ↓
  hash()
    ↓
  738291
    ↓
  index 7
    ↓
  stored value

And remember one critical exception:

Different keys
      ↓
Can produce
      ↓
Same bucket
      ↓
Collision

A good hash table isn't one that never has collisions.

It's one that handles collisions efficiently.

---

Summary

A hash table stores data as key-value pairs and uses hashing to provide fast average-case lookup.

The key ideas are:

• A hash function converts a key into a hash value.
• The hash value helps determine the storage bucket/index.
• Hash tables provide O(1) average-case insertion, lookup, and deletion.
• Different keys can produce the same bucket, causing collisions.
• Collisions can be handled using techniques such as chaining and open addressing.
• Load factor measures how full the table is.
• Tables may resize and rehash when they become too crowded.
• HashMap is used for key-value mappings.
• HashSet is useful for uniqueness and membership testing.
• Hash tables trade additional memory for fast access.

A hash table turns the question "Where is this value?" into a calculation, transforming potentially expensive searches into near-constant-time lookups—and that idea is one of the most powerful tools in algorithm design.