Class LinkedHashMap<K,V>

LinkedHashMap sử dụng một bảng băm (hash table) để lưu trữ các phần tử, tương tự như HashMap. Ngoài ra, LinkedHashMap duy trì một danh sách liên kết kép (doubly-linked list) để giữ thứ tự duyệt (iteration order) của các phần tử. Thứ tự duyệt trong LinkedHashMap thường là thứ tự các khóa (keys) được chèn vào bản đồ (insertion-order).

Sự khác biệt với HashMap: LinkedHashMap khác với HashMap ở chỗ nó duy trì thứ tự chèn (insertion-order) của các phần tử, trong khi HashMap không đảm bảo thứ tự này. Khi một khóa được chèn lại (đã tồn tại trong bản đồ trước đó), thứ tự duyệt không bị thay đổi.

Cấu trúc của một phần tử trong LinkedHashMap

LinkedHashMap là một lớp trong Java kế thừa từ HashMap, nhưng nó giữ thêm một danh sách liên kết để duy trì thứ tự chèn các phần tử. Điều này có nghĩa là ngoài việc sử dụng hàm băm để xác định vị trí của một phần tử, LinkedHashMap còn lưu trữ thông tin về thứ tự mà các phần tử được thêm vào.

Trong LinkedHashMap, mỗi phần tử được lưu trữ dưới dạng một nút (node) và chứa các thành phần chính sau:

1. Key (Khóa)

↳ Đây là giá trị của khóa mà bạn sử dụng để ánh xạ tới giá trị trong bản đồ.

↳ Ví dụ: Trong một ánh xạ map.put(key, value), key là khóa.

2. Value (Giá Trị)

↳ Đây là giá trị mà bạn lưu trữ và ánh xạ tới khóa trong bản đồ.

↳ Ví dụ: Trong map.put(key, value), value là giá trị.

3. Hash Code

↳ Hash code là một giá trị nguyên được tính toán từ khóa. Hash code này giúp xác định vị trí của phần tử trong bảng băm (hash table).

4. Previous Pointer (Con Trỏ Trước)

↳ Trỏ đến nút trước trong danh sách liên kết kép.

↳ Con trỏ này giúp duy trì thứ tự của các phần tử theo thứ tự chèn vào.

↳ Đối với nút đầu tiên trong danh sách liên kết, con trỏ này sẽ trỏ đến null.

5. Next Pointer (Con Trỏ Sau)

↳ Trỏ đến nút tiếp theo trong danh sách liên kết kép.

↳ Con trỏ này cũng giúp duy trì thứ tự của các phần tử.

↳ Đối với nút cuối cùng trong danh sách liên kết, con trỏ này sẽ trỏ đến null.

↳ Con trỏ trước và sau: Được sử dụng để duy trì danh sách liên kết kép, giúp duyệt qua các phần tử theo thứ tự chèn vào. Điều này là khác biệt chính giữa LinkedHashMap và HashMap, trong đó HashMap không duy trì thứ tự chèn vào.

Yêu cầu: Phải ghi đè phương thức hashCode() để đảm bảo phân phối đều trong các bucket. Cũng phải ghi đè phương thức equals() để so sánh các khóa.

Đặc điểm nổi bậc của LinkedHashMap<K,V>

Khi bạn cần một Map không chỉ lưu trữ các cặp khóa-giá trị mà còn ghi nhớ thứ tự của chúng, LinkedHashMap là lựa chọn lý tưởng. Khác với HashMap vốn không đảm bảo thứ tự, LinkedHashMap kết hợp hiệu suất của bảng băm với khả năng duy trì trật tự của các phần tử. Hãy cùng khám phá những đặc điểm nổi bật làm nên sự khác biệt của nó:

↳ Duy trì thứ tự chèn (Insertion Order) hoặc thứ tự truy cập (Access Order): LinkedHashMap duy trì thứ tự duyệt các phần tử dựa trên thứ tự mà các phần tử được chèn vào map (insertion-order). Điều này khác với HashMap, vốn không đảm bảo thứ tự duyệt các phần tử. Ngoài ra, LinkedHashMap có thể được cấu hình để duy trì thứ tự dựa trên thời gian truy cập (access-order) nếu được khởi tạo với tùy chọn này.

↳ Hiệu suất tốt: LinkedHashMap cung cấp hiệu suất gần như tương tự với HashMap cho các thao tác cơ bản như thêm (put), tìm kiếm (get), và xóa (remove) các phần tử, với thời gian thực thi trung bình là O(1). Tuy nhiên, LinkedHashMap có thể tốn thêm một chút tài nguyên do phải duy trì danh sách liên kết đôi (doubly-linked list) để lưu thứ tự các phần tử.

↳ LinkedHashMap có thể chứa một khóa null và cho phép nhiều giá trị null.

↳ Chứa các phần tử duy nhất: LinkedHashMap đảm bảo rằng mỗi khóa trong map là duy nhất. Không thể có hai khóa trùng lặp, nhưng các giá trị có thể trùng lặp.

↳ Đồng bộ hóa (Synchronization): LinkedHashMap không được đồng bộ hóa mặc định. Điều này có nghĩa là nếu nhiều luồng (threads) truy cập vào LinkedHashMap cùng một lúc và ít nhất một luồng thay đổi cấu trúc của map, thì map này cần được đồng bộ hóa bên ngoài. Để đồng bộ hóa, bạn có thể bọc LinkedHashMap bằng Collections.synchronizedMap khi tạo đối tượng:

Map m = Collections.synchronizedMap(new LinkedHashMap(...));

↳ Tính năng fail-fast của Iterator: Các iterator của LinkedHashMap là fail-fast, có nghĩa là chúng sẽ ném ra ngoại lệ ConcurrentModificationException nếu map bị thay đổi cấu trúc trong khi đang duyệt qua iterator, giúp phát hiện các lỗi đồng thời (concurrency bugs) sớm.

Khai báo Class LinkedHashMap<K,V> trong Java

Để sử dụng Class LinkedHashMap<K,V>, bạn cần import gói java.util vào đầu file Java của mình.

Cú pháp câu lệnh import:

import java.util.LinkedHashMap;

Cú pháp khai báo Class LinkedHashMap<K,V>:

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

Dưới đây là giải thích chi tiết về cú pháp khai báo này:

↳ public: Lớp LinkedHashMap có thể được truy cập từ bất kỳ đâu trong chương trình.

↳ class LinkedHashMap<K,V>: Khai báo một lớp có tên LinkedHashMap, sử dụng generic với K là kiểu khóa và V là kiểu giá trị.

↳ extends HashMap<K,V>: Kế thừa toàn bộ chức năng của HashMap, nhưng bổ sung thêm tính năng duy trì thứ tự thêm phần tử (insertion order).

↳ implements Map<K,V>: LinkedHashMap triển khai giao diện Map. Giao diện Map định nghĩa các phương thức chung cho các cấu trúc dữ liệu ánh xạ (mapping), và LinkedHashMap phải cung cấp các triển khai cụ thể cho những phương thức này.

LinkedHashMap là một phiên bản nâng cấp của HashMap với một tính năng quan trọng: nó duy trì thứ tự các phần tử dựa trên thứ tự chèn vào (insertion order). Điều này có nghĩa là khi bạn duyệt qua LinkedHashMap, các phần tử sẽ xuất hiện theo đúng thứ tự mà chúng được thêm vào, khác với HashMap không duy trì thứ tự này.

Các constructor của lớp LinkedHashMap

Lớp LinkedHashMap cung cấp các constructor để tạo một bản đồ được sắp xếp theo thứ tự chèn với các tùy chọn về dung lượng ban đầu, hệ số tải và chế độ sắp xếp. Dưới đây là năm constructor của lớp LinkedHashMap:

↳ LinkedHashMap(): Khởi tạo một LinkedHashMap theo thứ tự chèn rỗng với dung lượng ban đầu mặc định (16) và hệ số tải mặc định (0.75).

↳ LinkedHashMap(int initialCapacity): Khởi tạo một LinkedHashMap theo thứ tự chèn rỗng với dung lượng ban đầu được chỉ định và hệ số tải mặc định (0.75).

↳ LinkedHashMap(int initialCapacity, float loadFactor): Khởi tạo một LinkedHashMap theo thứ tự chèn rỗng với dung lượng ban đầu được chỉ định và hệ số tải được chỉ định.

↳ LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder): Khởi tạo một LinkedHashMap rỗng với dung lượng ban đầu được chỉ định, hệ số tải và chế độ sắp xếp.

↳ LinkedHashMap(Map<? extends K, ? extends V> m): Khởi tạo một LinkedHashMap theo thứ tự chèn với các ánh xạ giống như bản đồ được chỉ định.

  // 1. Tạo LinkedHashMap rỗng theo thứ tự chèn, dung lượng và hệ số tải mặc định
  LinkedHashMap<String, Integer> map1 = new LinkedHashMap<>();

  // 2. Tạo LinkedHashMap rỗng theo thứ tự chèn, dung lượng 10, hệ số tải mặc định
  LinkedHashMap<String, Integer> map2 = new LinkedHashMap<>(10);

  // 3. Tạo LinkedHashMap rỗng theo thứ tự chèn, dung lượng 20, hệ số tải 0.8
  LinkedHashMap<String, Integer> map3 = new LinkedHashMap<>(20, 0.8f);

  // 4. Tạo LinkedHashMap theo thứ tự truy cập, dung lượng 16, hệ số tải 0.75
  LinkedHashMap<String, Integer> map4 = new LinkedHashMap<>(16, 0.75f, true);

  // 5. Tạo LinkedHashMap từ một HashMap
  Map<String, Integer> tempMap = new HashMap<>();
  LinkedHashMap<String, Integer> map5 = new LinkedHashMap<>(tempMap);

Lưu ý:

↳ LinkedHashMap là một bản đồ được sắp xếp theo thứ tự chèn, nghĩa là các mục nhập sẽ được lưu trữ theo thứ tự chúng được thêm vào.

↳ Dung lượng ban đầu và hệ số tải được sử dụng để điều chỉnh kích thước của bảng băm và khi nào bảng băm cần được tăng kích thước.

↳ Chế độ sắp xếp có thể là true (sắp xếp theo thứ tự truy cập) hoặc false (sắp xếp theo thứ tự chèn).

Các phương thức chính trong lớp LinkedHashMap

Lớp LinkedHashMap cung cấp các phương thức để thao tác với các cặp khóa-giá trị trong một bản đồ được sắp xếp theo thứ tự chèn. Bạn có thể sử dụng các phương thức này để thêm, xóa, lấy, kiểm tra và duyệt qua các mục nhập trong bản đồ. Dưới đây là danh sách tất cả các phương thức của lớp LinkedHashMap<K,V> trong Java:

↳ void clear(): Xóa tất cả các ánh xạ khỏi bản đồ này.

↳ boolean containsValue(Object value): Trả về true nếu bản đồ này ánh xạ một hoặc nhiều khóa đến giá trị đã cho.

↳ Set<Map.Entry<K,V>> entrySet(): Trả về một view Set của các ánh xạ có trong bản đồ này.

↳ void forEach(BiConsumer<? super K, ? super V> action): Thực hiện hành động đã cho cho mỗi mục nhập trong bản đồ này cho đến khi tất cả các mục nhập đã được xử lý hoặc hành động ném ra một ngoại lệ.

↳ V get(Object key): Trả về giá trị mà khóa đã cho được ánh xạ đến, hoặc null nếu bản đồ này không chứa ánh xạ nào cho khóa.

↳ V getOrDefault(Object key, V defaultValue): Trả về giá trị mà khóa đã cho được ánh xạ đến, hoặc defaultValue nếu bản đồ này không chứa ánh xạ nào cho khóa.

↳ Set<K> keySet(): Trả về một view Set của các khóa có trong bản đồ này.

↳ protected boolean removeEldestEntry(Map.Entry<K,V> eldest): Trả về true nếu bản đồ này nên xóa mục nhập lớn tuổi nhất của nó.

↳ void replaceAll(BiFunction<? super K, ? super V, ? extends V> function): Thay thế giá trị của mỗi mục nhập bằng kết quả của việc gọi hàm đã cho trên mục nhập đó cho đến khi tất cả các mục nhập đã được xử lý hoặc hàm ném ra một ngoại lệ.

↳ Collection<V> values(): Trả về một view Collection của các giá trị có trong bản đồ này.

Ví dụ về cách sử dụng các phương thức put(), get(), containsKey(), remove(), size() và isEmpty()

Dưới đây là ví dụ về cách thêm, xóa, truy xuất và kiểm tra các phần tử trong LinkedHashMap trong Java:

import java.util.LinkedHashMap;

public class Example {
    public static void main(String[] args) {
        // Tạo một LinkedHashMap
        LinkedHashMap<Integer, String> linkedHashMap = new LinkedHashMap<>();

        // Thêm phần tử vào LinkedHashMap
        linkedHashMap.put(1, "Apple");
        linkedHashMap.put(2, "Banana");
        linkedHashMap.put(3, "Cherry");

        // Hiển thị LinkedHashMap sau khi thêm
        System.out.println("LinkedHashMap sau khi thêm: " + linkedHashMap);

        // Lấy giá trị với khóa 2
        String value = linkedHashMap.get(2);
        System.out.println("Giá trị của khóa 2: " + value);

        // Kiểm tra xem LinkedHashMap có chứa khóa 3 hay không
        boolean containsKey = linkedHashMap.containsKey(3);
        System.out.println("LinkedHashMap có chứa khóa 3 không? " + containsKey);

        // Xóa phần tử với khóa 1
        linkedHashMap.remove(1);

        // Hiển thị LinkedHashMap sau khi xóa
        System.out.println("LinkedHashMap sau khi xóa khóa 1:" + linkedHashMap);

        // Kiểm tra kích thước của LinkedHashMap
        int size = linkedHashMap.size();
        System.out.println("Kích thước của LinkedHashMap: " + size);

        // Kiểm tra xem LinkedHashMap có rỗng không
        boolean isEmpty = linkedHashMap.isEmpty();
        System.out.println("LinkedHashMap có rỗng không? " + isEmpty);
    }
}

Ví dụ về cách sử dụng các phương thức entrySet()

Dưới đây là một ví dụ về cách sử dụng phương thức entrySet() trong lớp LinkedHashMap:

import java.util.LinkedHashMap;
import java.util.Map;

public class Example {
    public static void main(String[] args) {
        // Tạo một LinkedHashMap
        LinkedHashMap<Integer, String> linkedHashMap = new LinkedHashMap<>();

        // Thêm phần tử vào LinkedHashMap
        linkedHashMap.put(1, "Apple");
        linkedHashMap.put(2, "Banana");
        linkedHashMap.put(3, "Cherry");

        // Sử dụng entrySet() để lấy tập hợp các cặp khóa-giá trị
        System.out.println("Các cặp khóa-giá trị trong LinkedHashMap:");
        for (Map.Entry<Integer, String> entry : linkedHashMap.entrySet()) {
            System.out.println("Khóa: " + entry.getKey() + ", Giá trị: " + entry.getValue());
        }

        // Sử dụng entrySet() và vòng lặp để thay đổi giá trị
        for (Map.Entry<Integer, String> entry : linkedHashMap.entrySet()) {
            if (entry.getKey() == 2) {
                entry.setValue("Blueberry"); // Thay đổi giá trị của khóa 2
            }
        }

        // Hiển thị LinkedHashMap sau khi thay đổi
        System.out.println("LinkedHashMap sau khi thay đổi giá trị của khóa 2:");
        for (Map.Entry<Integer, String> entry : linkedHashMap.entrySet()) {
            System.out.println("Khóa: " + entry.getKey() + ", Giá trị: " + entry.getValue());
        }
    }
}

Sử dụng Iterator duyệt các phần tử của LinkedHashMap

Để duyệt qua các phần tử của một LinkedHashMap bằng cách sử dụng Iterator, bạn có thể sử dụng các iterator cho keySet(), values(), hoặc entrySet(). Dưới đây là một ví dụ đơn giản về cách sử dụng Iterator để duyệt các phần tử của LinkedHashMap bằng cách sử dụng tất cả ba phương pháp này.

import java.util.Iterator;
import java.util.LinkedHashMap;
import java.util.Map;

public class Example {
    public static void main(String[] args) {
        // Tạo một LinkedHashMap
        LinkedHashMap<Integer, String> linkedHashMap = new LinkedHashMap<>();

        // Thêm phần tử vào LinkedHashMap
        linkedHashMap.put(1, "Apple");
        linkedHashMap.put(2, "Banana");
        linkedHashMap.put(3, "Cherry");

        // Sử dụng Iterator để duyệt các phần tử của LinkedHashMap
        System.out.println("Các phần tử của LinkedHashMap:");
        Iterator<Map.Entry<Integer, String>> iterator = linkedHashMap.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Integer, String> entry = iterator.next();
            System.out.println("Khóa: " + entry.getKey() + ", Giá trị: " + entry.getValue());
        }
    }
}

Ví dụ về việc sử dụng LinkedHashMap trong Java với các lớp do người dùng tự định nghĩa

Dưới đây là một ví dụ về cách sử dụng LinkedHashMap trong Java với các lớp do người dùng tự định nghĩa. Trong ví dụ này, chúng ta sẽ tạo một lớp Student và sử dụng LinkedHashMap để lưu trữ các đối tượng Student với ID làm khóa.

import java.util.LinkedHashMap;
import java.util.Map;

// Lớp Student do người dùng tự định nghĩa
class Student {
    private int id;
    private String name;
    
    // Constructor
    public Student(int id, String name) {
        this.id = id;
        this.name = name;
    }

    // Getter và Setter
    public int getId() {
        return id;
    }

    public void setId(int id) {
        this.id = id;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    // Phương thức toString() để hiển thị thông tin Student
    @Override
    public String toString() {
        return "Student{id=" + id + ", name='" + name + "'}";
    }
}

public class Example {
    public static void main(String[] args) {
        // Tạo một LinkedHashMap với ID là khóa và Student là giá trị
        LinkedHashMap<Integer, Student> studentMap = new LinkedHashMap<>();

        // Thêm các đối tượng Student vào LinkedHashMap
        studentMap.put(1, new Student(1, "A"));
        studentMap.put(2, new Student(2, "B"));
        studentMap.put(3, new Student(3, "C"));

        // Hiển thị các phần tử trong LinkedHashMap
        System.out.println("Danh sách sinh viên:");
        for (Map.Entry<Integer, Student> entry : studentMap.entrySet()) {
            System.out.println("Khóa: " + entry.getKey() + ", Giá trị: " + entry.getValue());
        }

        // Cập nhật thông tin của sinh viên với ID 2
        studentMap.put(2, new Student(2, "R"));

        // Xóa sinh viên với ID 1
        studentMap.remove(1);

        // Hiển thị các phần tử trong LinkedHashMap sau khi thay đổi
        System.out.println("\nDanh sách sinh viên sau khi cập nhật và xóa:");
        for (Map.Entry<Integer, Student> entry : studentMap.entrySet()) {
            System.out.println("Khóa: " + entry.getKey() + ", Giá trị: " + entry.getValue());
        }
    }
}

Như vậy, chúng ta đã tìm hiểu các phương thức chính của lớp LinkedHashMap. Với khả năng duy trì thứ tự chèn (hoặc thứ tự truy cập) đồng thời vẫn cung cấp hiệu suất cao cho các thao tác thêm, xóa, lấy tương tự như HashMap, LinkedHashMap là lựa chọn lý tưởng khi bạn cần một bản đồ mà thứ tự của các phần tử là quan trọng. Việc hiểu rõ lợi ích của LinkedHashMap sẽ giúp bạn tối ưu hóa việc quản lý dữ liệu trong các tình huống đòi hỏi cả tốc độ và trật tự trong ứng dụng Java của mình.