Array vs Hash Map: đổi không gian lấy thời gian
Tìm một phần tử trong mảng theo giá trị phải quét lần lượt — O(n). Hash Map (object/Map trong JS) lưu theo cặp khoá–giá trị, tìm được ngay — O(1). Đây là đổi đổi lấy tốc độ, bài toán kinh điển nhất của CS.
// File: hashmap.js
// Mảng: phải quét hết để tìm
const users = [];
const byId = new Map(); // khoá = id
for (const u of fetchedUsers) {
users.push(u); // mảng thêm cuối nhanh
byId.set(u.id, u); // map: tra theo id tức thì
}
// users.find(x => x.id === 42) -> O(n)
// byId.get(42) -> O(1)
💡 Khi nào dùng cái nào
Cần giữ thứ tự, đếm, duyệt tuần tự → mảng. Cần “tra cứu nhanh theo khoá”, đánh dấu đã thấy chưa, đếm tần suất → Map/Set. Nhớ điều này là ăn điểm mọi vòng phỏng vấn.
Stack và Queue: hai hàng đợi phổ biến nhất
| Cấu trúc | Nguyên tắc | Ví dụ thực tế |
|---|---|---|
| Stack | LIFO — vào sau ra trước | Nút Back của trình duyệt, undo, ngăn xếp lời gọi hàm |
| Queue | FIFO — vào trước ra trước | Hàng đợi in, xử lý tác vụ nền, message queue |
Trong JS, array.push/pop mô phỏng stack; array.push/shift mô phỏng queue (nhưng shift chậm, trong thực tế dùng cấu trúc chuyên dụng hơn).
Thuật toán sắp xếp: biết một cách nhanh, hiểu tại sao
Với người đi làm, bạn hiếm khi tự viết sắp xếp (JS đã có sort). Điều quan trọng là hiểu độ phức tạp: một giải thuật O(n²) như bubble sort chết với 100.000 phần tử, trong khi O(n log n) như quicksort/merge sort chạy mượt.
| Thuật toán | Tốt nhất | Trung bình | Khi nào dùng |
|---|---|---|---|
| Bubble sort | O(n) | O(n²) | Chỉ để học khái niệm |
| Merge sort | O(n log n) | O(n log n) | Dữ liệu lớn, cần ổn định |
| Quicksort | O(n log n) | O(n log n) | Phổ biến trong thư viện thực tế |
| sort() của JS | — | O(n log n) | Dùng mặc định, đừng tự viết lại |
❓ Bạn cần kiểm tra nhanh một email đã từng đăng ký chưa trong danh sách 1 triệu email. Nên lưu danh sách đó ở đâu?
- Phân biệt O(n) và O(1) bằng lời
- Dùng được Map để tra cứu theo id
- Nói được Stack khác Queue thế nào
- Không tự viết lại sort() của ngôn ngữ