TreeMap trong Java (Java TreeMap)

1. TreeMap là gì?

TreeMap trong Java là một cấu trúc dữ liệu thuộc loại Map, TreeMap lưu trữ các cặp khóa-giá trị và tự động sắp xếp các phần tử theo thứ tự của khóa. TreeMap dựa trên cấu trúc của cây nhị phân cân bằng (cụ thể là cây Red-Black Tree) giúp dữ liệu luôn được duy trì theo một thứ tự nhất định, chẳng hạn như thứ tự tự nhiên của khóa hoặc theo thứ tự xác định bởi một Comparator tùy chỉnh.

2. Đặc điểm của TreeMap

• Sắp xếp theo khóa: Mỗi phần tử trong TreeMap được sắp xếp tự động theo khóa. Điều này khác biệt với HashMap, nơi các phần tử không có thứ tự nhất định.
• Không cho phép khóa null: TreeMap không hỗ trợ giá trị null cho khóa nhưng các giá trị (value) vẫn có thể là null.
• Hiệu suất: Các thao tác như thêm, xóa, tìm kiếm trong TreeMap có độ phức tạp trung bình là O(log(n)) nhờ cấu trúc của cây Red-Black.
• Các phương thức bổ sung:
  • firstKey(), lastKey(): Lấy khóa nhỏ nhất và lớn nhất trong TreeMap.
  • headMap(toKey), tailMap(fromKey), subMap(fromKey, toKey): Trả về một phần của TreeMap theo khoảng khóa được chỉ định.

– Ví dụ:

import java.util.TreeMap;

public class App {
    public static void main(String[] args) {
        TreeMap<String, Integer> treeMap = new TreeMap<>();

        treeMap.put("Cam", 5);
        treeMap.put("Quýt", 10);
        treeMap.put("Mít", 15);
        treeMap.put("Dừa", 20);

        System.out.println("TreeMap: " + treeMap);
        System.out.println("First key: " + treeMap.firstKey());
        System.out.println("Last key: " + treeMap.lastKey());
        System.out.println("SubMap (Apple to Orange): " + treeMap.subMap("Apple", "Orange"));
    }
}

– kết quả:
TreeMap: {Cam=5, Dừa=20, Mít=15, Quýt=10}
First key: Cam
Last key: Quýt
SubMap (Mít -> Quýt): {Mít=15}

3. Sử dụng

TreeMap thích hợp khi bạn cần lưu trữ các cặp khóa-giá trị theo thứ tự và có thể trích xuất các phần tử theo khoảng khóa xác định.

4. Câu hỏi phỏng vấn Java TreeMap

1. TreeMap là gì và có đặc điểm gì nổi bật?

Trả lời:

TreeMap là một cấu trúc dữ liệu thuộc loại Map trong Java, lưu trữ các cặp khóa-giá trị theo thứ tự sắp xếp của khóa. TreeMap dựa trên cấu trúc cây nhị phân cân bằng (cụ thể là Red-Black Tree), đảm bảo rằng các phần tử luôn được duy trì theo thứ tự tự nhiên hoặc theo một Comparator tùy chỉnh. TreeMap có độ phức tạp thời gian trung bình cho các thao tác thêm, xóa và tìm kiếm là O(log(n)).

2. TreeMap khác gì với HashMap và LinkedHashMap?

Trả lời:

TreeMap lưu trữ các phần tử theo thứ tự của khóa, trong khi HashMap không duy trì thứ tự và LinkedHashMap duy trì thứ tự thêm vào. TreeMap không cho phép null làm khóa, còn HashMap và LinkedHashMap đều cho phép.

3. TreeMap sử dụng cấu trúc dữ liệu gì bên trong?

Trả lời:

TreeMap sử dụng cấu trúc cây Red-Black Tree, một dạng cây nhị phân cân bằng tự động, để lưu trữ các phần tử theo thứ tự sắp xếp của khóa và đạt hiệu suất logarit O(log(n)) cho các thao tác cơ bản.

4. TreeMap có cho phép khóa hoặc giá trị null không?

Trả lời:

TreeMap không cho phép null làm khóa vì cần sắp xếp các khóa, tuy nhiên nó cho phép giá trị null.

5. Làm cách nào để sắp xếp TreeMap theo thứ tự giảm dần của khóa?

Trả lời:

Có thể sắp xếp TreeMap theo thứ tự giảm dần của khóa bằng cách sử dụng Comparator.reverseOrder() trong constructor của TreeMap như sau:

TreeMap<Integer, String> treeMap = new TreeMap<>(Comparator.reverseOrder());

6. Cách tạo một TreeMap từ một Map có sẵn để duy trì thứ tự sắp xếp của TreeMap?

Trả lời:

Có thể tạo một TreeMap từ một Map có sẵn (ví dụ như HashMap hoặc LinkedHashMap) bằng cách sử dụng constructor của TreeMap như sau:

Map<Integer, String> map = new HashMap<>();
// Thêm phần tử vào map
TreeMap<Integer, String> treeMap = new TreeMap<>(map);

7. Sử dụng TreeMap khi nào là phù hợp nhất?

Trả lời:

TreeMap phù hợp khi cần lưu trữ các cặp khóa-giá trị theo thứ tự và thực hiện các thao tác tìm kiếm, lấy phần tử theo khoảng hoặc khi cần lấy khóa nhỏ nhất hoặc lớn nhất.

8. Các phương thức phổ biến của TreeMap là gì?

Trả lời: Một số phương thức phổ biến của TreeMap bao gồm:

• firstKey() và lastKey(): Lấy khóa đầu tiên và cuối cùng.
• headMap(toKey), tailMap(fromKey), và subMap(fromKey, toKey): Lấy các phần tử theo khoảng khóa nhất định.
• ceilingKey(key), floorKey(key), higherKey(key), lowerKey(key): Tìm khóa gần nhất lớn hơn, nhỏ hơn hoặc bằng key.

9. Làm thế nào để tạo một TreeMap với một Comparator tùy chỉnh?

Trả lời:

Có thể tạo TreeMap với Comparator tùy chỉnh bằng cách truyền Comparator vào constructor của TreeMap:

TreeMap<String, Integer> treeMap = new TreeMap<>(Comparator.comparing(String::length));

10. TreeMap có thread-safe không? Cách làm cho TreeMap an toàn trong môi trường đa luồng?

Trả lời:

TreeMap không thread-safe. Để sử dụng TreeMap trong môi trường đa luồng, có thể đồng bộ hóa TreeMap bằng cách dùng Collections.synchronizedSortedMap(new TreeMap<>()).