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 |
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:
map.merge(key, 1, Integer::sum); // counter pattern, gọn hơn get+put
map.computeIfAbsent(key, k -> new ArrayList<>()); // lazy init| HashMap | TreeMap | |
|---|---|---|
| Structure | Hash table (Java 8+: dense buckets become red-black trees) | Red-black tree |
get/put | O(1) average | O(log n) |
| Key order | Unspecified | Sorted |
| Null key | One allowed | ❌ |
| Extra API | — | firstKey, floorKey, subMap, tailMap |
NavigableMap<String, Integer> tm = new TreeMap<>(Map.of("banana", 2, "apple", 1));
tm.subMap("b", "d"); // {banana=2}
tm.floorKey("car"); // "banana"When to use:
- HashMap: default for key lookups.
- TreeMap: sorted iteration, range queries, "closest key" lookups (tax brackets).
- LinkedHashMap: O(1) like HashMap but iterates in insertion order. Set access-order=true and override removeEldestEntry → an LRU cache in a few lines.
Thread-safe: use ConcurrentHashMap (bucket-level locking). Avoid Hashtable (legacy) and Collections.synchronizedMap (full-map lock).
Handy Java 8+ methods:
map.merge(key, 1, Integer::sum); // counter pattern, cleaner than get+put
map.computeIfAbsent(key, k -> new ArrayList<>()); // lazy init