Custom Hash Design

The problem with complex keys

You have seen hash maps keyed by integers and strings. Now consider:

• "Group anagrams" — the key is a sorted string or a 26-length frequency tuple.
• "Two Sum with pair tracking" — the key is a (value, index) pair.
• "Encode TinyURL" — the key is a random 6-character code, and you need two maps (code→url, url→code).
• "Design HashSet from scratch" — you need to simulate the internal bucketing yourself.

Each case requires you to design what the key looks like. Getting this wrong leads to collisions (two different things mapping to the same key) or to O(n) lookups that defeat the purpose of hashing.

---

The passport control desk story

---

The one idea to remember

---

Design rule 1 — Use a canonical form

A canonical form is a standard representation that all equivalent inputs map to. Two inputs are "equivalent" if your problem treats them as the same bucket.

Example: Anagram grouping (LC #49)

"eat", "tea", "ate" are all anagrams. Their canonical form: sort the characters → "aet". All three map to the same key.

from collections import defaultdict

def groupAnagrams(strs: list[str]) -> list[list[str]]:
    groups = defaultdict(list)
    for s in strs:
        key = "".join(sorted(s))    # canonical form: sorted characters
        groups[key].append(s)
    return list(groups.values())

Alternative canonical form: a 26-element tuple of character counts. Avoids sorting (O(k) vs O(k log k)):

def groupAnagrams_v2(strs: list[str]) -> list[list[str]]:
    groups = defaultdict(list)
    for s in strs:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1
        key = tuple(count)          # tuples are hashable; lists are not
        groups[key].append(s)
    return list(groups.values())

Answer

Python requires hash map keys to be immutable (so their hash value can't change after insertion). Lists are mutable — you can change count[0] after inserting it, which would silently corrupt the map. Tuples are immutable — Python guarantees their hash stays constant. The rule: always convert mutable containers to tuples (or join them into strings) before using them as keys.

---

Design rule 2 — Add separators to avoid false merges

Consider encoding a 2D grid coordinate (row, col) as a string. A naive approach:

key = str(row) + str(col)    # WRONG
# (1, 23) and (12, 3) both become "123"

Fix: use a separator that can't appear in the values:

key = f"{row},{col}"         # (1,23) → "1,23"; (12,3) → "12,3"  ✅

General rule: when concatenating numeric or variable-length parts into a string key, always separate them with a character that cannot be part of the values.

Frame-by-frame: collision example

Without separator:
(1, 23)  → "123"
(12, 3)  → "123"   ← collision — two different grid cells map to the same key!

With separator:
(1, 23)  → "1,23"
(12, 3)  → "12,3"  ← distinct ✅

---

Design rule 3 — Use tuples for multi-field keys

When your key has multiple heterogeneous parts (different types or semantics), a tuple is cleaner and safer than string concatenation:

# Keying by (value, sign) pair
key = (num, "positive")      # tuple — always hashable, no separator needed

Tuples are compared element by element, so (1, "a") and (1, "b") are always distinct. No separator tricks needed.

---

Application: Encode and Decode TinyURL (LC #535)

Design a URL shortener with two operations:

• encode(long_url) → short_code
• decode(short_code) → long_url

Requirements: O(1) both ways, no two distinct URLs can get the same code, the same URL should always get the same code.

import random
import string

class Codec:
    def __init__(self):
        self.url_to_code = {}    # long_url → short_code
        self.code_to_url = {}    # short_code → long_url
        self.BASE = "http://tinyurl.com/"
        self.CHARS = string.ascii_letters + string.digits   # 62 chars

    def _generate_code(self) -> str:
        return "".join(random.choices(self.CHARS, k=6))    # 62^6 ≈ 56 billion codes

    def encode(self, long_url: str) -> str:
        if long_url in self.url_to_code:
            return self.BASE + self.url_to_code[long_url]  # idempotent: same URL → same code
        code = self._generate_code()
        while code in self.code_to_url:     # collision handling: regenerate on conflict
            code = self._generate_code()
        self.url_to_code[long_url] = code
        self.code_to_url[code] = long_url
        return self.BASE + code

    def decode(self, short_url: str) -> str:
        code = short_url.replace(self.BASE, "")
        return self.code_to_url[code]

Why two maps? encode needs to check if a URL is already stored (URL→code direction). decode needs to retrieve the original URL (code→URL direction). One map can't efficiently serve both directions.

Why check url_to_code first in encode? Idempotency — encoding the same URL twice should return the same short code, not two different codes pointing at the same destination.

Answer (Birthday Problem)

62^6 ≈ 56 billion possible codes. By the birthday problem, the expected number of URLs before the first collision is approximately √(56 × 10⁹) ≈ 237 000. At 237 000 stored URLs there is about a 50% chance of at least one collision. The while code in code_to_url loop handles this — it just regenerates until a fresh code is found. For typical interview use cases (much less than 237K URLs) this is essentially zero-collision.

---

Application: Design HashSet from scratch (LC #705)

Implement add(key), remove(key), contains(key) without using the built-in hash set.

class MyHashSet:
    def __init__(self):
        self.SIZE = 1000          # number of buckets
        self.buckets = [[] for _ in range(self.SIZE)]   # each bucket: a list (chaining)

    def _bucket(self, key: int) -> list:
        return self.buckets[key % self.SIZE]   # hash function: modulo

    def add(self, key: int) -> None:
        b = self._bucket(key)
        if key not in b:
            b.append(key)

    def remove(self, key: int) -> None:
        b = self._bucket(key)
        if key in b:
            b.remove(key)

    def contains(self, key: int) -> bool:
        return key in self._bucket(key)

Frame-by-frame: add(1000), add(2000), add(1)

SIZE = 1000

add(1000): bucket = 1000 % 1000 = 0  → buckets[0] = [1000]
add(2000): bucket = 2000 % 1000 = 0  → buckets[0] = [1000, 2000]  (chaining)
add(1):    bucket = 1    % 1000 = 1  → buckets[1] = [1]

contains(2000): bucket = 0, scan [1000, 2000] → True
remove(1000):   bucket = 0, remove → [2000]
contains(1000): bucket = 0, scan [2000] → False

The key design insight: key % SIZE is the hash function. With good SIZE and chaining, each bucket stays short — O(1) average operations.

---

When to use each key design

Situation	Key design	Example
Two strings are equivalent if same chars	sorted string or frequency tuple	Anagram grouping
Grid cell (row, col)	f"{row},{col}" or (row, col) tuple	Island problems, BFS grid
Multi-field object identity	tuple of fields	(name, dob) for person
Sequence identity (order matters)	tuple(sequence)	DP memoisation, state machines
Subarray/range	(left, right) tuple	Range queries
Bidirectional mapping	two dicts	TinyURL, bimap

---

The 4 custom hash pitfalls

---

Say it like a pro (interview one-liner)

"I need a custom hash key that maps equivalent objects to the same string or tuple, and different objects to different keys. I'll use [sorted string / frequency tuple / separator-delimited string / tuple of fields] as the canonical form, store it in a hash map, and get O(1) lookup."

---

---

Check yourself

Why does grouping anagrams with a 26-length frequency tuple work better than a sorted string for very long strings?

Sorting a string of length k costs O(k log k). Building the frequency array costs O(k) — one pass. For very long strings, O(k) vs O(k log k) is a meaningful improvement. The frequency tuple is also unambiguous — two strings that are anagrams will always produce the identical 26-element count array, regardless of character order.

In the custom HashSet implementation, why is a prime number a good choice for SIZE?

If SIZE shares common factors with many keys (e.g., SIZE=1000 with keys that are all multiples of 10), keys cluster into a small subset of buckets, making those buckets long and degrading operations toward O(n). A prime SIZE has no common factors with most key distributions, spreading keys more uniformly across all buckets. Common interview primes: 1009, 2003, 10007.

In TinyURL, why do you check `if long_url in url_to_code` at the start of encode?

Idempotency: if the same URL is encoded twice, it should return the same short code both times. Without the check, two different short codes would map to the same destination URL. Both would decode correctly, but the first code would become orphaned (url_to_code would overwrite it with the second code, so re-encoding the original URL would return the second code — inconsistent behaviour).

---

Practice problems

Problem	Difficulty	What to notice	Link
Group Anagrams	Medium	Canonical key: sorted string or frequency tuple	LC #49
Encode and Decode TinyURL	Medium	Two maps; idempotent encode; collision handling	LC #535
Design HashSet	Easy	Buckets + modulo hash; chaining for collisions	LC #705
Design HashMap	Easy	Same as HashSet but bucket stores (key, value) pairs	LC #706
Word Pattern	Easy	Bijection: word→char and char→word, two maps	LC #290
Find Duplicate Subtrees	Medium	Canonical key: serialised subtree string	LC #652

This completes Chapter 2 — Hashing (7 patterns). Next: Chapter 3 — Strings, starting with the two-pointer technique applied to string problems.