LinkedHashSet/LinkedHashMap

1. LinkedHashSet và LinkedHashMap là gì?

Trong thư viện chuẩn Java có một số hiện thực của các collection Set và Map. Nổi tiếng nhất là HashSet và HashMap. Các cấu trúc này cung cấp truy cập nhanh dựa trên hash, nhưng không bảo đảm bất kỳ thứ tự nào khi duyệt phần tử. Khi thứ tự duyệt quan trọng — LinkedHashSet và LinkedHashMap sẽ phát huy tác dụng.

• LinkedHashSet là một Set ghi nhớ thứ tự thêm phần tử.
• LinkedHashMap là một Map ghi nhớ thứ tự thêm cặp khóa–giá trị (hoặc, nếu muốn, thứ tự truy cập).

Chúng được hiện thực như HashSet/HashMap “thông thường”, nhưng được bổ sung một danh sách liên kết kép để lưu trữ thứ tự phần tử.

2. Thứ tự chèn và thứ tự truy cập

Thứ tự chèn

Mặc định, LinkedHashSet và LinkedHashMap bảo đảm rằng khi duyệt, các phần tử được trả về theo đúng thứ tự chúng đã được thêm vào (for-each/iterator).

Set<String> set = new LinkedHashSet<>();
set.add("A");
set.add("B");
set.add("C");
for (String s : set) {
    System.out.println(s);
}
// Sẽ in: A B C

Map<Integer, String> map = new LinkedHashMap<>();
map.put(1, "one");
map.put(2, "two");
map.put(3, "three");
for (Integer key : map.keySet()) {
    System.out.println(key + " -> " + map.get(key));
}
// Sẽ in: 1 -> one, 2 -> two, 3 -> three

Thứ tự truy cập (chỉ dành cho LinkedHashMap)

LinkedHashMap có chế độ thứ tự theo lần truy cập gần nhất (access order). Nếu truyền true làm tham số thứ ba của constructor khi tạo map, thì mỗi lần truy cập một phần tử (get/put) nó sẽ được chuyển xuống cuối danh sách.

Map<Integer, String> lruMap = new LinkedHashMap<>(16, 0.75f, true);
lruMap.put(1, "one");
lruMap.put(2, "two");
lruMap.put(3, "three");

lruMap.get(2); // Truy cập khóa 2

for (Integer key : lruMap.keySet()) {
    System.out.println(key);
}
// Sẽ in: 1 3 2 (2 là cuối cùng vì vừa được truy cập)

LRU cache thông qua removeEldestEntry

“Điểm mạnh” của LinkedHashMap là hiện thực LRU cache (Least Recently Used, “ít được sử dụng gần đây nhất”) rất đơn giản. Chỉ cần ghi đè phương thức removeEldestEntry(Map.Entry<K,V> eldest): nếu nó trả về true, phần tử “già” nhất sẽ bị xóa khi thêm phần tử mới.

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

    public LRUCache(int maxSize) {
        super(maxSize, 0.75f, true); // true — thứ tự theo truy cập
        this.maxSize = maxSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;
    }
}

// Sử dụng:
LRUCache<Integer, String> cache = new LRUCache<>(3);
cache.put(1, "one");
cache.put(2, "two");
cache.put(3, "three");
cache.get(1); // Khiến 1 trở thành phần tử “mới” nhất
cache.put(4, "four"); // 2 sẽ bị loại (cũ nhất)
System.out.println(cache.keySet()); // [3, 1, 4]

3. Chi phí bộ nhớ và tốc độ: LinkedHashSet/LinkedHashMap vs HashSet/HashMap

Cấu trúc bên trong

Bên trong — gần giống HashSet/HashMap thông thường, nhưng mỗi phần tử còn được lưu trong một danh sách liên kết kép. Cấu trúc bổ sung này “ghi nhớ” thứ tự thêm/truy cập.

Chi phí bộ nhớ

Do có các tham chiếu prev/next trên mỗi nút nên cần nhiều bộ nhớ hơn. Với hàng triệu phần tử điều này đáng kể; còn với các bài toán điển hình — đây là cái giá hợp lý để đổi lấy thứ tự xác định.

Hiệu năng

Các thao tác cơ bản thêm/tìm/xóa vẫn có độ phức tạp trung bình O(1). Việc duyệt sẽ chậm hơn đôi chút do phải đi qua danh sách, nhưng trong đa số trường hợp khác biệt là tối thiểu. Và kịch bản “xóa phần tử cũ nhất” (LRU) được hiện thực rất hiệu quả, vì phần tử “già” nhất luôn ở đầu danh sách.

Kết luận: nếu thứ tự quan trọng — hãy chọn LinkedHashSet/LinkedHashMap. Nếu cần tiết kiệm bộ nhớ và không cần thứ tự — HashSet/HashMap là đủ.

4. Cache, đầu ra xác định, kiểm thử ổn định

Cache (LRU)

LinkedHashMap là nền tảng lý tưởng cho các cache giới hạn kích thước với cơ chế tự động loại bỏ phần tử “cũ”. Được dùng trong thư viện/framework, khi làm việc với tệp, ảnh, kết quả tính toán.

Đầu ra xác định

Cho báo cáo, xuất dữ liệu, tuần tự hóa (serialization), nơi cách biểu diễn dữ liệu phải dự đoán được, hãy dùng LinkedHashSet/LinkedHashMap. Điều này đặc biệt quan trọng cho kiểm thử — thứ tự không “nhảy múa” giữa các lần chạy.

Kiểm thử ổn định

Trong unit test, người ta thường so sánh collection kỳ vọng với collection thực tế. Nếu thứ tự không được đảm bảo, test có thể “flaky”. Với các hiện thực “linked” — tính xác định mang lại sự ổn định.

Ví dụ: so sánh HashMap và LinkedHashMap

Map<Integer, String> hashMap = new HashMap<>();
Map<Integer, String> linkedMap = new LinkedHashMap<>();

for (int i = 1; i <= 5; i++) {
    hashMap.put(i, "val" + i);
    linkedMap.put(i, "val" + i);
}

System.out.println(hashMap.keySet());   // Thứ tự có thể bất kỳ!
System.out.println(linkedMap.keySet()); // Luôn 1, 2, 3, 4, 5

5. LinkedList vs ArrayDeque cho hàng đợi

LinkedList

• Triển khai các interface List, Deque, Queue.
• Danh sách liên kết kép: chèn/xóa nhanh ở đầu và cuối.
• Có thể dùng làm hàng đợi (FIFO), ngăn xếp (LIFO), hàng đợi hai đầu.

ArrayDeque

• Triển khai Deque, Queue (nhưng không phải List).
• Dựa trên mảng, tự động mở rộng.
• Thường nhanh hơn LinkedList cho các thao tác hàng đợi/ngăn xếp; overhead thấp hơn.
• Không hỗ trợ phần tử null.

Khi nào dùng cái nào?

• Hàng đợi và ngăn xếp — hầu như luôn là ArrayDeque.
• Nhiều chèn/xóa ở giữa và còn cần danh sách — LinkedList.
• Set/Map có thứ tự — LinkedHashSet/LinkedHashMap.

Ví dụ: hàng đợi công việc

Queue<String> queue = new ArrayDeque<>();
queue.add("task1");
queue.add("task2");
System.out.println(queue.poll()); // task1

Ví dụ: ngăn xếp

Deque<String> stack = new ArrayDeque<>();
stack.push("first");
stack.push("second");
System.out.println(stack.pop()); // second

Kết luận:
— Đối với hàng đợi và ngăn xếp — ArrayDeque.
— Đối với danh sách có nhiều chèn ở giữa — LinkedList.
— Đối với Set/Map có thứ tự — LinkedHashSet/LinkedHashMap.

6. Các lỗi thường gặp khi làm việc với LinkedHashSet/LinkedHashMap

Lỗi số 1: Kỳ vọng HashSet/HashMap giữ nguyên thứ tự.
HashSet/HashMap không đảm bảo thứ tự. Nếu thứ tự quan trọng — hãy dùng LinkedHashSet/LinkedHashMap.

Lỗi số 2: Dùng LinkedHashMap làm cache mà không ghi đè removeEldestEntry.
Đối với LRU cần ghi đè removeEldestEntry, nếu không map sẽ tăng kích thước không giới hạn.

Lỗi số 3: Dùng LinkedList cho hàng đợi/ngăn xếp khi không cần thiết.
Trong đa số trường hợp ArrayDeque nhanh hơn và tiết kiệm hơn.

Lỗi số 4: Kỳ vọng LinkedHashMap sẽ sắp xếp.
LinkedHashMap giữ thứ tự thêm/truy cập, nhưng không sắp xếp theo khóa. Để sắp xếp — dùng TreeMap.

Lỗi số 5: Thêm null vào ArrayDeque.
ArrayDeque không hỗ trợ phần tử null — sẽ ném NullPointerException.

Lỗi số 6: So sánh collection mà không tính đến thứ tự.
Khi so sánh LinkedHashSet/LinkedHashMap với HashSet/HashMap thông thường, hãy lưu ý sự khác biệt về thứ tự phần tử.