1. LinkedHashMap là gì?
LinkedHashMap trong Java là một cấu trúc dữ liệu thuộc loại Map, được kế thừa từ HashMap nhưng duy trì thứ tự của các phần tử. Khác với HashMap các phần tử trong LinkedHashMap không chỉ được lưu trữ dựa trên giá trị hash mà còn được duy trì theo thứ tự thêm vào hoặc thứ tự truy cập gần nhất. Điều này được thực hiện nhờ một danh sách liên kết kép (doubly-linked list) được liên kết với từng phần tử.
2. Đặc điểm chính của LinkedHashMap
- Thứ tự phần tử:
- Thứ tự thêm vào (Insertion Order): Các phần tử được duy trì theo thứ tự thêm vào.
- Thứ tự truy cập (Access Order): Nếu cấu hình theo cách này, phần tử được truy cập gần nhất sẽ được di chuyển lên đầu (điều này hữu ích cho các trường hợp như cache LRU – Least Recently Used).
- Hiệu suất:
LinkedHashMapcó hiệu suất gần tương đươngHashMapcho các thao tác như thêm, xoá và truy cập phần tử với độ phức tạp trung bình làO(1)cho các thao tác này.- Tuy nhiên
LinkedHashMapsẽ tốn bộ nhớ hơn một chút do cần thêm liên kết kép để duy trì thứ tự.
- Cho phép giá trị
null:LinkedHashMapcho phép cả khóa (key) và giá trị (value) có thể lànull. - Sử dụng trong các trường hợp đặc biệt:
LinkedHashMaphữu ích khi cần duy trì thứ tự phần tử như thứ tự thêm vào hoặc gần đây nhất, ví dụ như cache LRU.
– Ví dụ:
import java.util.LinkedHashMap;
import java.util.Map;
public class App {
public static void main(String[] args) {
// Tạo LinkedHashMap với thứ tự thêm vào
Map<String, Integer> linkedHashMap = new LinkedHashMap<>();
// Thêm các phần tử vào LinkedHashMap
linkedHashMap.put("Một", 1);
linkedHashMap.put("Hai", 2);
linkedHashMap.put("Ba", 3);
linkedHashMap.put("Bốn", 4);
// Duyệt qua các phần tử của LinkedHashMap
System.out.println("LinkedHashMap (theo thứ tự thêm vào): " + linkedHashMap);
// Truy cập phần tử để xem thứ tự
linkedHashMap.get("Hai");
linkedHashMap.get("Ba");
// Duyệt qua các phần tử của LinkedHashMap sau khi truy cập
System.out.println("LinkedHashMap sau khi truy cập (không thay đổi thứ tự): " + linkedHashMap);
}
}
– Kết quả:
LinkedHashMap (theo thứ tự thêm vào): {Một=1, Hai=2, Ba=3, Bốn=4}
LinkedHashMap sau khi truy cập (không thay đổi thứ tự): {Một=1, Hai=2, Ba=3, Bốn=4}
3. Sử dụng LinkedHashMap
LinkedHashMap là lựa chọn lý tưởng khi cần duy trì thứ tự phần tử và cần hiệu suất cao cho các thao tác thêm, tìm kiếm.
– Để thiết lập thứ tự truy cập gần nhất, bạn có thể sử dụng constructor LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) với accessOrder được đặt là true.
import java.util.LinkedHashMap;
import java.util.Map;
public class App {
public static void main(String[] args) {
Map<String, Integer> cache = new LinkedHashMap<>(16, 0.75f, true);
cache.put("Một", 1);
cache.put("Hai", 2);
cache.put("Ba", 3);
cache.get("Một"); // "Một" được di chuyển lên đầu
System.out.println("LinkedHashMap theo thứ tự truy cập: " + cache);
}
}
4. Câu hỏi phỏng vấn LinkedHashMap
1. LinkedHashMap là gì và khác gì với HashMap?
Trả lời:
LinkedHashMap là một lớp triển khai của Map trong Java, LinkedHashMap duy trì thứ tự của các phần tử dựa trên thứ tự thêm vào (insertion order) hoặc thứ tự truy cập (access order). Khác với HashMap, các phần tử trong LinkedHashMap luôn được duy trì thứ tự và có thể được cấu hình để theo dõi thứ tự truy cập gần nhất (LRU).
2. LinkedHashMap hoạt động như thế nào?
Trả lời:
LinkedHashMap sử dụng cấu trúc bảng băm (hash table) kết hợp với danh sách liên kết kép để duy trì thứ tự các phần tử. Các phần tử được lưu trữ theo thứ tự chèn hoặc truy cập, tùy theo cấu hình.
3. Khi nào nên sử dụng LinkedHashMap thay vì HashMap?
Trả lời:
LinkedHashMap nên được sử dụng khi cần duy trì thứ tự của các phần tử, chẳng hạn như trong cache, lịch sử truy cập hoặc khi cần lưu trữ các phần tử và duyệt chúng theo thứ tự thêm vào hoặc truy cập gần nhất.
4. LinkedHashMap có cho phép giá trị null không?
Trả lời:
Có, LinkedHashMap cho phép cả khóa (key) và giá trị (value) là null, giống như HashMap.
5. Làm thế nào để thiết lập LinkedHashMap hoạt động theo thứ tự truy cập?
Trả lời:
Có thể thiết lập LinkedHashMap hoạt động theo thứ tự truy cập gần nhất (access order) bằng cách sử dụng constructor LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) với accessOrder đặt là true.
6. LRU Cache là gì? LinkedHashMap có hỗ trợ không?
Trả lời:
LRU (Least Recently Used) Cache là một cơ chế quản lý cache mà phần tử ít được truy cập nhất sẽ bị xóa khi cần thêm phần tử mới. LinkedHashMap hỗ trợ việc này thông qua cấu hình accessOrder=true và ghi đè phương thức removeEldestEntry(Map.Entry<K, V> eldest) để xóa phần tử cũ nhất khi cần.
7. Độ phức tạp thời gian của các thao tác trong LinkedHashMap là gì?
Trả lời:
Các thao tác thêm (put), tìm kiếm (get) và xóa (remove) trong LinkedHashMap có độ phức tạp trung bình là O(1), tương tự như HashMap.
8. Có bao nhiêu cấu tử (constructor) của LinkedHashMap và công dụng của chúng là gì?
Trả lời: LinkedHashMap có bốn constructor:
LinkedHashMap(): Khởi tạoLinkedHashMaprỗng với dung lượng mặc định.LinkedHashMap(int initialCapacity): Khởi tạo với dung lượng tùy chọn.LinkedHashMap(int initialCapacity, float loadFactor): Khởi tạo với dung lượng và hệ số tải tùy chọn.LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder): Khởi tạo với dung lượng, hệ số tải và thứ tự (accessOrder=truecho thứ tự truy cập gần nhất).
9. LinkedHashMap có an toàn khi sử dụng trong môi trường đa luồng không?
Trả lời:
Không, LinkedHashMap không phải là thread-safe. Để sử dụng trong môi trường đa luồng bạn có thể dùng Collections.synchronizedMap(new LinkedHashMap<>()) để có thể sử dụng an toàn trong môi trường đa luồng hoặc dùng các thư viện đồng bộ hóa khác như ConcurrentHashMap.
10. Làm cách nào để xóa phần tử ít được truy cập nhất trong LinkedHashMap?
Trả lời:
Để xóa phần tử ít được truy cập nhất (LRU) cần thiết lập accessOrder=true khi tạo LinkedHashMap và ghi đè phương thức removeEldestEntry. Phương thức này trả về true khi kích thước LinkedHashMap vượt quá ngưỡng mong muốn, từ đó phần tử lâu nhất sẽ bị xóa tự động.
