Module 8: Hashing & Hash Tables

Hashing is one of the most powerful ideas in Data Structures.
It allows us to trade space for time, converting many O(n²) problems into O(n) solutions.

At its core, hashing answers one question efficiently:

“Have I seen this before?”

Hash Function Basics

What is a Hash Function?

A hash function maps a key to an index in a fixed-size table.

index = hash(key)

Example:

hash(23) = 23 % 10 = 3

Properties of a Good Hash Function

• Fast computation
• Uniform distribution
• Same input → same output
• Minimizes collisions

Bad hash functions cause clustering, which ruins performance.

Hash Table Structure

A hash table consists of:

• Array (buckets)
• Hash function
• Collision handling mechanism

Operations:

• Insert
• Search
• Delete

Average time complexity: O(1)
Worst case: O(n) (when collisions dominate)

Collision Handling

Why Collisions Happen

Two different keys may produce the same hash index.

Example:

hash(12) = 2
hash(22) = 2

---

Chaining (Most Common)

Each bucket stores a linked list (or tree).

Index 2 → [12 → 22 → 32]

Java uses:

• Linked List initially
• Converts to Red-Black Tree when chain grows large

Open Addressing (Conceptual)

• Linear probing
• Quadratic probing
• Double hashing

Used in low-level systems, less in interviews.

HashMap Internals (Java Perspective)

How HashMap Works

1. Key’s hashCode() is called
2. Index is calculated
3. Key-value pair stored in bucket
4. Collisions handled via chaining

Important:

• HashMap allows one null key
• Order is not guaranteed
• Load factor default = 0.75

When size exceeds threshold → rehashing occurs

---

HashSet Internals

HashSet is internally backed by a HashMap.

HashSet.add(x) → map.put(x, PRESENT)

Properties:

• Stores unique elements
• No indexing
• Fast lookups

Frequency Problems

Pattern

Count occurrences of elements.

Example:
Find frequency of characters in a string.

Map<Character, Integer> map = new HashMap<>();
for(char c : s.toCharArray()){
    map.put(c, map.getOrDefault(c, 0) + 1);
}

Used in:

• Majority element
• First non-repeating character
• Mode calculation

Subarray Sum Problems

Problem

Check if a subarray with sum = K exists.

Brute Force

O(n²)

Optimized Using Hashing

Idea:
If

prefixSum[j] - prefixSum[i] = K

Then subarray exists.

Set<Integer> set = new HashSet<>();
set.add(0);
int sum = 0;

for(int x : arr){
    sum += x;
    if(set.contains(sum - K))
        return true;
    set.add(sum);
}

Time: O(n)

---

Two Sum & Variants

Classic Two Sum

Find indices such that:

nums[i] + nums[j] = target

Map<Integer, Integer> map = new HashMap<>();

for(int i = 0; i < nums.length; i++){
    int need = target - nums[i];
    if(map.containsKey(need))
        return new int[]{map.get(need), i};
    map.put(nums[i], i);
}

---

Variants

• Count pairs
• Closest sum
• 3-Sum / 4-Sum (hashing + two pointers)

---

Longest Consecutive Sequence

Problem

Find longest sequence of consecutive numbers.

Example:

[100, 4, 200, 1, 3, 2] → 4

Approach

• Store all numbers in HashSet
• Start sequence only if num - 1 not present

Set<Integer> set = new HashSet<>();
for(int x : nums) set.add(x);

int longest = 0;

for(int x : set){
    if(!set.contains(x - 1)){
        int curr = x;
        int count = 1;
        while(set.contains(curr + 1)){
            curr++;
            count++;
        }
        longest = Math.max(longest, count);
    }
}

Time: O(n)

---

Anagram Grouping

Problem

Group words that are anagrams.

Example:

["eat","tea","tan","ate","nat","bat"]

Approach

• Sort string as key
• Use HashMap

Map<String, List<String>> map = new HashMap<>();

for(String word : strs){
    char[] arr = word.toCharArray();
    Arrays.sort(arr);
    String key = new String(arr);

    map.putIfAbsent(key, new ArrayList<>());
    map.get(key).add(word);
}

---

Custom Hashing

When Custom Hashing Is Needed

• Pair keys
• Objects
• Coordinates
• Composite data

---

Example: Pair Hashing

class Pair {
    int x, y;

    public int hashCode(){
        return Objects.hash(x, y);
    }

    public boolean equals(Object o){
        Pair p = (Pair)o;
        return x == p.x && y == p.y;
    }
}

Without proper hashing:

• Wrong results
• Performance drops

---

Time Complexity Pitfalls

Expected O(1) Is Not Guaranteed

Worst-case HashMap → O(n)

Reasons:

• Poor hash function
• Too many collisions
• Adversarial inputs

---

Common Mistakes

• Using mutable keys
• Forgetting equals + hashCode
• Assuming order in HashMap
• Nested hashing without analysis

---

When to Use Hashing

Use hashing when:

• You need fast lookup
• Order doesn’t matter
• Duplicate handling is required
• Constraints demand O(n)

Avoid hashing when:

• Order is important
• Memory is limited
• Keys are large objects without good hash