Chuyển tới nội dung chính

Map Interface

Mục tiêu bài học

Sau bài này, bạn sẽ:

  • Hiểu Map interface - key-value pairs với unique keys (không phải Collection)
  • So sánh HashMap (O(1), unordered), LinkedHashMap (insertion-ordered), TreeMap (sorted by key, O(log n))
  • Thành thạo các operations: put, get, getOrDefault, putIfAbsent, computeIfAbsent, merge
  • Biết cách iterate hiệu quả qua Map với entrySet(), keySet(), values()
  • Áp dụng Map cho frequency counting, grouping, caching, và fast lookup

Bài trước: Set Interface — Đã học về Set với HashSet, LinkedHashSet, TreeSet. Bài này sẽ tìm hiểu Map - cấu trúc lưu trữ key-value pairs.

Map Interface là gì?​

Map là một interface trong Java Collections Framework đại diện cho ánh xạ (mapping) từ key đến value. Mỗi key ánh xạ đến đúng một value.

Đặc điểm chính​

  • Key-Value pairs: Lưu trữ dữ liệu dạng cặp (key, value)
  • Unique keys: Mỗi key chỉ xuất hiện một lần (không duplicate keys)
  • One value per key: Mỗi key chỉ ánh xạ đến một value
  • Value có thể duplicate: Nhiều key có thể trỏ đến cùng một value
  • KHÔNG phải Collection: Map không extends Collection interface
public interface Map<K, V> {
    // Basic operations
    V put(K key, V value);
    V get(Object key);
    V remove(Object key);
    boolean containsKey(Object key);
    boolean containsValue(Object value);
    int size();
    boolean isEmpty();

    // Bulk operations
    void putAll(Map<? extends K, ? extends V> m);
    void clear();

    // Collection views
    Set<K> keySet();
    Collection<V> values();
    Set<Map.Entry<K, V>> entrySet();
}
Map không phải Collection

Map KHÔNG extends Collection interface vì:

  • Collection chứa các phần tử đơn lẻ
  • Map chứa các cặp key-value

Tuy nhiên, Map vẫn được coi là một phần của Collections Framework.

HashMap - Hash Table Implementation​

HashMap là implementation phổ biến nhất của Map, sử dụng hash table bên trong.

HashMap Internal Structure Deep Dive​

HashMap lưu trữ data dựa trên hash table với các thành phần sau:

1. Array of buckets (Node[])

// Simplified HashMap internal structure
class HashMap<K, V> {
    transient Node<K,V>[] table;  // Main array holding buckets
    int size;                      // Number of key-value pairs
    int threshold;                 // Resize threshold = capacity * load factor
    final float loadFactor;        // Default 0.75

    static class Node<K,V> {
        final int hash;       // Cached hash code
        final K key;
        V value;
        Node<K,V> next;       // LinkedList pointer (collision handling)
    }
}

2. Hash function và bucket index

// Quy trình put/get
int hash = key.hashCode();
int bucketIndex = hash & (table.length - 1);  // Equivalent to hash % table.length
// Ví dụ: hash = 1234, table.length = 16
// bucketIndex = 1234 & 15 = 2

Tại sao dùng & thay vì %?

  • & (bitwise AND) nhanh hơn % (modulo) nhiều
  • Chỉ work khi table.length là power of 2 (16, 32, 64, ...)

3. Load factor và resize

  • Load factor (default 0.75): Tỷ lệ "đầy" trước khi resize
  • Threshold = capacity × load factor
  • Khi size > threshold → resize (double capacity)
// Default values
Initial capacity: 16
Load factor: 0.75
Threshold: 16 * 0.75 = 12

// Resize process
When size reaches 13:
  1. Create new array: length 32
  2. Rehash all entries (hash & 31)
  3. Transfer to new array
  4. New threshold: 32 * 0.75 = 24

4. Hash collision → Chaining → Treeify

Khi nhiều keys hash về cùng bucket:

Phase 1: Chaining (LinkedList)

Bucket 5: [key1, val1] → [key2, val2] → [key3, val3] → null
  • Tìm kiếm: O(n) trong chain

Phase 2: Treeify (Red-Black Tree, Java 8+)

Điều kiện: bucket.size > 8 AND table.length >= 64
Convert: LinkedList → Red-Black Tree
Benefit: O(n) → O(log n)
// Constants
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
static final int MIN_TREEIFY_CAPACITY = 64;

Full process visualization:

Đặc điểm​

  • Unordered: Không đảm bảo thứ tự
  • Fast operations: O(1) average cho get, put, remove
  • Allows one null key: Chấp nhận một key null
  • Allows multiple null values: Values có thể là null
  • Not thread-safe
  • Dựa vào equals() và hashCode() của key
import java.util.*;

public class HashMapDemo {
    public static void main(String[] args) {
        // Khởi tạo
        Map<String, Integer> ages = new HashMap<>();

        // put() - Thêm hoặc update
        ages.put("Alice", 25);
        ages.put("Bob", 30);
        ages.put("Charlie", 35);
        ages.put("Alice", 26);  // Update Alice's age
        System.out.println(ages);  // {Bob=30, Alice=26, Charlie=35}

        // get() - Lấy value theo key
        Integer aliceAge = ages.get("Alice");  // 26
        Integer davidAge = ages.get("David");  // null (không tồn tại)

        // containsKey() và containsValue()
        boolean hasAlice = ages.containsKey("Alice");    // true
        boolean hasAge30 = ages.containsValue(30);       // true

        // remove() - Xóa theo key
        Integer removed = ages.remove("Bob");  // 30
        System.out.println(ages);  // {Alice=26, Charlie=35}

        // size() và isEmpty()
        int size = ages.size();         // 2
        boolean empty = ages.isEmpty(); // false

        // Null key và null value
        ages.put(null, 99);      // OK - one null key allowed
        ages.put("Eve", null);   // OK - null values allowed
        System.out.println(ages);
    }
}

Performance của HashMap​

OperationTime ComplexityNote
get(key)O(1) averageCó thể O(n) với hash collision nhiều
put(key, value)O(1) averageCó thể O(n) khi resize
remove(key)O(1) average
containsKey(key)O(1) average
containsValue(value)O(n)Phải scan toàn bộ values
Capacity và Load Factor

Giống HashSet, HashMap có:

  • Initial capacity: Mặc định 16
  • Load factor: Mặc định 0.75
// Mặc định: capacity=16, loadFactor=0.75
Map<String, Integer> map1 = new HashMap<>();

// Custom capacity (tốt khi biết trước số lượng)
Map<String, Integer> map2 = new HashMap<>(1000);

// Custom capacity và loadFactor
Map<String, Integer> map3 = new HashMap<>(1000, 0.8f);

HashMap Null Key Handling​

HashMap cho phép 1 null key, và null key được lưu ở bucket 0:

Map<String, Integer> map = new HashMap<>();
map.put(null, 100);
map.put("A", 1);
map.put(null, 200);  // Update null key

System.out.println(map.get(null));  // Output: 200
System.out.println(map.size());     // Output: 2

// Internally:
// hash(null) = 0
// bucketIndex = 0 & (n-1) = 0
// → Null key luôn ở bucket 0

Implementation detail:

// HashMap source code
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    //     Null key → hash = 0 → bucket index = 0
}

Comparison với TreeMap:

// HashMap: null key OK
Map<String, Integer> hashMap = new HashMap<>();
hashMap.put(null, 1);  // ✅ OK

// TreeMap: null key → NullPointerException
Map<String, Integer> treeMap = new TreeMap<>();
treeMap.put(null, 1);  // ❌ NullPointerException
// Vì TreeMap cần compare keys → null.compareTo(...) → NPE

LinkedHashMap - Ordered HashMap​

LinkedHashMap extends HashMap và duy trì insertion order (hoặc access order).

Đặc điểm​

  • Insertion-ordered (mặc định): Duy trì thứ tự thêm vào
  • Access-ordered (optional): Có thể duy trì thứ tự truy cập (LRU cache)
  • Performance tương tự HashMap: O(1) average
  • Tốn bộ nhớ hơn: Cần doubly-linked list
  • Allows one null key
import java.util.*;

public class LinkedHashMapDemo {
    public static void main(String[] args) {
        // Insertion-order (mặc định)
        Map<String, Integer> map = new LinkedHashMap<>();
        map.put("C", 3);
        map.put("A", 1);
        map.put("B", 2);

        System.out.println(map);  // {C=3, A=1, B=2} - thứ tự insertion

        // Iteration theo insertion order
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            System.out.println(entry.getKey() + " = " + entry.getValue());
        }
        // Output:
        // C = 3
        // A = 1
        // B = 2

        // Access-order mode (cho LRU cache)
        Map<String, Integer> accessOrderMap = new LinkedHashMap<>(16, 0.75f, true);
        accessOrderMap.put("A", 1);
        accessOrderMap.put("B", 2);
        accessOrderMap.put("C", 3);

        accessOrderMap.get("A");  // Access A
        System.out.println(accessOrderMap);  // {B=2, C=3, A=1} - A moved to end
    }
}

LRU Cache với LinkedHashMap​

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;

    public LRUCache(int maxSize) {
        super(maxSize, 0.75f, true);  // access-order = true
        this.maxSize = maxSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;  // Tự động xóa entry cũ nhất khi vượt maxSize
    }

    public static void main(String[] args) {
        LRUCache<String, Integer> cache = new LRUCache<>(3);

        cache.put("A", 1);
        cache.put("B", 2);
        cache.put("C", 3);
        System.out.println(cache);  // {A=1, B=2, C=3}

        cache.get("A");  // Access A
        System.out.println(cache);  // {B=2, C=3, A=1} - A moved to end

        cache.put("D", 4);  // Add D, B sẽ bị xóa (eldest)
        System.out.println(cache);  // {C=3, A=1, D=4}
    }
}

TreeMap - Sorted Map​

TreeMap là implementation dựa trên Red-Black Tree, tự động sắp xếp theo key.

Đặc điểm​

  • Sorted by keys: Tự động sắp xếp theo natural order hoặc Comparator
  • NavigableMap: Hỗ trợ navigation methods
  • NO null key: Không chấp nhận null key (NullPointerException)
  • Null values OK: Values có thể null
  • Slower: O(log n) cho get, put, remove
import java.util.*;

public class TreeMapDemo {
    public static void main(String[] args) {
        // Natural order (alphabetical cho String)
        Map<String, Integer> map = new TreeMap<>();
        map.put("Charlie", 35);
        map.put("Alice", 25);
        map.put("Bob", 30);

        System.out.println(map);  // {Alice=25, Bob=30, Charlie=35} - sorted!

        // Numbers - sorted ascending
        Map<Integer, String> grades = new TreeMap<>();
        grades.put(90, "A");
        grades.put(70, "C");
        grades.put(80, "B");
        System.out.println(grades);  // {70=C, 80=B, 90=A}

        // Custom comparator - descending
        Map<String, Integer> descMap = new TreeMap<>(Comparator.reverseOrder());
        descMap.put("Charlie", 35);
        descMap.put("Alice", 25);
        descMap.put("Bob", 30);
        System.out.println(descMap);  // {Charlie=35, Bob=30, Alice=25}

        // NavigableMap methods
        TreeMap<Integer, String> navMap = new TreeMap<>();
        navMap.put(10, "Ten");
        navMap.put(20, "Twenty");
        navMap.put(30, "Thirty");
        navMap.put(40, "Forty");

        System.out.println(navMap.firstKey());      // 10
        System.out.println(navMap.lastKey());       // 40
        System.out.println(navMap.lowerKey(25));    // 20 (< 25)
        System.out.println(navMap.higherKey(25));   // 30 (> 25)
        System.out.println(navMap.floorKey(25));    // 20 (<= 25)
        System.out.println(navMap.ceilingKey(25));  // 30 (>= 25)

        // Range views
        System.out.println(navMap.headMap(30));     // {10=Ten, 20=Twenty} (< 30)
        System.out.println(navMap.tailMap(20));     // {20=Twenty, 30=Thirty, 40=Forty} (>= 20)
        System.out.println(navMap.subMap(15, 35));  // {20=Twenty, 30=Thirty} (>= 15, < 35)
    }
}

TreeMap uses Comparator for Equality (NOT equals!)​

Quan trọng: TreeMap dùng Comparator.compare() (hoặc Comparable.compareTo()) để xác định equality, KHÔNG dùng equals()!

class Person {
    String name;
    int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public boolean equals(Object o) {
        if (!(o instanceof Person)) return false;
        Person p = (Person) o;
        return age == p.age && Objects.equals(name, p.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

// TreeMap với Comparator chỉ compare age
Map<Person, String> map = new TreeMap<>(Comparator.comparingInt(p -> p.age));

Person alice25 = new Person("Alice", 25);
Person bob25 = new Person("Bob", 25);  // Cùng age!

map.put(alice25, "Alice's data");
map.put(bob25, "Bob's data");  // OVERWRITE Alice's data!

System.out.println(map.size());  // Output: 1 (not 2!)
System.out.println(map.get(alice25));  // Output: "Bob's data"
// TreeMap coi alice25 và bob25 là "equal" vì compare(alice25, bob25) == 0

// get() cũng dùng Comparator!
Person charlie25 = new Person("Charlie", 25);
System.out.println(map.get(charlie25));  // Output: "Bob's data"
// Dù !charlie25.equals(bob25), nhưng compare(charlie25, bob25) == 0 → found!
🔥 Bẫy OCP: TreeMap "lost" entries
Map<Person, String> map = new TreeMap<>(
    Comparator.comparing(Person::getName)  // Chỉ compare name
);

map.put(new Person("Alice", 25), "Young Alice");
map.put(new Person("Alice", 50), "Old Alice");  // OVERWRITE!

System.out.println(map.size());  // Output: 1 - lost entry!

// Fix: Compare tất cả distinguishing fields
Map<Person, String> map = new TreeMap<>(
    Comparator.comparing(Person::getName)
              .thenComparingInt(Person::getAge)
);
map.put(new Person("Alice", 25), "Young Alice");
map.put(new Person("Alice", 50), "Old Alice");
System.out.println(map.size());  // Output: 2 - correct!

LinkedHashMap Access-Order Mode (LRU Cache)​

LinkedHashMap có hai modes:

  1. Insertion-order (default): Duy trì thứ tự insert
  2. Access-order: Duy trì thứ tự access (LRU cache)

LinkedHashMap Access-Order LRU Diagram​

Giải thích:

  • Access (get/put) → element moved to end (most recently used)
  • Eldest = đầu danh sách (least recently used)
  • removeEldestEntry check → auto remove LRU element khi exceed size
// Access-order mode: LRU (Least Recently Used) cache
Map<String, Integer> lru = new LinkedHashMap<>(16, 0.75f, true);
//                                             capacity, loadFactor, accessOrder=true

lru.put("A", 1);
lru.put("B", 2);
lru.put("C", 3);
System.out.println(lru);  // Output: {A=1, B=2, C=3}

// Access "A" → move to end
lru.get("A");
System.out.println(lru);  // Output: {B=2, C=3, A=1} - A moved to end!

// Access "B" → move to end
lru.get("B");
System.out.println(lru);  // Output: {C=3, A=1, B=2} - B moved to end!

Implement LRU Cache với size limit:

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;

    public LRUCache(int maxSize) {
        super(maxSize, 0.75f, true);  // accessOrder = true
        this.maxSize = maxSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;  // Remove eldest khi vượt maxSize
    }
}

// Test LRU Cache
LRUCache<String, Integer> cache = new LRUCache<>(3);  // Max 3 entries

cache.put("A", 1);
cache.put("B", 2);
cache.put("C", 3);
System.out.println(cache);  // {A=1, B=2, C=3}

cache.get("A");  // Access A
System.out.println(cache);  // {B=2, C=3, A=1}

cache.put("D", 4);  // Add D → B is eldest, removed!
System.out.println(cache);  // {C=3, A=1, D=4}

cache.get("C");  // Access C
cache.put("E", 5);  // Add E → A is eldest, removed!
System.out.println(cache);  // {D=4, C=3, E=5}
💡 Cách nhớ: Access-order = "Người vừa dùng lên đầu hàng"

Access-order LinkedHashMap giống hàng chờ ưu tiên người vừa dùng dịch vụ. Mỗi khi ai đó dùng (get), họ được xếp lại lên cuối hàng. Người ở đầu hàng (least recently used) sẽ bị loại bỏ khi đầy.

TreeMap implements NavigableMap, cung cấp navigation methods tương tự NavigableSet:

NavigableMap<Integer, String> map = new TreeMap<>();
map.put(10, "Ten");
map.put(20, "Twenty");
map.put(30, "Thirty");
map.put(40, "Forty");
map.put(50, "Fifty");

// Navigation methods (similar to NavigableSet)
System.out.println(map.lowerKey(35));      // 30 (< 35)
System.out.println(map.floorKey(30));      // 30 (<= 30)
System.out.println(map.ceilingKey(35));    // 40 (>= 35)
System.out.println(map.higherKey(30));     // 40 (> 30)

System.out.println(map.lowerEntry(35));    // 30=Thirty
System.out.println(map.higherEntry(35));   // 40=Forty

// First and last
System.out.println(map.firstKey());        // 10
System.out.println(map.lastKey());         // 50
System.out.println(map.firstEntry());      // 10=Ten
System.out.println(map.lastEntry());       // 50=Fifty

// Poll (remove and return)
System.out.println(map.pollFirstEntry());  // 10=Ten (removed)
System.out.println(map.pollLastEntry());   // 50=Fifty (removed)
System.out.println(map);                   // {20=Twenty, 30=Thirty, 40=Forty}

// Submaps (VIEWS!)
NavigableMap<Integer, String> subMap = map.subMap(20, true, 40, true);
System.out.println(subMap);                // {20=Twenty, 30=Thirty, 40=Forty}

subMap.put(25, "TwentyFive");
System.out.println(map);  // {20=Twenty, 25=TwentyFive, 30=Thirty, 40=Forty}
// Modification qua subMap ảnh hưởng parent map (view!)

// Descending map
NavigableMap<Integer, String> desc = map.descendingMap();
System.out.println(desc);  // {40=Forty, 30=Thirty, 25=TwentyFive, 20=Twenty}

TreeMap vs HashMap Lookup Diagram​

So sánh:

  • HashMap: Hash → Bucket → O(1) average (có thể O(n) worst case với collision nhiều)
  • TreeMap: Binary search tree → O(log n) guaranteed

Performance của TreeMap​

OperationTime ComplexityNote
get(key)O(log n)Binary search tree
put(key, value)O(log n)
remove(key)O(log n)
containsKey(key)O(log n)
firstKey(), lastKey()O(log n)

So sánh 3 Implementations​

Đặc điểmHashMapLinkedHashMapTreeMap
Cấu trúcHash tableHash table + Linked listRed-Black Tree
OrderingUnorderedInsertion orderSorted by keys
Null key1 null key OK1 null key OKNO null key
Null valuesYesYesYes
PerformanceO(1) averageO(1) averageO(log n)
MemoryÍt nhấtTrung bìnhNhiều nhất
Use caseGeneral purpose, nhanh nhấtCần duy trì insertion orderCần sắp xếp theo key
Thread-safeNoNoNo

Khi nào dùng implementation nào?​

// HashMap - Default choice, nhanh nhất
Map<String, User> userMap = new HashMap<>();  // ✅ General purpose

// LinkedHashMap - Cần duy trì thứ tự insertion hoặc LRU cache
Map<String, String> config = new LinkedHashMap<>();  // ✅ Preserve order
LRUCache<String, Data> cache = new LRUCache<>(100);  // ✅ LRU cache

// TreeMap - Cần tự động sắp xếp theo key
Map<Date, Event> events = new TreeMap<>();  // ✅ Chronological order
Map<Integer, String> rankings = new TreeMap<>(Comparator.reverseOrder());  // ✅ Sorted rankings

Common Operations trên Map​

1. Basic operations​

Map<String, Integer> map = new HashMap<>();

// put() - thêm hoặc update
map.put("A", 1);
map.put("B", 2);
map.put("A", 10);  // Update A's value to 10

// get() - lấy value
Integer value = map.get("A");  // 10
Integer missing = map.get("Z");  // null

// remove() - xóa
Integer removed = map.remove("B");  // 2

// containsKey() và containsValue()
boolean hasA = map.containsKey("A");    // true
boolean hasValue10 = map.containsValue(10);  // true

// size() và isEmpty()
int size = map.size();
boolean empty = map.isEmpty();

// clear() - xóa tất cả
map.clear();

2. Java 8+ methods​

Map<String, Integer> map = new HashMap<>();
map.put("A", 1);
map.put("B", 2);

// getOrDefault() - tránh null
Integer value = map.getOrDefault("Z", 0);  // 0 (default value)

// putIfAbsent() - chỉ put nếu key chưa tồn tại
map.putIfAbsent("A", 100);  // Không update (A đã tồn tại)
map.putIfAbsent("C", 3);    // Thêm C=3 (C chưa tồn tại)

// computeIfAbsent() - tạo value nếu key chưa tồn tại
map.computeIfAbsent("D", k -> k.length());  // D=1

// computeIfPresent() - update value nếu key tồn tại
map.computeIfPresent("A", (k, v) -> v * 10);  // A=10

// compute() - tính toán value mới
map.compute("B", (k, v) -> (v == null) ? 1 : v + 1);  // B=3

// merge() - merge value
map.merge("A", 5, Integer::sum);  // A=15 (10+5)

// replace() - thay thế value
map.replace("A", 20);           // A=20
map.replace("A", 20, 30);       // A=30 (nếu old value = 20)

// forEach() - iterate với lambda
map.forEach((k, v) -> System.out.println(k + " = " + v));

compute/merge/putIfAbsent Deep Dive​

Đây là các methods quan trọng nhất của Java 8+ Map API, nhưng nhiều người nhầm lẫn:

1. putIfAbsent() - Eager evaluation

Map<String, List<String>> map = new HashMap<>();

// putIfAbsent: value được evaluate TRƯỚC KHI check
map.putIfAbsent("A", new ArrayList<>());  // Tạo ArrayList dù "A" đã tồn tại
map.putIfAbsent("A", new ArrayList<>());  // Tạo thêm ArrayList (lãng phí!)

// Value param luôn được evaluate
String expensiveValue = computeExpensiveValue();  // Always called
map.putIfAbsent("A", expensiveValue);  // Dù "A" đã có, vẫn gọi computeExpensiveValue()!

2. computeIfAbsent() - Lazy evaluation

Map<String, List<String>> map = new HashMap<>();

// computeIfAbsent: function CHỈ được gọi khi key chưa tồn tại
map.computeIfAbsent("A", k -> new ArrayList<>());  // Tạo ArrayList
map.computeIfAbsent("A", k -> new ArrayList<>());  // KHÔNG tạo ArrayList!

// Function chỉ được gọi khi cần
map.computeIfAbsent("B", k -> {
    System.out.println("Computing for key: " + k);
    return expensiveComputation();
});
// Nếu "B" đã tồn tại, function KHÔNG được gọi (lazy!)

Use case: Build nested collections

Map<String, List<String>> groups = new HashMap<>();

// ❌ CÁCH CŨ: Verbose
String key = "team1";
if (!groups.containsKey(key)) {
    groups.put(key, new ArrayList<>());
}
groups.get(key).add("Alice");

// ✅ CÁCH MỚI: Concise
groups.computeIfAbsent("team1", k -> new ArrayList<>()).add("Alice");
groups.computeIfAbsent("team1", k -> new ArrayList<>()).add("Bob");
groups.computeIfAbsent("team2", k -> new ArrayList<>()).add("Charlie");

System.out.println(groups);
// Output: {team1=[Alice, Bob], team2=[Charlie]}

3. merge() - Combine values

Map<String, Integer> map = new HashMap<>();

// merge(key, value, remappingFunction)
// - Nếu key KHÔNG tồn tại: put(key, value)
// - Nếu key TỒN TẠI: newValue = remappingFunction(oldValue, value)
// - Nếu newValue == null: remove key

// Example: Word frequency counter
String[] words = {"apple", "banana", "apple", "cherry", "banana", "apple"};
Map<String, Integer> freq = new HashMap<>();

for (String word : words) {
    freq.merge(word, 1, Integer::sum);
    // apple: null → put("apple", 1)
    // apple: 1 → remapping(1, 1) = 2
    // apple: 2 → remapping(2, 1) = 3
}

System.out.println(freq);  // Output: {apple=3, banana=2, cherry=1}

// TƯƠNG ĐƯƠNG với:
for (String word : words) {
    freq.put(word, freq.getOrDefault(word, 0) + 1);
}

merge() với null result → remove

Map<String, Integer> scores = new HashMap<>();
scores.put("Alice", 10);
scores.put("Bob", 5);

// Giảm score, nếu <= 0 thì remove
scores.merge("Alice", -3, (old, val) -> old + val);  // 10 - 3 = 7
scores.merge("Bob", -10, (old, val) -> {
    int newScore = old + val;
    return newScore <= 0 ? null : newScore;  // null → remove key!
});

System.out.println(scores);  // Output: {Alice=7}
// Bob bị remove vì merge function trả về null

4. compute() - Unconditional computation

Map<String, Integer> map = new HashMap<>();
map.put("A", 10);

// compute(key, remappingFunction)
// Function LUÔN được gọi, dù key có tồn tại hay không
// - function(key, oldValue) → newValue
// - oldValue = null nếu key không tồn tại
// - newValue = null → remove key

map.compute("A", (k, v) -> (v == null) ? 1 : v + 1);  // A=11 (10+1)
map.compute("B", (k, v) -> (v == null) ? 1 : v + 1);  // B=1 (null → 1)
map.compute("A", (k, v) -> null);  // Remove A (return null)

System.out.println(map);  // Output: {B=1}

compute/merge/putIfAbsent Decision Flowchart​

Khi nào dùng gì:

  • putIfAbsent: Value đơn giản, eager evaluation OK
  • computeIfAbsent: Value expensive (DB call, computation), lazy evaluation
  • merge: Combine values (sum, concat, etc.)
  • compute: Unconditional computation, có thể remove key (return null)

Comparison Table:

MethodKey exists?Function called?Value paramNull result
putIfAbsent(k, v)No → putNever (eager eval)Always evaluatedN/A
computeIfAbsent(k, f)No → computeOnly if key absentLazy (function)Insert null? No!
computeIfPresent(k, f)Yes → computeOnly if key presentN/ARemove key
compute(k, f)Always computeAlwaysN/ARemove key
merge(k, v, f)No→put, Yes→mergeOnly if key presentAlways evaluatedRemove key
🔥 Bẫy OCP: merge() value param cannot be null
Map<String, Integer> map = new HashMap<>();
map.put("A", 10);

// merge() value parameter KHÔNG THỂ null!
map.merge("A", null, Integer::sum);  // ❌ NullPointerException
// Vì merge sẽ put(key, value) nếu key chưa tồn tại → value = null không hợp lệ

// Nhưng remapping function CÓ THỂ trả về null
map.merge("A", 5, (old, val) -> null);  // ✅ OK - remove key

3. Immutable Map với Map.of() (Java 9+)​

// Tạo immutable map
Map<String, Integer> map1 = Map.of("A", 1, "B", 2, "C", 3);

// Tối đa 10 cặp với Map.of()
Map<String, Integer> map2 = Map.of(
    "A", 1,
    "B", 2,
    "C", 3,
    "D", 4,
    "E", 5
);

// Trên 10 cặp: dùng Map.ofEntries()
Map<String, Integer> map3 = Map.ofEntries(
    Map.entry("A", 1),
    Map.entry("B", 2),
    Map.entry("C", 3),
    Map.entry("D", 4),
    Map.entry("E", 5),
    Map.entry("F", 6)
    // ... thêm nhiều entries
);

// Không thể thay đổi
// map1.put("D", 4);  // UnsupportedOperationException

// Không chứa null
// Map<String, Integer> withNull = Map.of("A", null);  // NullPointerException

Iteration Patterns​

1. Iterate qua keySet()​

Map<String, Integer> map = new HashMap<>();
map.put("A", 1);
map.put("B", 2);
map.put("C", 3);

// Cách 1: for-each
for (String key : map.keySet()) {
    Integer value = map.get(key);
    System.out.println(key + " = " + value);
}

// Cách 2: Iterator
Iterator<String> keyIter = map.keySet().iterator();
while (keyIter.hasNext()) {
    String key = keyIter.next();
    System.out.println(key);
}

2. Iterate qua values()​

// Chỉ quan tâm values, không quan tâm keys
for (Integer value : map.values()) {
    System.out.println(value);
}

3. Iterate qua entrySet() - RECOMMENDED​

// Cách HIỆU QUẢ NHẤT để iterate Map
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    String key = entry.getKey();
    Integer value = entry.getValue();
    System.out.println(key + " = " + value);

    // Có thể update value qua entry
    entry.setValue(value * 2);
}
entrySet() vs keySet()

Luôn dùng entrySet() khi cần cả key và value!

// ❌ KHÔNG TỐT: Gọi get() mỗi lần (O(n) operations)
for (String key : map.keySet()) {
    Integer value = map.get(key);  // Extra O(1) lookup
}

// ✅ TỐT: Truy cập trực tiếp entry (O(n) operations)
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    String key = entry.getKey();    // No extra lookup
    Integer value = entry.getValue();
}

4. forEach() với Lambda (Java 8+)​

// Ngắn gọn nhất
map.forEach((key, value) -> {
    System.out.println(key + " = " + value);
});

// Method reference
map.forEach((k, v) -> System.out.println(k + ": " + v));

5. Stream API (Java 8+)​

// Filter và collect
Map<String, Integer> filtered = map.entrySet().stream()
    .filter(entry -> entry.getValue() > 1)
    .collect(Collectors.toMap(Map.Entry::getKey, Map.Entry::getValue));

// Map values
Map<String, Integer> doubled = map.entrySet().stream()
    .collect(Collectors.toMap(
        Map.Entry::getKey,
        entry -> entry.getValue() * 2
    ));

// Sorted by value
map.entrySet().stream()
    .sorted(Map.Entry.comparingByValue())
    .forEach(entry -> System.out.println(entry));

HashMap Internal Structure Diagram​

OCP Traps - Bẫy thường gặp trong kỳ thi​

🔥 Bẫy 1: map.get() returns null có 2 ý nghĩa
Map<String, Integer> map = new HashMap<>();
map.put("A", null);  // Value is null

System.out.println(map.get("A"));  // null - key exists, value is null
System.out.println(map.get("B"));  // null - key does not exist

// Không thể phân biệt! Phải dùng containsKey()
if (map.containsKey("A")) {
    System.out.println("Key exists, value = " + map.get("A"));
} else {
    System.out.println("Key does not exist");
}
🔥 Bẫy 2: HashMap allows 1 null key, TreeMap forbids null keys
// HashMap: null key OK
Map<String, Integer> hashMap = new HashMap<>();
hashMap.put(null, 1);  // ✅ OK

// TreeMap: null key → NullPointerException
Map<String, Integer> treeMap = new TreeMap<>();
treeMap.put(null, 1);  // ❌ NullPointerException at runtime!
🔥 Bẫy 3: merge() value param cannot be null
Map<String, Integer> map = new HashMap<>();
map.put("A", 10);

// merge(key, value, remappingFunction)
// value parameter KHÔNG được null!
map.merge("A", null, Integer::sum);  // ❌ NullPointerException

// Nhưng remapping function CÓ THỂ return null
map.merge("A", 5, (old, val) -> null);  // ✅ OK - removes key
🔥 Bẫy 4: TreeMap dùng Comparator, không dùng equals()
class Person {
    String name;
    int age;
    // equals() compares name AND age
}

Map<Person, String> map = new TreeMap<>(
    Comparator.comparingInt(p -> p.age)  // Chỉ compare age!
);

map.put(new Person("Alice", 25), "Data1");
map.put(new Person("Bob", 25), "Data2");  // OVERWRITE Data1!

System.out.println(map.size());  // Output: 1 (not 2!)
// TreeMap coi two persons với cùng age là "equal"

Ví dụ thực hành​

Ví dụ 1: Word Frequency Counter​

import java.util.*;

public class WordFrequency {
    public static void main(String[] args) {
        String text = "the quick brown fox jumps over the lazy dog the fox";
        String[] words = text.split(" ");

        // Đếm frequency
        Map<String, Integer> frequencyMap = new HashMap<>();
        for (String word : words) {
            // Cách 1: Manual check
            // if (frequencyMap.containsKey(word)) {
            //     frequencyMap.put(word, frequencyMap.get(word) + 1);
            // } else {
            //     frequencyMap.put(word, 1);
            // }

            // Cách 2: getOrDefault (Java 8+)
            frequencyMap.put(word, frequencyMap.getOrDefault(word, 0) + 1);

            // Cách 3: merge (Java 8+)
            // frequencyMap.merge(word, 1, Integer::sum);
        }

        System.out.println("Word frequencies:");
        frequencyMap.forEach((word, count) ->
            System.out.println(word + ": " + count)
        );

        // Tìm từ xuất hiện nhiều nhất
        String mostFrequent = frequencyMap.entrySet().stream()
            .max(Map.Entry.comparingByValue())
            .map(Map.Entry::getKey)
            .orElse(null);

        System.out.println("\nMost frequent word: " + mostFrequent);
    }
}

Ví dụ 2: Group By với Map​

class Student {
    String name;
    String major;
    double gpa;

    public Student(String name, String major, double gpa) {
        this.name = name;
        this.major = major;
        this.gpa = gpa;
    }

    @Override
    public String toString() {
        return name + "(" + gpa + ")";
    }
}

public class GroupStudents {
    public static void main(String[] args) {
        List<Student> students = Arrays.asList(
            new Student("Alice", "CS", 3.8),
            new Student("Bob", "Math", 3.5),
            new Student("Charlie", "CS", 3.9),
            new Student("David", "Math", 3.6),
            new Student("Eve", "CS", 3.7)
        );

        // Group by major
        Map<String, List<Student>> groupedByMajor = new HashMap<>();
        for (Student student : students) {
            groupedByMajor.computeIfAbsent(student.major, k -> new ArrayList<>())
                          .add(student);
        }

        System.out.println("Grouped by major:");
        groupedByMajor.forEach((major, studentList) -> {
            System.out.println(major + ": " + studentList);
        });

        // Với Stream API (Java 8+)
        Map<String, List<Student>> grouped = students.stream()
            .collect(Collectors.groupingBy(s -> s.major));
    }
}

Ví dụ 3: Two Sum Problem với HashMap​

public class TwoSum {
    public static int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }

        return null;  // Không tìm thấy
    }

    public static void main(String[] args) {
        int[] nums = {2, 7, 11, 15};
        int target = 9;

        int[] result = twoSum(nums, target);
        System.out.println("Indices: " + Arrays.toString(result));
        // Output: [0, 1] vì nums[0] + nums[1] = 2 + 7 = 9
    }
}

Ví dụ 4: Cache với computeIfAbsent()​

class ExpensiveOperation {
    private Map<String, String> cache = new HashMap<>();

    public String compute(String input) {
        return cache.computeIfAbsent(input, k -> {
            // Expensive computation
            System.out.println("Computing for: " + k);
            try {
                Thread.sleep(1000);  // Simulate delay
            } catch (InterruptedException e) {}
            return k.toUpperCase();
        });
    }

    public static void main(String[] args) {
        ExpensiveOperation op = new ExpensiveOperation();

        System.out.println(op.compute("hello"));  // Computes (1s delay)
        System.out.println(op.compute("world"));  // Computes (1s delay)
        System.out.println(op.compute("hello"));  // From cache (instant)
    }
}

Bài tập thực hành​

Bài 1: Anagram Groups​

Viết method Map<String, List<String>> groupAnagrams(String[] words) để group các từ là anagram của nhau. Ví dụ: ["eat", "tea", "tan", "ate", "nat", "bat"] → {aet=[eat, tea, ate], ant=[tan, nat], abt=[bat]}

Bài 2: Contact Manager​

Tạo class ContactManager với Map lưu contacts (name → phone):

  • addContact(String name, String phone)
  • getPhone(String name)
  • removeContact(String name)
  • listAllContacts(): in ra tất cả contacts theo alphabetical order

Bài 3: Subarray Sum Equals K​

Viết method int subarraySum(int[] nums, int k) đếm số subarray có tổng bằng k. Sử dụng HashMap để giải quyết trong O(n).

Bài 4: LFU Cache​

Implement LFU (Least Frequently Used) Cache với:

  • get(key): Lấy value, tăng frequency
  • put(key, value): Thêm/update, xóa item ít dùng nhất khi đầy

Tổng kết​

Trong bài này, bạn đã học:

  • Map: Key-value pairs, unique keys, KHÔNG phải Collection
  • HashMap: Nhanh nhất (O(1) average), unordered, cho phép 1 null key
  • LinkedHashMap: Duy trì insertion order (hoặc access order cho LRU cache)
  • TreeMap: Tự động sắp xếp theo key (O(log n)), KHÔNG cho phép null key
  • Common operations: put, get, remove, containsKey, getOrDefault, putIfAbsent, computeIfAbsent
  • Iteration: entrySet() là cách hiệu quả nhất để iterate qua Map
  • Immutable Map: Map.of(), Map.ofEntries() (Java 9+)
  • Use cases: Frequency counter, grouping, caching, fast lookup

Quy tắc vàng:

  1. Khi không chắc → Dùng HashMap
  2. Cần thứ tự insertion hoặc LRU cache → Dùng LinkedHashMap
  3. Cần sắp xếp theo key → Dùng TreeMap
  4. Iterate Map → Dùng entrySet(), không dùng keySet()

Đọc thêm​