DSA Tutorial

🔍

Stack Basics Stack Operations Stack Implementation Stack Collection Frameworks Balanced Parentheses Expression Evaluation Monotonic Stack Practice Problems

Queue Basics Queue Operations Queue Implementation Queue Collection Frameworks Circular Queue Deque Priority Queue Queue in BFS Practice Problems

Tree Basics & Terminologies Types of Trees Binary Tree Basics & Types Binary Tree DFS Traversals BFS / Level Order Traversal Binary Tree Operations Binary Tree Practice Problems BST Basics BST DFS Traversals BST BFS Traversal BST Operations BST Practice Problems Heap Trie Advanced Trees

Graph Basics and Terminologies Graph Representation Types of Graphs Breadth First Search (BFS)Depth First Search (DFS)Connected Components Cycle Detection Topological Sort Shortest Path Algorithms Dijkstra's Algorithm Minimum Spanning Tree Union Find (DSU)Practice Problems

Backtracking Basics Decision Tree Thinking Time & Space Complexity Subsets Permutations Combination Problems N-Queens Sudoku Solver Word Search Common Mistakes Practice Problems

DP Basics State Transition Thinking Memoization Tabulation Memoization vs Tabulation 1D Dynamic Programming 2D Dynamic Programming Knapsack Pattern Longest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Practice Problems

Two Pointers Sliding Window Fast & Slow Pointers Prefix Sum Hashing Pattern Binary Search Pattern Greedy Pattern Divide & Conquer Heap Pattern Monotonic Stack & Queue Practice Problems

Top 100 DSA Problems Blind 75 NeetCode 150 Pattern → Problem Map Easy → Medium Roadmap Medium → Hard Roadmap FAANG Question Bank Mock Interviews

Weekly Revision Plan Spaced Repetition Guide Mixed Problem Sets Mock Interview Schedule Self Assessment Checklist

Hashing Basics

What Is Hashing?

Hashing is a technique that maps data of arbitrary size to a fixed-size index in a table. That index is used to store and retrieve the data directly — no searching, no scanning, no comparison with other elements.

The core idea: you have a key (anything — a string, an integer, an object). You run it through a hash function that converts it into a number. That number becomes the index into an array called a hash table where the value is stored. When you want to retrieve the value later, you run the same key through the same hash function, get the same index, and read the value directly.

Key: "alice"
           ↓
    Hash Function
           ↓
    Index: 3
           ↓
Hash Table:
  [0] → null
  [1] → null
  [2] → null
  [3] → ("alice", 95)    ← stored here
  [4] → null
  [5] → null

Lookup "alice":
  hash("alice") → 3 → return table[3] → 95
  One step. O(1).

This direct-addressing property is what makes hashing uniquely powerful. Arrays give you O(1) access by index. Hashing gives you O(1) access by any key — not just by numeric position.

Why Hashing Matters in DSA

Before hashing, the fastest general-purpose lookup was O(log n) with a balanced binary search tree. To find if a key exists among n items, you had to compare and traverse.

Hashing changes the equation fundamentally:

Without hashing:
  "Is 'alice' in this set of 1,000,000 names?"
  Binary search tree: ~20 comparisons (log₂ 1,000,000 ≈ 20)
  Unsorted array: up to 1,000,000 comparisons

With hashing:
  hash("alice") → index → check that slot
  1 computation. O(1) regardless of table size.

This is why hashing is used everywhere: database indexes, caches, symbol tables in compilers, frequency counting, duplicate detection, grouping problems. Any problem that asks "have I seen this before?" or "how many times did this appear?" uses hashing.

The Hash Function

A hash function takes a key and returns an integer — the hash code. The index in the hash table is then computed from the hash code, typically as:

index = hash_code % table_size

What Makes a Good Hash Function?

Property 1 — Deterministic
  Same key → always same hash code
  "alice" → 3, always. Not 3 sometimes, 7 other times.

Property 2 — Uniform distribution
  Keys should spread evenly across the table
  All outputs landing in index 0 defeats the purpose

Property 3 — Fast to compute
  O(1) or O(k) where k = key length
  A hash function that takes O(n) time to compute defeats the speedup

Property 4 — Avalanche effect
  Small change in key → large change in hash
  "alice" and "Alice" should hash to very different values
  This prevents clustering of similar keys

Integer Keys

For integer keys, a common hash function is:

hash(k) = k % table_size

For table_size = 7:
  hash(0)  = 0
  hash(7)  = 0   ← same slot as 0 — collision!
  hash(13) = 6
  hash(20) = 6   ← same slot as 13 — collision!

Better: use a prime table_size
  Prime sizes reduce clustering from multiples
  Common sizes: 7, 11, 17, 31, 67, 127, 257, ...

String Keys

For string keys, a common approach multiplies each character by a prime base and accumulates:

hash("abc") = ('a' × 31² + 'b' × 31¹ + 'c' × 31⁰) % table_size
            = (97 × 961 + 98 × 31 + 99 × 1) % table_size
            = (93217 + 3038 + 99) % table_size
            = 96354 % table_size

The prime base 31 gives good distribution and is used in
Java's String.hashCode() implementation.

Java

Try it out

public class HashFunctionDemo {

    // Simple integer hash
    public static int hashInt(int key, int tableSize) {
        return Math.abs(key % tableSize);
    }

    // Polynomial string hash (mirrors Java's String.hashCode())
    public static int hashString(String key, int tableSize) {
        int hash = 0;
        for (char c : key.toCharArray()) {
            hash = 31 * hash + c;
        }
        return Math.abs(hash % tableSize);
    }

    public static void main(String[] args) {
        int size = 11; // Prime table size

        // Integer hashing
        System.out.println("Integer hashing (table size 11):");
        int[] keys = {0, 7, 13, 20, 55, 100};
        for (int k : keys) {
            System.out.println("  hash(" + k + ") = " + hashInt(k, size));
        }

        // String hashing
        System.out.println("\nString hashing (table size 11):");
        String[] words = {"alice", "bob", "charlie", "alice"}; // Note: alice appears twice
        for (String w : words) {
            System.out.println("  hash(\"" + w + "\") = " + hashString(w, size));
        }

        // Java's built-in hashCode
        System.out.println("\nJava built-in hashCode:");
        System.out.println("  \"alice\".hashCode() = " + "alice".hashCode());
        System.out.println("  \"Alice\".hashCode() = " + "Alice".hashCode());
        System.out.println("  \"alice\" and \"Alice\" differ: "
            + ("alice".hashCode() != "Alice".hashCode()));
    }
}

Output:
Integer hashing (table size 11):
  hash(0)   = 0
  hash(7)   = 7
  hash(13)  = 2
  hash(20)  = 9
  hash(55)  = 0
  hash(100) = 1

String hashing (table size 11):
  hash("alice")   = 3
  hash("bob")     = 7
  hash("charlie") = 5
  hash("alice")   = 3   ← same key → same index, always

What Is a Collision?

A collision happens when two different keys produce the same index in the hash table. This is inevitable — no matter how good the hash function is, a table of finite size will eventually have two keys land in the same slot.

Example with table size 7:
  hash("alice") = 3
  hash("dave")  = 3    ← collision! Both map to index 3

  Table:
  [0] → null
  [1] → null
  [2] → null
  [3] → ???            ← where do both entries go?
  [4] → null
  [5] → null
  [6] → null

The birthday paradox explains why collisions happen sooner than you expect. In a table of size n, you expect a collision after inserting roughly √n keys — not n keys. For a table of 365 slots, a 50% collision probability hits at just 23 entries.

This is not a bug — it is an expected property of any finite hash table. The design question is how to handle collisions, not how to prevent them entirely.

Collision handling is covered in depth in the next topic. For now, the two fundamental strategies are:

Chaining: each table slot holds a linked list
  When two keys collide, both go in the same list
  Lookup: hash to the slot, then scan the short list

Open Addressing: find the next available slot
  When a collision occurs, probe neighboring slots
  Lookup: hash to the slot, probe forward if key doesn't match

The Hash Table Data Structure

A hash table is the array-based implementation that uses a hash function to map keys to indices. It is the underlying structure behind all hash-based collections.

Hash Table (size 7, chaining):

Index  Contents
  0  → [("mallory", 88)]
  1  → []
  2  → [("charlie", 72), ("grace", 91)]   ← two entries, same hash
  3  → [("alice", 95)]
  4  → []
  5  → [("bob", 61)]
  6  → [("dave", 77)]

Operations:
  Insert ("alice", 95): hash("alice")→3 → store at index 3
  Lookup "alice":        hash("alice")→3 → scan list at 3 → found (95)
  Lookup "eve":          hash("eve")→?   → scan list → not found (-1)
  Delete "bob":          hash("bob")→5   → remove from list at 5

All four operations — insert, lookup, delete, update — are O(1) average because the hash function points directly to the right slot and the chain at each slot is expected to be short (close to 1 entry if the table is not overloaded).

Load Factor: The Key to O(1) Performance

The load factor α is the ratio of stored entries to table size:

α = number of entries / table size

α = 0.5:  table is half full — very few collisions, fast lookups
α = 1.0:  table is full — frequent collisions, chains getting longer
α = 2.0:  twice as many entries as slots — chains average length 2
α = 10.0: ten entries per slot on average — effectively O(n) lookup

To keep O(1) performance, hash tables resize (rehash) when the load factor exceeds a threshold — typically 0.75 for Java's HashMap, and roughly similar for Python's dict and C++'s unordered_map.

Rehashing means:

›Allocate a new, larger array (usually 2× the current size)
›Recompute the hash index for every existing entry in the new table
›Discard the old array

Rehashing is O(n) but happens infrequently — the amortized cost per insertion remains O(1).

Java HashMap load factor thresholds:
  Default capacity:     16 slots
  Load factor limit:    0.75
  Resize triggers when: 16 × 0.75 = 12 entries inserted
  New capacity:         32 slots
  Next resize at:       32 × 0.75 = 24 entries

Python dict:
  Resizes when load factor exceeds ~0.66
  Growth factor: ~4× for small dicts, 2× for larger

C++ unordered_map:
  max_load_factor() default = 1.0
  Rehashes when n / bucket_count > max_load_factor

Hash Functions in Each Language

You rarely write hash functions from scratch — languages provide them for built-in types and require you to implement them for custom objects.

Java

Try it out

public class LanguageHashFunctions {

    public static void main(String[] args) {
        // Java computes hashCode() for common types automatically
        System.out.println("Integer hash:   " + Integer.hashCode(42));
        System.out.println("String hash:    " + "hello".hashCode());
        System.out.println("Boolean hash:   " + Boolean.hashCode(true));
        System.out.println("Double hash:    " + Double.hashCode(3.14));

        // Using in HashMap — hashCode() is called automatically
        java.util.HashMap<String, Integer> map = new java.util.HashMap<>();
        map.put("alice", 95);  // Java calls "alice".hashCode() internally
        System.out.println("HashMap get:    " + map.get("alice"));

        // Custom class must override hashCode() and equals()
        // Without override, uses identity hash (memory address) — objects
        // with equal fields are not equal and cannot be found in maps
    }

    // Example of correct hashCode override for a custom class
    static class Point {
        int x, y;

        Point(int x, int y) { this.x = x; this.y = y; }

        @Override
        public int hashCode() {
            // Combine fields using prime multiplication — standard pattern
            return 31 * x + y;
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj) return true;
            if (!(obj instanceof Point)) return false;
            Point other = (Point) obj;
            return this.x == other.x && this.y == other.y;
        }
    }
}

Output (Java):
Integer hash:   42
String hash:    99162322
Boolean hash:   1231
HashMap get:    95
Point in set:   true

Why Mutable Objects Cannot Be Hash Map Keys

This is a critical correctness rule. Once an object is inserted into a hash map as a key, its hash code must not change. If it does, the stored entry becomes permanently unfindable.

Scenario (pseudocode):
  list key = [1, 2, 3]
  map.put(key, "value")      // stored at index = hash([1,2,3]) % size

  key.append(4)              // mutate the key — hash changes!

  map.get(key)               // hash([1,2,3,4]) → different index
                             // → looks in wrong slot
                             // → returns null / not found!

  The entry ("value") is still in the table at the OLD index.
  It is now permanently orphaned — can never be found or deleted.

This is why:

›Java String is immutable — safe to use as map key
›Python list is not hashable — the language prevents the mistake
›Python tuple is hashable — immutable by design
›C++ requires you to declare const key types — mutating is undefined behavior
›JavaScript objects use reference identity — mutation does not change identity, but this creates its own confusions

Hashing vs Other Lookup Structures

Understanding when hashing is the right choice versus trees or arrays.

Structure	Lookup	Insert	Delete	Ordered	Memory
Unsorted array	O(n)	O(1) append	O(n)	No	Low
Sorted array	O(log n) binary search	O(n) shift	O(n) shift	Yes	Low
Balanced BST	O(log n)	O(log n)	O(log n)	Yes	Medium
Hash Table	O(1) average	O(1) average	O(1) average	No	Medium-High

Choose hashing when:

›You need O(1) lookup, insert, and delete by key
›Order does not matter
›Keys are any type (strings, integers, tuples)
›The key set is not known in advance

Choose a sorted structure when:

›You need keys in sorted order
›You need range queries ("all keys between x and y")
›You need the minimum or maximum key efficiently
›Worst-case guarantees matter more than average performance

Interview Questions

Q: What is a hash function and what properties must it have?

A hash function maps a key to a non-negative integer (the hash code). It must be deterministic — the same key always produces the same hash code. It should be fast to compute — O(1) or O(k) for a key of length k. It should distribute keys uniformly across the table to minimize collisions. It should have the avalanche effect — small changes in the key produce large changes in the hash code, preventing clustering.

Q: Why is O(1) lookup for a hash table an average-case guarantee, not worst-case?

In the worst case, all keys hash to the same index and every lookup must scan a chain of length n — O(n). This happens when the hash function is terrible or the input is adversarially chosen to cause maximum collisions. With a good hash function and a reasonable load factor (typically < 0.75), the expected chain length at any slot is O(1), making lookup O(1) on average. Cryptographic hash functions are used when adversarial inputs are a concern.

Q: Why can't you use a mutable object as a hash map key?

The hash map uses the key's hash code to determine which slot to store the entry. If the key mutates after insertion, its hash code changes — the entry is now stored at the old slot but any new lookup will compute a new hash code pointing to a different slot. The entry becomes permanently unfindable. This is why Java String (immutable), Python tuples (immutable), and C++ POD types are safe map keys.

Q: What is the load factor and why does it matter?

The load factor is the ratio of stored entries to table capacity. As the load factor increases, the expected chain length increases — a load factor of 1.0 means one entry per slot on average, with some slots having longer chains. Most hash table implementations resize (rehash) when the load factor exceeds a threshold (0.75 in Java HashMap) to keep lookup time close to O(1). Pre-sizing a hash map when you know the approximate number of entries avoids rehashing.

FAQs

Is a hash table the same as a hash map?

A hash table is the underlying data structure — an array with a hash function that maps keys to indices. A hash map (HashMap, dict, unordered_map) is the key-value collection built on top of a hash table. A hash set is also built on a hash table but stores only keys, not values. The term "hash table" is often used interchangeably with "hash map" in conversation.

Why does Python disallow lists as dictionary keys?

Python requires dictionary keys to be hashable — their hash value must not change. Lists are mutable (elements can be added, removed, or changed), so their hash would change with the content, making it impossible to reliably find them in a dictionary. Python raises TypeError: unhashable type: 'list' to prevent the bug rather than allow silent data loss. Use a tuple instead — it is immutable and hashable.

Does hash(x) in Python always return the same value for the same x?

Within one Python session, yes. Across sessions, no. Python uses hash randomization (enabled by default since Python 3.3) — the hash function for strings and bytes is seeded with a random value at startup. This prevents hash-flooding denial-of-service attacks. Use PYTHONHASHSEED=0 to disable randomization if reproducibility is required across sessions.

What is a perfect hash function?

A perfect hash function maps a fixed, known set of keys to unique indices with no collisions. It is only possible when the complete set of keys is known in advance (static sets). Perfect hash functions are used in compilers (keyword tables), network routing tables, and other settings where the key set never changes. For general dynamic use cases, they are not applicable.

Quick Quiz

Question 1: A hash function maps key k to index k % 7. For table size 7, which two keys will always collide?

›A) 3 and 10
›B) 3 and 7
›C) 7 and 14
›D) Both B and C

Answer: D) Both B and C. 3 % 7 = 3 and 10 % 7 = 3 — collision. 7 % 7 = 0 and 14 % 7 = 0 — collision. Any pair of keys that differ by exactly 7 (or a multiple of 7) will always hash to the same index with this function and table size.

Question 2: A hash table has capacity 16 and load factor threshold 0.75. After how many insertions does it resize?

›A) 8
›B) 12
›C) 14
›D) 16

Answer: B) 12. The resize threshold is capacity × load_factor = 16 × 0.75 = 12. After the 12th insertion, the table rehashes to a larger capacity (typically 32) and re-distributes all entries.

Question 3: Why should the table size be a prime number?

›A) Prime sizes are always powers of two — faster for computers
›B) Prime sizes reduce clustering when keys have common factors
›C) Prime sizes guarantee no collisions
›D) Prime sizes are required by the birthday paradox

Answer: B) Prime sizes reduce clustering when keys have common factors. If keys are multiples of some factor k and the table size shares that factor, many keys hash to a small subset of indices. A prime table size has no common factors with any typical key distribution, producing more uniform spreading. Note: Java's HashMap uses power-of-two sizes (faster modulo via bitwise AND) and compensates with a secondary mixing step.

Question 4: You insert a key-value pair into a HashMap. Then you mutate the key object. What happens when you try to look up that key?

›A) The lookup succeeds — HashMap updates the slot automatically
›B) The lookup returns the old value using the old hash
›C) The lookup fails — it hashes to a different slot and the entry is not found there
›D) The HashMap throws an exception

Answer: C) The lookup fails. The HashMap stored the entry at the slot computed from the key's hash at insertion time. After mutation, the key's hash code is different, so the lookup computes a new slot — which either contains a different entry or is empty. The original entry is still in the table at the old slot but is permanently unreachable. Most languages prevent this for built-in types (immutable strings, etc.) but allow it for custom mutable objects.

Summary

Hashing is the technique that enables O(1) average-case lookup, insert, and delete for any key type. A hash function maps keys to integers; a modulo operation converts those integers to array indices; the hash table stores values at those indices.

The key ideas to carry forward:

›Hash function: deterministic, fast, uniform distribution, avalanche effect
›Index formula: hash_code % table_size — use a prime table size for better distribution
›Collisions are inevitable — the birthday paradox guarantees them well before the table is full
›Load factor = entries / capacity — keep below 0.75 for O(1) performance
›Rehashing when load factor is exceeded — O(n) cost, O(1) amortized per insertion
›Mutable objects cannot be hash map keys — their hash must not change after insertion
›Use arrays for O(1) positional access; use hash tables for O(1) key-based access; use trees for O(log n) ordered access

In the next topic, you will explore HashMap — the key-value collection built on hashing, its complete API, and the patterns where it appears in interview problems.

←

PreviousPractice Problems

NextHashMap

→