Visualization Exercise: Hash Distribution

Deepen your understanding of hash collision resolution by simulating bucket assignments and rehashing manually.

Problem: Simulating a Hash Table with Linear Probing

Setup

You are given a Hash Table with Capacity = 7 (indices 0 through 6).

• Collision Strategy: Open Addressing with Linear Probing (f(i) = i).
• Hash function: h(k) = k mod 7.

Insert the following sequence of keys:

15, 22, 8, 29, 36

Step-by-Step Execution Trace

1. Insert 15

h(15) = 15 mod 7 = 1

• Bucket 1 is empty.
• Place 15 at Index 1.

Copy code[ 0: null, 1: 15, 2: null, 3: null, 4: null, 5: null, 6: null ]

2. Insert 22

h(22) = 22 mod 7 = 1

• Bucket 1 is occupied (15) → Collision!
• Linear probe: check index (1 + 1) = 2.
• Bucket 2 is empty.
• Place 22 at Index 2.

Copy code[ 0: null, 1: 15, 2: 22, 3: null, 4: null, 5: null, 6: null ]

3. Insert 8

h(8) = 8 mod 7 = 1

• Bucket 1 is occupied (15) → Collision!
• Linear probe: check index 2 (22) → Collision!
• Linear probe: check index 3.
• Bucket 3 is empty.
• Place 8 at Index 3.

Copy code[ 0: null, 1: 15, 2: 22, 3: 8, 4: null, 5: null, 6: null ]

4. Insert 29

h(29) = 29 mod 7 = 1

• Probing indices 1, 2, 3 (all occupied).
• Place 29 at Index 4.

Copy code[ 0: null, 1: 15, 2: 22, 3: 8, 4: 29, 5: null, 6: null ]

5. Insert 36

h(36) = 36 mod 7 = 1

• Probing indices 1, 2, 3, 4 (all occupied).
• Place 36 at Index 5.

Copy code[ 0: null, 1: 15, 2: 22, 3: 8, 4: 29, 5: 36, 6: null ]

Notice what happened? A single cluster formed from index 1 to index 5! This is classic Primary Clustering in linear probing.

Challenge 2: Group Anagrams using Hash Tables

Given an array of strings, group anagrams together:

Copy codefun groupAnagrams(strs: Array<String>): List<List<String>> {
    val map = HashMap<String, MutableList<String>>()

    for (str in strs) {
        // Sort characters to form canonical key
        val sortedKey = str.toCharArray().sorted().joinToString("")
        
        map.computeIfAbsent(sortedKey) { mutableListOf() }.add(str)
    }

    return map.values.toList()
}

Complexity:

• Time: O(N · K log K) where N is word count and K is max word length.
• Space: O(N · K) to store keys and grouped lists.