Back to Main ACS Page

Module 3: Advanced Hash Table Applications

Master advanced hash table techniques and learn how to solve complex problems efficiently using hash-based data structures.

Learning Objectives

Core Concepts

Advanced hash table optimization techniques
Common hash table patterns and use cases
Time and space complexity analysis
Problem-solving strategies with hash tables

Key Skills

Identify hash table-suitable problems
Implement efficient hash-based solutions
Handle collisions and edge cases
Optimize space usage

Common Applications

Frequency Counting

Track occurrences of elements in arrays, strings, or streams of data.

Caching

Store frequently accessed data for quick retrieval.

De-duplication

Efficiently remove or identify duplicate items.

Hash Table Data Structures in JavaScript

Data Structure	Main Features	When to Use	Performance
Object	Built-in hash-based structure String/Symbol keys only Unordered	Simple key-value mapping with string keys	Average O(1) for access, insertion, deletion
Map	Can use any value as key Maintains insertion order Iterable	When key order matters or when using non-string keys	Average O(1) for access, insertion, deletion
Set	Collection of unique values No key-value pairs Maintains insertion order	When you need to track unique values without associated keys	Average O(1) for access, insertion, deletion
WeakMap / WeakSet	Allows for automatic garbage collection Only objects as keys Not iterable	When tracking object references that should be garbage collected	Average O(1) for access, insertion, deletion

Advanced Hash Table Techniques

Key Concepts Covered

Finding first non-repeating character
Two-pass vs. single-pass solutions
Space-time complexity tradeoffs
Handling edge cases

Hash Table Problem-Solving Patterns

1. Count Frequency

def count_frequency(arr):
    frequency_map = {}
    for item in arr:
        frequency_map[item] = frequency_map.get(item, 0) + 1
    return frequency_map

# Example: Count letter frequency
letters = "programming"
print(count_frequency(letters))

2. First Non-Repeating Character

def first_non_repeating_char(s):
    # Create frequency map
    char_count = {}
    # First pass: count frequencies
    for char in s:
        char_count[char] = char_count.get(char, 0) + 1
    # Second pass: find first char with count 1
    for char in s:
        if char_count[char] == 1:
            return char
    return None

Implementation Examples

First Non-Repeating Character

def first_non_repeating_char(s):
    # Create frequency map
    char_count = {}
    # First pass: count frequencies
    for char in s:
        char_count[char] = char_count.get(char, 0) + 1
    # Second pass: find first char with count 1
    for char in s:
        if char_count[char] == 1:
            return char
    return None

Example Usage:

print(first_non_repeating_char("leetcode"))    # "l"
print(first_non_repeating_char("aabbcc"))     # None
print(first_non_repeating_char("aabbc"))      # "c"

Optimized Single-Pass Solution

def first_non_repeating_char_optimized(s):
    char_info = {}
    # Single pass: track both count and first position
    for i, char in enumerate(s):
        if char not in char_info:
            char_info[char] = {'count': 1, 'first_index': i}
        else:
            char_info[char]['count'] += 1
    # Find character with count 1 and minimum index
    result = None
    min_index = len(s)
    for char, info in char_info.items():
        if info['count'] == 1 and info['first_index'] < min_index:
            result = char
            min_index = info['first_index']
    return result

Practice Exercises

Exercise 1: First Repeating Character

Implement a function that finds the first character that repeats in a string.

Example:

firstRepeatingChar("abcdeef") → "e"
firstRepeatingChar("abcde") → null
firstRepeatingChar("abba") → "b"

Exercise 2: Character Frequency Map

Create a function that returns a map of character frequencies in descending order.

Example:

charFrequency("programming") →
{
    "g": 2,
    "r": 2,
    "m": 2,
    "p": 1,
    "o": 1,
    "a": 1,
    "i": 1,
    "n": 1
}

Exercise 3: Anagram Groups

Write a function that groups anagrams together from an array of strings.

Example:

groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]) →
[
    ["eat", "tea", "ate"],
    ["tan", "nat"],
    ["bat"]
]