How to Choose the Right Hash Map Key (The Decision Framework)

You're solving "Group Anagrams." You know you need a hash map to group words... but what's the key?

Sorted string? Character count? Some hash? You're not sure, so you guess.

This is one of the most common points of confusion in hash map problems: choosing the right key.

This guide gives you a systematic 3-step framework for key selection that works every time.

The Three Requirements for Good Keys

A good hash map key must satisfy three properties:

1. Uniqueness

Rule: Different groups must have different keys.

Example: For anagrams, "eat" and "tea" should have the same key (same group), but "eat" and "tan" should have different keys (different groups).

2. Immutability

Rule: Keys must be immutable (can't change after creation).

Why: Hash maps compute a hash code when you insert. If the key changes, the hash code becomes invalid.

Immutable types: strings, numbers, tuples, frozensets
Mutable types: lists, sets, dicts (can't use as keys!)

3. Hashability

Rule: Keys must be hashable (can be converted to a hash code).

In practice: If it's immutable, it's usually hashable.

The Decision Framework

Step 1: What makes items belong together?

Identify the grouping property.

Examples:

• Anagrams: Same characters (different order)
• Isomorphic strings: Same pattern
• Numbers: Same sum of digits

Step 2: How can I represent that property?

Choose a canonical representation.

Options:

• Sorted string
• Character count tuple
• Pattern string
• Tuple of properties
• Custom hash

Step 3: Is it immutable and unique?

Verify your key satisfies all three requirements.

Common Key Types

Type 1: Sorted String

Use for: Anagrams, permutations

# Group anagrams
key = ''.join(sorted(word))

"eat" → "aet"
"tea" → "aet"  # Same key ✓
"tan" → "ant"  # Different key ✓

Pros: Simple, works for any characters
Cons: O(k log k) where k = string length

Type 2: Character Count Tuple

Use for: Anagrams (optimized), frequency-based grouping

# Group anagrams (faster for long words)
count = [0] * 26
for char in word:
    count[ord(char) - ord('a')] += 1
key = tuple(count)

"eat" → (1,0,0,0,1,0,...,1,0)
"tea" → (1,0,0,0,1,0,...,1,0)  # Same key ✓

Pros: O(k) time, faster for long words
Cons: Only works for known alphabet (a-z)

Type 3: Pattern String

Use for: Isomorphic strings, structural similarity

# Group isomorphic strings
def get_pattern(s):
    mapping = {}
    pattern = []
    next_id = 0
    
    for char in s:
        if char not in mapping:
            mapping[char] = next_id
            next_id += 1
        pattern.append(str(mapping[char]))
    
    return ','.join(pattern)

"egg" → "0,1,1"
"add" → "0,1,1"  # Same pattern ✓
"foo" → "0,1,1"  # Same pattern ✓
"bar" → "0,1,2"  # Different pattern ✓

Pros: Captures structure
Cons: More complex to compute

Type 4: Tuple of Properties

Use for: Multi-criteria grouping

# Group by (length, first character)
key = (len(word), word[0] if word else '')

"apple" → (5, 'a')
"ant" → (3, 'a')  # Different key (different length)
"apply" → (5, 'a')  # Same key ✓

Pros: Flexible, handles multiple criteria
Cons: Need to ensure all parts are hashable

Type 5: Frozen Set

Use for: Unordered collections

# Group by set of characters (ignoring frequency)
key = frozenset(word)

"aab" → frozenset({'a', 'b'})
"aba" → frozenset({'a', 'b'})  # Same key ✓
"abc" → frozenset({'a', 'b', 'c'})  # Different key ✓

Pros: Unordered, immutable
Cons: Loses frequency information

Examples by Problem

Example 1: Group Anagrams (LeetCode 49)

Grouping property: Same characters (different order)

Option A: Sorted string

def groupAnagrams(strs):
    groups = defaultdict(list)
    for word in strs:
        key = ''.join(sorted(word))  # O(k log k)
        groups[key].append(word)
    return list(groups.values())

Option B: Character count

def groupAnagrams(strs):
    groups = defaultdict(list)
    for word in strs:
        count = [0] * 26
        for char in word:
            count[ord(char) - ord('a')] += 1
        key = tuple(count)  # O(k)
        groups[key].append(word)
    return list(groups.values())

Which to use: Option A (simpler), Option B (faster for long words)

Example 2: Isomorphic Strings (LeetCode 205)

Grouping property: Same pattern

def isIsomorphic(s, t):
    def pattern(string):
        mapping = {}
        result = []
        next_id = 0
        for char in string:
            if char not in mapping:
                mapping[char] = next_id
                next_id += 1
            result.append(mapping[char])
        return tuple(result)
    
    return pattern(s) == pattern(t)

Key: Pattern tuple (e.g., (0, 1, 1) for "egg")

Example 3: Group Shifted Strings (LeetCode 249)

Grouping property: Same shift pattern

def groupStrings(strings):
    def get_key(s):
        if not s:
            return ()
        # Compute shifts relative to first character
        shifts = []
        for i in range(1, len(s)):
            shift = (ord(s[i]) - ord(s[i-1])) % 26
            shifts.append(shift)
        return tuple(shifts)
    
    groups = defaultdict(list)
    for s in strings:
        key = get_key(s)
        groups[key].append(s)
    return list(groups.values())

Key: Tuple of relative shifts

Common Mistakes

Mistake 1: Using Mutable Keys

❌ Wrong:

# List is mutable!
key = sorted(word)  # Returns list
groups[key] = []  # TypeError!

✅ Correct:

# Convert to immutable
key = ''.join(sorted(word))  # String
# Or
key = tuple(sorted(word))  # Tuple

Mistake 2: Non-Unique Keys

❌ Wrong:

# Using first character as key for anagrams
key = word[0]
# "eat" and "egg" would have same key!

✅ Correct:

# Use sorted characters
key = ''.join(sorted(word))

Mistake 3: Forgetting Edge Cases

❌ Wrong:

# Crashes on empty string
key = word[0]

✅ Correct:

# Handle empty
key = word[0] if word else ''

Mistake 4: Overly Complex Keys

❌ Wrong (overkill):

# Using hash of sorted string
import hashlib
key = hashlib.md5(''.join(sorted(word)).encode()).hexdigest()

✅ Correct (simple):

# Just use sorted string
key = ''.join(sorted(word))

Decision Checklist

When choosing a key, ask:

1. What makes items belong together?

   • Identify the grouping property

2. How can I represent that uniquely?

   • Choose canonical representation

3. Is it immutable?

   • Strings, tuples, numbers ✓
   • Lists, sets, dicts ✗

4. Is it efficient to compute?

   • O(k) or O(k log k) is usually fine
   • Avoid O(k²) or worse

5. Does it handle edge cases?

   • Empty strings
   • Single characters
   • Special characters

Quick Reference

Summary

Choosing the right hash map key is systematic, not guesswork.

The framework:

1. Identify grouping property
2. Choose canonical representation
3. Verify: unique, immutable, hashable

Common key types:

• Sorted string (anagrams)
• Character count tuple (anagrams, optimized)
• Pattern tuple (isomorphic)
• Property tuple (multi-criteria)
• Frozen set (unordered)

The rule: Use the simplest key that uniquely identifies each group.

Next steps:

• Study grouping pattern
• Learn common mistakes
• Master the complete hash map guide

Choose the right key, and grouping problems become straightforward.