Java| HashMap | TreeMap | |
|---|---|---|
| Cấu trúc | Hash table (Java 8+: bucket nhiều entry → red-black tree) | Red-black tree |
get/put | O(1) trung bình | O(log n) |
| Thứ tự key | Không xác định | Sắp xếp |
| Null key | 1 cái | ❌ |
| Extra API | — | firstKey, floorKey, subMap, tailMap |
java
NavigableMap<String, Integer> tm = new TreeMap<>(Map.of("banana", 2, "apple", 1));
tm.subMap("b", "d"); // {banana=2}
tm.floorKey("car"); // "banana"Khi dùng:
- HashMap: default cho mọi lookup theo key.
- TreeMap: khi cần duyệt theo thứ tự key, range query, hoặc tìm key "gần nhất" (bảng biểu thuế).
- LinkedHashMap: O(1) như HashMap nhưng duyệt theo insertion order. Bật access-order=true → biến thành LRU cache chỉ vài dòng (override removeEldestEntry).
Thread-safe: dùng ConcurrentHashMap (lock bucket level). Tránh Hashtable (legacy) và Collections.synchronizedMap (lock toàn map).
Java 8+ method tiện:
java
map.merge(key, 1, Integer::sum); // counter pattern, gọn hơn get+put
map.computeIfAbsent(key, k -> new ArrayList<>()); // lazy init