Tổng quan về kiến trúc

LinkedHashMap là một lớp kế thừa trực tiếp từ HashMap, do đó nó sở hữu đầy đủ các đặc tính của HashMap (lưu trữ dạng mảng + danh sách liên kết đơn/cây đỏ-đen). Điểm khác biệt cốt lõi nằm ở việc LinkedHashMap duy trì một danh sách liên kết kép (doubly linked list) chạy qua tất cả các mục nhập (entries). Cơ chế này giúp đảm bảo thứ tự duyệt các phần tử. Có hai chế độ sắp xếp chính được hỗ trợ:

• Insertion Order (Thứ tự chèn): Thứ tự các phần tử khi duyệt sẽ giống hệt với thứ tự chúng được thêm vào map.
• Access Order (Thứ tự truy cập - LRU): Thứ tự các phần tử được sắp xếp lại dựa trên lần truy cập gần nhất. Phần tử nào được truy cập (get/put) sẽ được di chuyển xuống cuối danh sách. Đây là cơ sở để triển khai bộ nhớ đệm LRU (Least Recently Used).

Chi tiết cài đặt và cách sử dụng

1. Thứ tự chèn (Insertion Order)

Mặc định, LinkedHashMap sắp xếp các phần tử theo thứ tự chúng được đưa vào.

import java.util.*;

public class InsertionOrderDemo {
    public static void main(String[] args) {
        // Khởi tạo map với mặc định là thứ tự chèn
        Map<String, Integer> productMap = new LinkedHashMap<>();
        
        productMap.put("Laptop", 1500);
        productMap.put("Mouse", 25);
        productMap.put("Keyboard", 80);

        // Duyệt qua map
        for (Map.Entry<String, Integer> item : productMap.entrySet()) {
            System.out.println(item.getKey() + " : " + item.getValue());
        }
        
        // Kết quả sẽ in ra theo đúng thứ tự: Laptop -> Mouse -> Keyboard
    }
}

2. Thứ tự truy cập (Access Order - LRU)

Để kích hoạt chế độ này, ta cần sử dụng constructor có tham số accessOrder là true.

import java.util.*;

public class AccessOrderDemo {
    public static void main(String[] args) {
        // Tham số thứ 3 (true) kích hoạt chế độ truy cập
        Map<String, String> cache = new LinkedHashMap<>(16, 0.75f, true);
        
        cache.put("A", "Data A");
        cache.put("B", "Data B");
        cache.put("C", "Data C");

        // Truy cập phần tử "A"
        System.out.println("Get A: " + cache.get("A"));

        // Sau khi truy cập "A", nó sẽ bị di chuyển xuống cuối danh sách
        System.out.println("Iteration order:");
        cache.forEach((k, v) -> System.out.println(k + " = " + v));
        
        // Kết quả in ra: B, C, A
    }
}

Phân tích mã nguồn (Source Code Analysis)

1. Cấu trúc lớp và các biến thành viên

LinkedHashMap mở rộng HashMap và định nghĩa lại node (nút) để thêm các con trỏ before và after phục vụ cho danh sách liên kết kép.

public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V> {

    // Node mở rộng từ HashMap.Node, thêm vào con trỏ trước và sau
    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }

    // Con trỏ đầu và cuối của danh sách liên kết kép
    transient LinkedHashMap.Entry<K,V> head;
    transient LinkedHashMap.Entry<K,V> tail;

    // Biến cờ xác định loại thứ tự: false = chèn, true = truy cập
    final boolean accessOrder;

    // Constructor mặc định
    public LinkedHashMap() {
        super();
        accessOrder = false; // Mặc định là thứ tự chèn
    }
}

2. Cơ chế hoạt động của phương thức put

Phương thức put của LinkedHashMap gọi trực tiếp putVal của lớp cha HashMap. Tuy nhiên, nó ghi đè (override) một số phương thức hook (móc nối) để duy trì danh sách liên kết.

• Tạo node mới (newNode): Khi thêm một cặp key-value hoàn toàn mới, HashMap sẽ gọi phương thức newNode. LinkedHashMap ghi đè phương thức này để tạo một Entry và nối nó vào cuối danh sách liên kết (linkNodeLast).

Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    linkNodeLast(p); // Nối node mới vào cuối (tail)
    return p;
}

• Cập nhật node tồn tại (afterNodeAccess): Nếu key đã tồn tại và giá trị value được cập nhật, phương thức afterNodeAccess sẽ được gọi. Nếu accessOrder là true, node này sẽ được di chuyển xuống cuối danh sách.

void afterNodeAccess(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> last;
    // Chỉ di chuyển nếu accessOrder là true và node không phải đang ở cuối
    if (accessOrder && (last = tail) != e) {
        LinkedHashMap.Entry<K,V> p =
            (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
        
        p.after = null;
        if (b == null)
            head = a;
        else
            b.after = a;
        
        if (a != null)
            a.before = b;
        else
            last = b;
            
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
        tail = p;
        ++modCount;
    }
}

• Xóa node cũ nhất (afterNodeInsertion): Sau khi chèn, phương thức này được gọi. Nó kiểm tra removeEldestEntry. Nếu trả về true, node đầu (đã lâu không được truy cập) sẽ bị xóa. Đây là chìa khóa để xây dựng Cache LRU giới hạn dung lượng.

3. Cơ chế hoạt động của phương thức get

Phương thức get gọi getNode của HashMap để tìm kiếm. Nếu tìm thấy và accessOrder là true, nó sẽ gọi afterNodeAccess để đưa node vừa được truy cập xuống cuối danh sách.

public V get(Object key) {
    Node<K,V> e;
    if ((e = getNode(hash(key), key)) == null)
        return null;
    if (accessOrder) // Nếu chế độ truy cập được bật
        afterNodeAccess(e); // Di chuyển node xuống cuối
    return e.value;
}

4. Cơ chế xóa (Remove)

Phương thức remove được kế thừa từ HashMap. Sau khi node bị xóa khỏi bucket (mảng), phương thức callback afterNodeRemoval sẽ được gọi để ngắt kết nối node này khỏi danh sách liên kết kép.

void afterNodeRemoval(Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
    
    p.before = p.after = null;
    
    if (b == null)
        head = a;
    else
        b.after = a;
        
    if (a == null)
        tail = b;
    else
        a.before = b;
}

5. Tối ưu hóa containsValue

Khi gọi containsValue, thay vì phải duyệt qua toàn bộ các bucket của HashMap (cách làm của HashMap), LinkedHashMap chỉ cần duyệt qua danh sách liên kết kép của nó. Điều này giúp việc kiểm tra tồn tại của value nhanh hơn rất nhiều.

public boolean containsValue(Object value) {
    // Duyệt từ head đến tail thay vì duyệt mảng
    for (LinkedHashMap.Entry<K,V> e = head; e != null; e = e.after) {
        V v = e.value;
        if (v == value || (value != null && value.equals(v)))
            return true;
    }
    return false;
}

6. Iterator và cơ chế duyệt

Các iterator trả về bởi entrySet(), keySet(), hoặc values() sẽ duyệt theo danh sách liên kết kép (từ head đến tail) thay vì theo thứ tự của bảng băm (bucket array). Điều này đảm bảo output luôn có thứ tự nhất quán.

Tóm tắt kỹ thuật

LinkedHashMap kết hợp ưu điểm của HashMap về hiệu suất tìm kiếm O(1) với khả năng duy trì thứ tự thông qua danh sách liên kết kép. Việc quản lý thứ tự được thực hiện mượt mà thông qua các phương thức hook (afterNodeAccess, afterNodeInsertion, afterNodeRemoval) được gọi bởi các phương thức của lớp cha HashMap. Cấu trúc này là nền tảng lý tưởng để triển khai các thuật toán LRU Cache một cách hiệu quả trong Java.