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

public static Map<Character, Integer> countFrequency(String str) {
    Map<Character, Integer> frequencyMap = new HashMap<>();
    for (char c : str.toCharArray()) {
        frequencyMap.put(c, frequencyMap.getOrDefault(c, 0) + 1);
    }
    return frequencyMap;
}

// Example: Count letter frequency
String letters = "programming";
System.out.println(countFrequency(letters));

2. First Non-Repeating Character

public static Character firstNonRepeatingChar(String str) {
    Map<Character, Integer> charCount = new HashMap<>();
    for (char c : str.toCharArray()) {
        charCount.put(c, charCount.getOrDefault(c, 0) + 1);
    }
    for (char c : str.toCharArray()) {
        if (charCount.get(c) == 1) {
            return c;
        }
    }
    return null;
}

Implementation Examples

First Non-Repeating Character

public static Character firstNonRepeatingChar(String str) {
    // Create frequency map
    Map<Character, Integer> charCount = new HashMap<>();
    
    // First pass: count frequencies
    for (char c : str.toCharArray()) {
        charCount.put(c, charCount.getOrDefault(c, 0) + 1);
    }
    
    // Second pass: find first char with count 1
    for (char c : str.toCharArray()) {
        if (charCount.get(c) == 1) {
            return c;
        }
    }
    
    return null;
}

Example Usage:

System.out.println(firstNonRepeatingChar("leetcode"));    // 'l'
System.out.println(firstNonRepeatingChar("aabbcc"));     // null
System.out.println(firstNonRepeatingChar("aabbc"));      // 'c'

Optimized Single-Pass Solution

public static Character firstNonRepeatingCharOptimized(String str) {
    Map<Character, int[]> charInfo = new HashMap<>();
    for (int i = 0; i < str.length(); i++) {
        char c = str.charAt(i);
        if (!charInfo.containsKey(c)) {
            charInfo.put(c, new int[]{1, i});
        } else {
            charInfo.get(c)[0]++;
        }
    }
    Character result = null;
    int minIndex = str.length();
    for (Map.Entry<Character, int[]> entry : charInfo.entrySet()) {
        if (entry.getValue()[0] == 1 && entry.getValue()[1] < minIndex) {
            result = entry.getKey();
            minIndex = entry.getValue()[1];
        }
    }
    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"]
]