Dictionary (Từ điển / Bản đồ / Associative Array / Map) là cấu trúc dữ liệu trừu tượng lưu trữ tập hợp cặp (Key, Value) với điều kiện mỗi Key xuất hiện tối đa một lần (Unique Keys).
Các triển khai phổ biến (Implementation)
| Loại | Cơ chế | Độ phức tạp (Trung bình) | Đặc điểm |
|---|---|---|---|
| Hash Table | Hash function + Array + Collision handling (Chaining/Open Addressing) | O(1) Insert/Search/Delete | Nhanh nhất, phổ biến nhất (JS Object/Map dùng này) |
| Tree-Based (BST, AVL, Red-Black) | Cây tìm kiếm nhị phân cân bằng | O(log n) | Key có thứ tự (Sorted), Range query tốt |
| List-based (Array/Linked List) | Duyệt tuyến tính | O(n) | Đơn giản, chỉ dùng cho dữ liệu rất nhỏ |
Khi nào NÊN dùng Dictionary?
- ✅ Cần tra cứu nhanh (Fast Lookup) O(1): Cache, Index database, Symbol table, Router, Config.
- ✅ Key duy nhất (Unique Keys).
- ✅ Thứ tự không quan trọng (Map ES6 giữ insertion order, nhưng logic không phụ thuộc).
- ✅ Insert ít, Read nhiều (Insert chậm hơn Tree do hash/resize, Read O(1) nhanh hơn Tree O(log n)).
Khi nào KHÔNG nên dùng Dictionary?
- ❌ Cần duyệt theo thứ tự key (Sorted) -> Dùng Tree (Map trong C++/Java, hoặc array sorted + binary search).
- ❌ Key không unique (Multi-map) -> Dùng Map<Key, Array<Value>> hoặc MultiMap lib.
- ❌ Dữ liệu rất nhỏ (< 10 phần tử) -> Array linear search có thể nhanh hơn do overhead hash.
- ❌ Cần persistent/immutable structure -> Dùng thư viện (Immer, Immutable.js).
API Dictionary tiêu chuẩn (Methods)
- get(key): Lấy value theo key. Trả về value hoặc undefined/null.
- put(key, value) / set(key, value): Thêm hoặc cập nhật cặp key-value.
- has(key) / hasKey(key): Kiểm tra key tồn tại (Boolean).
- delete(key) / remove(key): Xóa cặp key-value. Trả về Boolean thành công.
- clear(): Xóa tất cả cặp key-value.
- keys(): Trả về tập hợp tất cả keys (Array/Set/Iterable).
- values(): Trả về tập hợp tất cả values.
- entries(): Trả về tập hợp cặp [key, value].
- size / length: Số lượng cặp key-value.
JavaScript cung cấp sẵn 2 Dictionary
| Đặc điểm | Object | Map (ES6) |
|---|---|---|
| Key type | String / Symbol | Bất kỳ (Object, Function, Primitive...) |
| Prototype pollution | Có rủi ro (__proto__) | An toàn (No prototype) |
| Size | Object.keys(obj).length | map.size (O(1)) |
| Iterable | Không (Object.keys/values/entries) | Có (for...of, forEach) |
| Insert/Delete perf | Chậm hơn (Hidden class) | Nhanh, ổn định |
| JSON Serialize | Native JSON.stringify | Cần convert Array.from(map) |
| Order | Insertion order (String key, ES2015+) | Insertion order (Luôn) |
Best Practice
- Mặc định dùng
Mapcho Dictionary logic nghiệp vụ, dynamic data, performance critical. - Dùng Object cho: Record tĩnh (DTO, Config, Schema cố định), cần
JSON.stringifytrực tiếp, key string đơn giản. - Tránh dùng Object làm Dictionary nếu key do user nhập (rủi ro
__proto__,constructor,toString). - Luôn dùng
map.has(key)/obj.hasOwnProperty(key)để check tồn tại.
Tóm lại: Dictionary = Cặp Key-Value unique. JS có Object (legacy) và Map (ES6, chuẩn, mạnh). Triển khai gốc: Hash Table (O(1)). API chuẩn: get, set/put, has, delete, clear, keys, values, entries, size. Ưu tiên Map cho Dictionary động.