Hash Map
Hash Map là cấu trúc dữ liệu lưu cặp khoá → giá trị, cho phép tra cứu, thêm và xoá ở thời gian trung bình O(1). Đây thường là công cụ đầu tiên nên nghĩ tới khi bài hỏi "đã từng thấy chưa", "đếm số lần", hay "tìm phần bù của một giá trị".
Sức mạnh của Hash Map đến từ việc đổi bộ nhớ lấy tốc độ: thay vì quét lại mảng mỗi lần (O(n)), ta ghi nhớ trước những gì đã gặp rồi tra trong một bước. Điều cần lưu ý là chọn đúng khoá và xử lý gọn trường hợp khoá chưa tồn tại.
Như tủ locker phòng gym — biết số tủ là lấy đồ ra ngay, không phải đi mở từng tủ kiểm tra.
Dấu hiệu nhận biết
Gặp những từ khoá này trong đề → nghĩ ngay đến Hash Map
| Từ khoá trong đề | Tại sao gợi đến chủ đề này |
|---|---|
| tra cứu O(1) | Cần kiểm tra / lấy giá trị nhanh nhất |
| đếm tần suất | Đếm số lần xuất hiện của ký tự hoặc phần tử |
| tìm cặp tổng = X | Lưu complement đã thấy rồi check O(1) |
| phát hiện duplicate | Dùng Set/Map ghi nhớ đã thấy |
| gom anagram | Hash key = chuỗi đã sắp xếp |
Khi nào dùng
4 tình huống điển hình cần nghĩ đến chủ đề này
Cần tra cứu/đếm/kiểm tra tồn tại với O(1) trung bình
Cần đếm tần suất ký tự / phần tử
Cần map từ key này sang giá trị khác (anagram, isomorphic strings)
Cần phát hiện duplicate hoặc complement
Khi nào KHÔNG dùng
3 tình huống chủ đề này không phù hợp — biết để tránh overuse
Mảng đã sorted: Two-Pointer rẻ hơn về bộ nhớ (O(1) thay vì O(n))
Domain rất nhỏ và cố định (vd 26 chữ cái): dùng array index nhanh hơn, ít overhead hashing
Cần duyệt theo thứ tự sắp xếp: TreeMap / Sorted Map đúng bản chất hơn HashMap
Hình minh hoạ
Sơ đồ thể hiện cách giải của chủ đề này.
Hàm hash() chuyển key thành chỉ số mảng — tra cứu trực tiếp, không cần duyệt mảng.
Code mẫu
Hầu hết bài cùng chủ đề dùng chung mẫu này — copy rồi điền phần logic riêng của bài.
function pattern(input: T[]): R {
const map = new Map<K, V>() // hoặc: const seen = new Set<K>()
for (const item of input) {
// 1. Check trong map trước
if (map.has(someKey(item))) {
// dùng giá trị đã có
}
// 2. Cập nhật map
map.set(someKey(item), someValue(item))
}
return assembleResult(map)
}Recap
Tổng hợp nhanh — đọc lại trước phỏng vấn
Điểm chính
Map.set(key, value) và Map.get(key) trung bình O(1)
Trong JS dùng plain object hoặc Map.
Map giữ thứ tự insert; object cũng giữ với key chữ, nhưng key dạng số bị sắp xếp lại — cần thứ tự ổn định thì dùng Map.
Set khi chỉ cần "tồn tại không" (không cần value) — tiết kiệm bộ nhớ.
Map khi cần lưu cả key + value.
Hash collision = 2 key khác nhau hash về cùng slot.
- Hai cách giải: Chaining (mỗi slot là list các (key,value), tra cứu tuyến tính trong slot) hoặc Open addressing (tìm slot trống kế tiếp theo công thức probing).
- Cả 2 cùng worst-case O(n), nhưng với hash function tốt + load factor < 0.75 thì cực hiếm.
Load factor = n/m (số phần tử / số slot).
Khi vượt ngưỡng (~0.75) → auto-rehash mở rộng bảng, cost O(n) amortized.
Lỗi thường gặp
Quên check key tồn tại trước khi tăng count (NaN bug)
Dùng object cho key là object — bị stringify, mất key
Coi load factor không quan trọng — khi load factor lớn (> 0.75) collision tăng nhanh, thao tác chậm hơn nhiều
Độ phức tạp
Time O(1) average / O(n) worst, Space O(n)Bài luyện theo chủ đề này
Phân theo độ khó — luyện tuần tự cho chắc tay