Buổi 07 — Hash Table

Navigation

← 06-Sorting-Merge-Quick | → 08-Tree-DFS-BFS Giai đoạn: Big Tech Foundation | Độ khó: ⭐⭐⭐

1. Analogy & Context

Thư viện với catalog tra cứu

Thay vì dạo qua từng kệ sách để tìm cuốn bạn cần, bạn tra card catalog: nhập tên sách, catalog trả về ngay vị trí kệ chính xác — ví dụ “Kệ B, hàng 3, vị trí 7”. Bạn đi thẳng đến đó. Hash function chính là card catalog: ánh xạ tên sách (key) → vị trí kệ (index).

Nhưng điều gì xảy ra khi hai cuốn sách được map đến cùng một vị trí? Đây là hash collision. Chiến lược “chaining” giải quyết bằng cách đặt một mini-kệ nhỏ tại vị trí đó — các cuốn sách cùng hash được xếp chồng lên nhau, tìm kiếm trong mini-kệ này là $O (k)$ với $k$ là số phần tử trong chain.

Key: "Harry Potter"
    ↓ hash function
hash("Harry Potter") % 16 = 7
    ↓
Slot [7] → [("Harry Potter", location_B3_7)]

Key: "Lord of the Rings"  → hash % 16 = 7 (collision!)
Slot [7] → [("Harry Potter", loc1) → ("Lord of the Rings", loc2)]
             ↑ chaining: linked list tại slot 7

Tại sao Hash Table quan trọng tại FAANG?

Operation	Array	Sorted Array	Hash Table
Search	$O (N)$	$O (lo g N)$	$O (1)$ avg
Insert	$O (1)$	$O (N)$	$O (1)$ avg
Delete	$O (N)$	$O (N)$	$O (1)$ avg

$O (N)$ search → $O (1)$ search là sự khác biệt giữa TLE và Accepted trên FAANG interview.

2. The FAANG Standard

Hash Table là "chìa khóa vạn năng" của FAANG

“Two Sum” — bài phổ biến nhất trong FAANG warm-up — đang test xem bạn có biết dùng HashMap không. Câu trả lời $O (N^{2})$ nested loop sẽ fail. Câu trả lời $O (N)$ HashMap sẽ pass.

Bốn pattern cốt lõi của Hash Table:

Two Sum Pattern: complement = target - num, tra cứu complement trong map $O (1)$
Frequency Counting: đếm xuất hiện của mỗi phần tử → map.set(key, (map.get(key) ?? 0) + 1)
Grouping: nhóm phần tử theo property → if (!map.has(key)) map.set(key, []) → map.get(key)!.push(item)
Prefix Sum + Map: subArraySumEqualsK — lưu prefix sum frequencies để query $O (1)$

JavaScript: Map vs Object vs Set

Map: key-value, key có thể là bất kỳ type. Dùng Map trong interview.

Object {}: key tự động convert sang string — nguy hiểm với số keys

Set: chỉ lưu unique values, check existence $O (1)$ . Dùng khi không cần lưu value.

Rule: Luôn dùng Map và Set thay vì {} trong TypeScript interview

3. Visual Thinking (Mermaid)

3.1 Hash Function: Key → Hash → Index

graph LR
    subgraph Keys["Keys (input)"]
        K1["'apple'"]
        K2["'banana'"]
        K3["'cherry'"]
        K4["'date'"]
    end

    subgraph Hash["Hash Function"]
        H["hash(key) % tableSize"]
    end

    subgraph Table["Hash Table (size=8)"]
        S0["[0]: empty"]
        S1["[1]: banana→2"]
        S2["[2]: empty"]
        S3["[3]: apple→5, cherry→8"]
        S4["[4]: empty"]
        S5["[5]: date→1"]
        S6["[6]: empty"]
        S7["[7]: empty"]
    end

    K1 --> Hash
    K2 --> Hash
    K3 --> Hash
    K4 --> Hash
    Hash --> S1
    Hash --> S3
    Hash --> S5

    note["apple và cherry → slot 3 (collision!)<br/>Giải quyết bằng chaining"]

3.2 Collision Resolution: Chaining vs Open Addressing

graph TD
    subgraph Chaining["Chaining (LinkedList tại mỗi slot)"]
        C0["Slot 3: → [apple,5] → [cherry,8] → null"]
        C1["Ưu điểm: đơn giản, handle nhiều collision tốt"]
        C2["Nhược điểm: extra memory cho pointers, cache-unfriendly"]
    end

    subgraph OpenAddr["Open Addressing (Linear Probing)"]
        O0["Slot 3 bị dùng → thử slot 4, 5, 6..."]
        O1["Ưu điểm: cache-friendly, không cần extra memory"]
        O2["Nhược điểm: clustering, xấu khi load factor cao"]
    end

    subgraph LoadFactor["Load Factor = n/m (n=keys, m=slots)"]
        L1["Load factor < 0.7 → performance OK"]
        L2["Load factor > 0.7 → rehash (double size)"]
        L3["Rehashing: O(N) — nhưng amortized O(1)"]
    end

3.3 Two Sum với HashMap — Quá trình Lookup

graph TD
    A["nums=[2,7,11,15], target=9"] --> B

    B["i=0, num=2<br/>complement = 9-2 = 7<br/>map.has(7)? NO<br/>map.set(2, 0)"] --> C

    C["i=1, num=7<br/>complement = 9-7 = 2<br/>map.has(2)? YES → map.get(2)=0<br/>return [0, 1] ✓"] --> D["DONE"]

    E["map state:<br/>{2→0}"]

    style D fill:#1a4731,color:#fff
    style C fill:#1e3a5f,color:#fff

4. TypeScript Template

4.1 Manual Hash Table với Chaining

/**
 * Hash Table tự implement — để hiểu internals
 * Trong interview, dùng JavaScript's built-in Map
 */
class HashTable<K, V> {
    private buckets: Array<Array<[K, V]>>;
    private size: number;
    private count: number = 0;
 
    constructor(size: number = 16) {
        this.size = size;
        this.buckets = Array.from({ length: size }, () => []);
    }
 
    private hash(key: K): number {
        const str = String(key);
        let hash = 0;
        for (let i = 0; i < str.length; i++) {
            // Polynomial rolling hash
            hash = (hash * 31 + str.charCodeAt(i)) % this.size;
        }
        return hash;
    }
 
    set(key: K, value: V): void {
        const idx = this.hash(key);
        const bucket = this.buckets[idx];
 
        for (const pair of bucket) {
            if (pair[0] === key) {
                pair[1] = value; // update existing
                return;
            }
        }
 
        bucket.push([key, value]); // insert new
        this.count++;
 
        // Rehash if load factor > 0.7
        if (this.count / this.size > 0.7) this.rehash();
    }
 
    get(key: K): V | undefined {
        const idx = this.hash(key);
        const bucket = this.buckets[idx];
        return bucket.find(([k]) => k === key)?.[1];
    }
 
    private rehash(): void {
        const old = this.buckets;
        this.size *= 2;
        this.buckets = Array.from({ length: this.size }, () => []);
        this.count = 0;
        for (const bucket of old) {
            for (const [k, v] of bucket) this.set(k, v);
        }
    }
}

4.2 Two Sum — Canonical HashMap Usage

/**
 * LeetCode #1 — Two Sum
 *
 * Brute force: O(N²) — nested loop kiểm tra từng cặp
 * HashMap: O(N) — với mỗi num, tìm complement (target - num) trong map
 *
 * Pattern: "One pass" — vừa lookup vừa insert
 * Key: lookup trước insert để tránh dùng cùng element hai lần
 *
 * Time: O(N) | Space: O(N)
 */
function twoSum(nums: number[], target: number): number[] {
    // map: value → index
    const map = new Map<number, number>();
 
    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];
 
        if (map.has(complement)) {
            return [map.get(complement)!, i];
        }
 
        // Insert AFTER checking — tránh dùng cùng index hai lần
        // Ví dụ: nums=[3,3], target=6 → đúng phải return [0,1]
        // Nếu insert trước: i=0, map={3:0}, check has(3)→YES → return [0,0] (SAI)
        map.set(nums[i], i);
    }
 
    return []; // theo constraint của LeetCode, luôn có answer
}

4.3 Group Anagrams — Sorted Key as Hash

/**
 * LeetCode #49 — Group Anagrams
 * Nhóm các strings là anagram của nhau
 *
 * Key insight: Hai strings là anagram khi và chỉ khi sorted version giống nhau
 * "eat" → "aet", "tea" → "aet", "tan" → "ant"
 * → Map: sorted string → [list of original strings]
 *
 * Alternative: dùng character frequency array [0,1,0,...] làm key (O(N) thay vì O(N log N))
 *
 * Time: O(N × K log K) — N strings, K độ dài trung bình | Space: O(N × K)
 */
function groupAnagrams(strs: string[]): string[][] {
    const map = new Map<string, string[]>();
 
    for (const str of strs) {
        // sorted string làm key
        const key = str.split('').sort().join('');
 
        if (!map.has(key)) {
            map.set(key, []);
        }
        map.get(key)!.push(str);
    }
 
    return Array.from(map.values());
}
 
// Optimization: O(N × K) thay vì O(N × K log K) — dùng freq array làm key
function groupAnagramsOptimal(strs: string[]): string[][] {
    const map = new Map<string, string[]>();
 
    for (const str of strs) {
        const freq = new Array(26).fill(0);
        for (const ch of str) {
            freq[ch.charCodeAt(0) - 'a'.charCodeAt(0)]++;
        }
        const key = freq.join(','); // "1,0,0,...,1,0" — unique per anagram group
 
        if (!map.has(key)) map.set(key, []);
        map.get(key)!.push(str);
    }
 
    return Array.from(map.values());
}

4.4 Longest Consecutive Sequence — O(N) với Set

/**
 * LeetCode #128 — Longest Consecutive Sequence
 *
 * Tìm độ dài của dãy liên tiếp dài nhất trong unsorted array.
 * Yêu cầu: O(N) time.
 *
 * Suy nghĩ đầu tiên: Sort → O(N log N) — không đủ.
 *
 * Key insight với Set:
 * Chỉ bắt đầu đếm dãy từ phần tử LÀ ĐẦU DÃY — tức là num-1 KHÔNG có trong set.
 * → Mỗi phần tử chỉ được xét tối đa 2 lần:
 *   1. Kiểm tra xem có phải đầu dãy không
 *   2. Được count khi extend dãy từ đầu dãy
 * → Tổng: O(N)
 *
 * Time: O(N) | Space: O(N)
 */
function longestConsecutive(nums: number[]): number {
    // Bước 1: Đưa tất cả vào Set để lookup O(1)
    const numSet = new Set<number>(nums);
    let maxLength = 0;
 
    for (const num of numSet) {
        // Chỉ bắt đầu đếm nếu num LÀ ĐẦU DÃY
        // Tức là num-1 KHÔNG tồn tại trong set
        if (!numSet.has(num - 1)) {
            let currentNum = num;
            let length = 1;
 
            // Extend dãy về phía phải
            while (numSet.has(currentNum + 1)) {
                currentNum++;
                length++;
            }
 
            maxLength = Math.max(maxLength, length);
        }
        // Nếu num-1 tồn tại → num là phần tử giữa dãy
        // → bỏ qua, để tránh đếm lại dãy từ giữa
    }
 
    return maxLength;
}
 
/*
 * Walkthrough: nums = [100, 4, 200, 1, 3, 2]
 *
 * numSet = {100, 4, 200, 1, 3, 2}
 *
 * num=100: has(99)? NO → start counting
 *   has(101)? NO → length=1, maxLength=1
 *
 * num=4: has(3)? YES → skip (4 không phải đầu dãy)
 *
 * num=200: has(199)? NO → start counting
 *   has(201)? NO → length=1, maxLength=1
 *
 * num=1: has(0)? NO → start counting! (1 là đầu dãy [1,2,3,4])
 *   has(2)? YES → length=2, currentNum=2
 *   has(3)? YES → length=3, currentNum=3
 *   has(4)? YES → length=4, currentNum=4
 *   has(5)? NO → done, maxLength=4
 *
 * num=3: has(2)? YES → skip
 * num=2: has(1)? YES → skip
 *
 * return 4 ✓ (dãy [1,2,3,4])
 *
 * Tại sao O(N)?
 * - Outer loop: N lần
 * - Inner while: chỉ chạy cho "đầu dãy"
 * - Tổng bước inner while trên tất cả iterations = N (mỗi phần tử được count đúng 1 lần)
 * → Total = O(N) + O(N) = O(N) ✓
 */

4.5 Subarray Sum Equals K — Prefix Sum + Frequency Map

/**
 * LeetCode #560 — Subarray Sum Equals K
 *
 * Đếm số subarrays có tổng bằng k.
 *
 * Key insight: prefix sum!
 * Nếu prefixSum[j] - prefixSum[i] = k, thì subarray [i+1..j] có tổng = k
 * → Tương đương: với mỗi j, đếm số i mà prefixSum[i] = prefixSum[j] - k
 * → Dùng map để lưu: prefixSum value → số lần xuất hiện
 *
 * Time: O(N) | Space: O(N)
 */
function subarraySum(nums: number[], k: number): number {
    // map: prefixSum → frequency
    const prefixFreq = new Map<number, number>();
    prefixFreq.set(0, 1); // prefixSum=0 xuất hiện 1 lần (empty subarray từ đầu)
 
    let count = 0;
    let prefixSum = 0;
 
    for (const num of nums) {
        prefixSum += num;
 
        // Có bao nhiêu subarray kết thúc tại đây có tổng = k?
        const complement = prefixSum - k;
        count += prefixFreq.get(complement) ?? 0;
 
        // Lưu prefixSum hiện tại vào map
        prefixFreq.set(prefixSum, (prefixFreq.get(prefixSum) ?? 0) + 1);
    }
 
    return count;
}

4.6 Top K Frequent Elements — Map + Bucket Sort Trick

/**
 * LeetCode #347 — Top K Frequent Elements
 *
 * Approach 1: Map + Min-Heap → O(N log K)
 * Approach 2: Map + Bucket Sort → O(N) — tận dụng frequency bounded bởi N
 *
 * Bucket Sort trick:
 * bucket[i] = [tất cả elements với frequency = i]
 * Frequency tối đa = N → N+1 buckets
 * Duyệt bucket từ cuối (freq cao) → đủ K elements thì dừng
 *
 * Time: O(N) | Space: O(N)
 */
function topKFrequent(nums: number[], k: number): number[] {
    // Bước 1: Đếm frequency
    const freqMap = new Map<number, number>();
    for (const num of nums) {
        freqMap.set(num, (freqMap.get(num) ?? 0) + 1);
    }
 
    // Bước 2: Bucket sort — bucket[i] = elements với freq i
    const buckets: number[][] = Array.from({ length: nums.length + 1 }, () => []);
    for (const [num, freq] of freqMap) {
        buckets[freq].push(num);
    }
 
    // Bước 3: Thu thập K elements từ bucket freq cao nhất
    const result: number[] = [];
    for (let freq = buckets.length - 1; freq >= 1 && result.length < k; freq--) {
        result.push(...buckets[freq]);
    }
 
    return result.slice(0, k);
}

5. Complexity Deep-dive

Average vs Worst Case

Operation	Average	Worst Case	Nguyên nhân Worst
Insert	$O (1)$	$O (N)$	Tất cả keys collide → 1 bucket
Search	$O (1)$	$O (N)$	Search trong chain dài N
Delete	$O (1)$	$O (N)$	Tương tự search

Tại sao average là $O (1)$ ?

Với hash function tốt (uniform distribution), mỗi bucket có trung bình $α = N / M$ phần tử (load factor). Nếu $α = O (1)$ (giữ load factor thấp), search trong bucket là $O (1)$ .

Amortized O(1) cho N insertions

Khi rehash (double size):

N insertions ban đầu: $O (N)$ total
Rehash xảy ra khi đạt N/2, N, 2N, 4N, … phần tử
Chi phí rehash: N/2 + N + 2N + … ≤ 2N = $O (N)$
Amortized cost per insertion: $O (N) / N = O (1)$ ✓

Load Factor 0.75 — Lý do Java chọn 0.75

Load factor quá thấp (0.1) → tốn memory, rehash quá thường

Load factor quá cao (0.9) → collision nhiều, chain dài, performance suy giảm

0.75 là điểm cân bằng tối ưu giữa time và space

6. Edge Cases & Pitfalls

Pitfall #1 — Object {} với Number Keys: Coercion sang String

// SAI — Object coerces số thành string
const obj: Record<string, number> = {};
obj[1] = "one";   // key thực sự là "1" (string)
obj["1"] = "ONE"; // ghi đè lên key "1"!
console.log(obj[1]); // "ONE" — không phải "one"!
 
// ĐÚNG — Map giữ key type nguyên vẹn
const map = new Map<number, string>();
map.set(1, "one");
map.set("1", "ONE"); // key khác nhau! Map phân biệt 1 và "1"
console.log(map.get(1)); // "one" ✓

Pitfall #2 — map.get(key) falsy khi value là 0

const freqMap = new Map<number, number>();
freqMap.set(0, 0); // giả sử 0 xuất hiện 0 lần (hoặc chưa)
freqMap.set(5, 0); // 5 xuất hiện 0 lần
 
// SAI — fails khi value là 0 (falsy!)
if (freqMap.get(5)) {
    // Không vào đây vì 0 là falsy → logic sai!
}
 
// ĐÚNG — kiểm tra sự tồn tại bằng .has()
if (freqMap.has(5)) {
    const val = freqMap.get(5)!; // an toàn dùng ! vì đã check has()
}
 
// HOẶC — dùng nullish coalescing
const freq = freqMap.get(key) ?? 0; // trả về 0 nếu undefined, giữ 0 nếu value là 0

Pitfall #3 — Dùng Array làm Key trong Map

// SAI — Arrays so sánh bằng reference, không phải value
const map = new Map<number[], string>();
map.set([1, 2], "hello");
console.log(map.get([1, 2])); // undefined! — [1,2] mới !== [1,2] cũ
 
// ĐÚNG — Convert array thành string key
const map2 = new Map<string, string>();
map2.set([1, 2].join(','), "hello");
console.log(map2.get([1, 2].join(','))); // "hello" ✓
 
// HOẶC — dùng JSON.stringify cho nested structures
map2.set(JSON.stringify([1, 2]), "hello");

Pitfall #4 — Modifying Map While Iterating

const map = new Map([[1, 'a'], [2, 'b'], [3, 'c']]);
 
// SAI — undefined behavior: thêm/xóa keys khi đang forEach
map.forEach((val, key) => {
    if (key === 2) map.delete(key); // có thể skip key 3
    if (key === 1) map.set(4, 'd'); // có thể iterate key 4 hoặc không
});
 
// ĐÚNG — collect keys first, then modify
const keysToDelete = [...map.keys()].filter(k => k === 2);
for (const key of keysToDelete) map.delete(key);

Pitfall #5 — Set vs Map: Chọn Đúng Tool

// Set: chỉ cần biết "có tồn tại không?" — O(1) lookup
const visited = new Set<string>();
visited.add("A");
if (visited.has("A")) { /* ... */ }
 
// Map: cần lưu key-value pair
const distance = new Map<string, number>();
distance.set("A", 5);
const d = distance.get("A"); // 5
 
// Sai lầm thường gặp: dùng Map khi chỉ cần Set
// → tốn memory hơn, code dài hơn
const BAD = new Map<string, boolean>();
BAD.set("A", true); // Không cần boolean! Dùng Set thay thế.
 
const GOOD = new Set<string>();
GOOD.add("A");

7. Pattern Recognition

Từ khóa nhận dạng Hash Table

Two Sum pattern:

“Hai số / phần tử tổng bằng X” → Map: complement = target - current
“Pair / triplet với điều kiện” → Sort hoặc HashMap

Frequency Counting:

“Count occurrences”, “Find duplicate”, “Most frequent”
“First non-repeating element”
freq = new Map(); for x: freq.set(x, (freq.get(x)??0)+1)

Grouping:

“Group by property”, “Anagram grouping”, “Same pattern”
Key = canonical form (sorted, frequency array, normalized)

Prefix Sum + Map:

“Subarray sum equals K” (not necessarily contiguous range)
“Count subarrays with condition”
Pattern: if (map.has(prefixSum - k)) count += map.get(prefixSum - k)

Set for Existence Check:

“Longest consecutive”, “Find duplicate”, “Contains cycle”
Bất cứ khi nào câu hỏi là “có X tồn tại không?“

Decision Tree:
Cần lưu value? → Map
Chỉ cần check existence? → Set
Key là số nguyên bounded? → Array (faster than Map, O(1) access)

8. Top LeetCode Problems

#	Tên	Độ khó	Pattern	Ghi chú
LC-1 #1	Two Sum	Easy	HashMap complement	Bài FAANG warm-up kinh điển
LC-49 #49	Group Anagrams	Medium	Sorted key as hash	Canonical form technique
LC-128 #128	Longest Consecutive Sequence	Medium	Set + smart iteration	O(N) without sorting
LC-560 #560	Subarray Sum Equals K	Medium	Prefix sum + frequency map	Classic prefix sum pattern
LC-347 #347	Top K Frequent Elements	Medium	Map + bucket sort	O(N) bucket sort trick
LC-146 #146	LRU Cache	Medium	Map + Doubly Linked List	Map cho O(1) access
LC-380 #380	Insert Delete GetRandom O(1)	Medium	Map + Array	Kết hợp hai structures

Lộ trình học

#1 → master Two Sum pattern

#49 → hiểu “canonical key” technique

#128 → O(N) Set-based consecutive search

#560 → master prefix sum + map

#146 → LRU Cache (kết hợp Map + DLL — FAANG system design classic)

9. Self-Assessment Checklist

Kiểm tra mức độ thành thạo

Level 1 — Cơ bản:

Giải được Two Sum với HashMap trong O(N) từ đầu
Biết khi nào dùng Map vs Set vs Object
Hiểu được tại sao map.get(key) ?? 0 tốt hơn map.get(key) || 0
Implement được frequency counting pattern

Level 2 — Intermediate:

Giải được Group Anagrams với sorted key technique
Giải được Longest Consecutive Sequence với O(N) approach
Giải được Subarray Sum Equals K với prefix sum + map
Giải thích được tại sao load factor ảnh hưởng performance

Level 3 — FAANG-ready:

Implement được LRU Cache với Map + Doubly Linked List
Giải được #380 (Insert Delete GetRandom O(1)) — combining data structures
Thiết kế được hash function tự viết và handle collision
Phân tích được amortized O(1) cho N insertions với rehashing

Mental Model để nhớ

Khi thấy: “Tìm… trong O(N)” → nghĩ ngay đến HashMap/Set Khi thấy: “Two elements tổng bằng X” → Two Sum pattern, 1 pass HashMap Khi thấy: “Count / Group by” → HashMap làm frequency/grouping map Khi thấy: “Subarray sum condition” → Prefix sum + HashMap

Interview Gotcha

Luôn hỏi: “Input có thể có duplicate không?” và “Range của values là gì?”

Duplicates → có thể ảnh hưởng Two Sum (same element twice?)

Bounded range → có thể dùng Array thay Map (nhanh hơn)

Negative numbers → ảnh hưởng prefix sum logic

Tags: hash-table hashmap set frequency-counting FAANG prefix-sum Liên kết: 06-Sorting-Merge-Quick | 08-Tree-DFS-BFS | Pattern-Prefix-Sum | Pattern-Two-Sum-Variants

lthieu's notes

Explorer

07-Hash-Table

Buổi 07 — Hash Table

1. Analogy & Context

2. The FAANG Standard

3. Visual Thinking (Mermaid)

3.1 Hash Function: Key → Hash → Index

3.2 Collision Resolution: Chaining vs Open Addressing

3.3 Two Sum với HashMap — Quá trình Lookup

4. TypeScript Template

4.1 Manual Hash Table với Chaining

4.2 Two Sum — Canonical HashMap Usage

4.3 Group Anagrams — Sorted Key as Hash

4.4 Longest Consecutive Sequence — O(N) với Set

4.5 Subarray Sum Equals K — Prefix Sum + Frequency Map

4.6 Top K Frequent Elements — Map + Bucket Sort Trick

5. Complexity Deep-dive

Average vs Worst Case

Amortized O(1) cho N insertions

6. Edge Cases & Pitfalls

7. Pattern Recognition

8. Top LeetCode Problems

9. Self-Assessment Checklist

Graph View

Table of Contents

Backlinks