Coding Patterns - HashMaps

Intuition

HashMaps (also called dictionaries or hash tables) are fundamental data structures that allow for fast average-time operations for insert, delete, and lookup all in O(1). Instead of searching through an array linearly, HashMaps leverage hashing to jump directly to the value associated with a key. This efficiency makes them valuable in algorithm design, especially in problems where performance matters.

Think of a HashMap as a highly organized locker system: each key points directly to a unique locker where its value is stored, so retrieval is instant.

HashMap Strategies

1. Frequency Counting

• Count occurrences of elements in arrays, strings, or lists.

• Essential for problems like anagram checks, majority elements, and word counts.

2. Duplicate Detection

• Store seen elements to instantly check if an item has appeared before.

3. Mapping Relationships

• Connect two entities, such as employee → manager or word → index.

4. Caching Results (Memoization)

• Save results of expensive computations for reuse in dynamic programming or recursion.

5. Grouping / Classification

• Group items by shared properties, such as grouping words by sorted characters for anagram clusters.

When To Use HashMaps

Use a HashMap when:

• You need constant-time lookups.

• The problem involves counting, grouping, or detecting duplicates.

• You want to quickly test membership (whether an element exists).

• You need a key-value relationship, not just sequential access.

Real-World Example

Autocomplete in Search Engines: When you type a few letters into a search bar, the system instantly suggests completions. Behind the scenes, HashMaps may store mappings from prefixes to word lists. For example, typing “app” instantly fetches [“apple”, “application”, “appetizer”] without scanning the full dictionary.

Another example: Counting word frequency in large text streams for trending topics on social media platforms.

Coding Example: Word Frequency Counter

def word_frequency(text):
    freq = {}
    for word in text.split():
        word = word.lower()
        freq[word] = freq.get(word, 0) + 1
    return freq

# Example usage
text = "HashMaps are powerful powerful tools"
print(word_frequency(text))
# Output: {'hashmaps': 1, 'are': 1, 'powerful': 2, 'tools': 1}

Framework

1. Identify the Key: Decide what needs to be tracked (e.g., element, character, substring).

2. Initialize HashMap: Start with an empty dictionary.

3. Update While Traversing: For each item, insert or update the HashMap.

4. Check Conditions: Use the HashMap to detect duplicates, compare counts, or retrieve values.

5. Return or Process Results: Format and return the final result as required.

Key Points

• HashMaps provide instant lookups with average O(1) performance.

• Ideal for problems involving frequency, duplicates, and mapping.

• Widely used in memoization and dynamic programming.

• Real-world systems like search engines and caches rely on HashMaps.

Practice Exercise

Exercise: Write a function to determine if two strings are anagrams using a HashMap.

Sample Solution:

def are_anagrams(s1, s2):
    if len(s1) != len(s2):
        return False

    count = {}
    for ch in s1:
        count[ch] = count.get(ch, 0) + 1

    for ch in s2:
        if ch not in count:
            return False
        count[ch] -= 1
        if count[ch] == 0:
            del count[ch]

    return len(count) == 0

print(are_anagrams("listen", "silent"))  # True
print(are_anagrams("hello", "world"))    # False

Next Chapter