Back to Welcome 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

function countFrequency(arr) {
    const frequencyMap = new Map();
    
    for (const item of arr) {
        frequencyMap.set(item, (frequencyMap.get(item) || 0) + 1);
    }
    
    return frequencyMap;
}

// Example: Count letter frequency
const letters = "programming";

2. First Non-Repeating Character

function firstNonRepeatingChar(str) {
    // Create frequency map
    const charCount = new Map();
    
    // First pass: count frequencies
    for (const char of str) {
        charCount.set(char, (charCount.get(char) || 0) + 1);
    }
    
    // Second pass: find first char with count 1
    for (const char of str) {
        if (charCount.get(char) === 1) {
            return char;
        }
    }
    
    return null;
}

Implementation Examples

First Non-Repeating Character

function firstNonRepeatingChar(str) {
    // Create frequency map
    const charCount = new Map();
    
    // First pass: count frequencies
    for (const char of str) {
        charCount.set(char, (charCount.get(char) || 0) + 1);
    }
    
    // Second pass: find first char with count 1
    for (const char of str) {
        if (charCount.get(char) === 1) {
            return char;
        }
    }
    
    return null;
}

Example Usage:

console.log(firstNonRepeatingChar("leetcode"));    // "l"
console.log(firstNonRepeatingChar("aabbcc"));     // null
console.log(firstNonRepeatingChar("aabbc"));      // "c"

Optimized Single-Pass Solution

function firstNonRepeatingCharOptimized(str) {
    const charInfo = new Map();
    
    // Single pass: track both count and first position
    for (let i = 0; i < str.length; i++) {
        const char = str[i];
        if (!charInfo.has(char)) {
            charInfo.set(char, { count: 1, firstIndex: i });
        } else {
            const info = charInfo.get(char);
            info.count++;
        }
    }
    
    // Find character with count 1 and minimum index
    let result = null;
    let minIndex = str.length;
    
    for (const [char, info] of charInfo) {
        if (info.count === 1 && info.firstIndex < minIndex) {
            result = char;
            minIndex = info.firstIndex;
        }
    }
    
    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"]
]