Hướng dẫn và ví dụ Java TreeMap

TreeMap
TreeMap lưu trữ dữ liệu như thế nào?
Examples
TreeMap với khoá null

1. TreeMap

Trong bài viết này chúng ta sẽ khám phá về lớp TreeMap, nó là một triển khai (implementation) của interaface Map và nằm trong nền tảng tập hợp của Java (Java Collection Framework).

public class TreeMap<K,V> extends AbstractMap<K,V>
                    implements NavigableMap<K,V>, Cloneable, java.io.Serializable

Về cơ bản, trong bài viết này chúng ta sẽ tìm hiểu các đặc điểm của TreeMap và cách nó lưu trữ các ánh xạ. Các khái niệm cơ bản về Map sẽ không được đề cập lại, nếu chưa có khái niệm về Map, bạn nên tìm hiểu nó trước khi khi tiếp tục với bài viết này.

Map<K,V>	SortedMap<K,V> NavigableMap<K,V>	TreeMap<K,V>
Không cho phép trùng lặp khoá.
Có thể cho phép khoá null và các giá trị null.		Chỉ cho phép khoá null nếu được cung cấp một Comparator phù hợp.
Thứ tự của các khoá không được đảm bảo.	Các khoá được xắp xếp theo thứ tự tăng dần dựa trên thứ tự tự nhiên của chúng hoặc theo một Comparator được cung cấp.

Thừa hưởng các đặc điểm của interface SortedMap. Tất cả các khoá của TreeMapphải là kiểu Comparable (có thể so sánh) hoặc bạn phải cung cấp một Comparator (bộ so sánh) cho TreeMap để nó so sánh các khoá với nhau. Ngược lại, ClassCastException sẽ bị ném ra. Comparator được cung cấp tại thời điểm tạo đối tượng TreeMap thông qua một trong các constructor của nó.

TreeMap constructors

TreeMap()

TreeMap(Map<? extends K,? extends V> m)    

TreeMap(Comparator<? super K> comparator)

// Using the same ordering as the specified sortedMap.
TreeMap(SortedMap<K,? extends V> m)

HashMap
IdentityHashMap
WeakHashMap
LinkedHashMap
EnumMap
ConcurrentHashMap
ConcurrentSkipListMap
Map
ConcurrentMap
ConcurrentNavigableMap
SortedMap
NavigableMap

2. TreeMap lưu trữ dữ liệu như thế nào?

TreeMap sử dụng comparator.compare(key1,key2) để so sánh 2 khoá nếu Comparator được cung cấp, ngược lại nó sử dụng key1.compareTo(key2) để so sánh 2 khoá. TreeMap được thiết kế để đảm bảo rằng các hoạt động tìm kiếm, cập nhập hoặc xoá một ánh xạ sẽ tốn ít thời gian nhất có thể bằng cách giảm số lần phải so sánh các khoá với nhau. Trong phần này chúng ta sẽ tìm hiểu về cách TreeMap lưu trữ dữ liệu của nó.

Entry<K,V> là một lớp được sử dụng để lưu trữ một ánh xạ, nó bao gồm 5 property: key, value, parent, left, right. TreeMap quản lý một tham chiếu tới một Entry gốc - root, các hoạt động tìm kiếm trên TreeMap sẽ bắt đầu từ Entry gốc và lan toả tới một lá của cây.

Entry<K,V>

K key;
V value;
Entry<K,V> left;
Entry<K,V> right;
Entry<K,V> parent;

Để đơn giản hãy xem điều gì sẽ xẩy ra khi chúng ta thêm các ánh xạ vào một TreeMap<Integer,String>.

TreeMap<Integer, String> map = new TreeMap<>();

// keys = 5, 3, 9, 7, 1, 11.
map.put(5, "Five");
map.put(3,  "Three");
map.put(9,  "Nine");
map.put(7, "Seven");
map.put(1, "One");
map.put(11, "Eleven");

Hình ảnh trên cho thấy cấu trúc cây của TreeMap. Ánh xạ đầu tiên được thêm vào TreeMap sẽ là gốc (root) của cây, ánh xạ với khoá nhỏ hơn sẽ được đặt bên trái, và ánh xạ với khoá lớn hơn sẽ được đặt bên phải.

get(key)?

map.get(7); // key =  7

Hoạt động tìm kiếm một ánh xạ luôn bắt đầu từ Entry gốc của cây. Khoá cần tìm kiếm sẽ được so sánh với khoá của Entry hiện tại, nếu lớn hơn nó sẽ được so sánh với khoá của Entry tiếp theo bên phải, ngược lại nếu nhỏ hơn nó sẽ được so sánh với khoá của Entry tiếp theo bên trái cho tới khi tìm thấy hoặc đã tiến tới lá của cây.

remove(key)?

Tiếp theo, hãy xem TreeMap làm gì để loại bỏ một ánh xạ.

map.remove(5); // Remove the mapping has key = 5.

Để loại bỏ một ánh xạ, TreeMap xác định vị trí của Entry cần loại bỏ. Sau đó nó tìm kiếm Entry với khoá nhỏ nhất và lớn hơn khoá cần loại bỏ để thay thế vào vị trí của Entry cần loại bỏ.

put(key,value)?

map.put(2, "Two");

3. Examples

Như chúng ta đã biết, lớp Integer thi hành interface Comparable, nên các đối tượng Integer có khả năng so sánh được với nhau. TreeMap với các khoá kiểu Integer không cần thiết phải cung cấp một Comparator.

TreeMapEx1.java

package org.o7planning.treemap.ex;

import java.util.Set;
import java.util.TreeMap;

public class TreeMapEx1 {

    public static void main(String[] args) {
        TreeMap<Integer, String> map = new TreeMap<>();
        //  
        map.put(5, "Five");
        map.put(3, "Three");
        map.put(9, "Nine");
        map.put(7, "Seven");
        map.put(1, "One");
        map.put(11, "Eleven");
        
        Set<Integer> keys = map.keySet();
        
        System.out.println(keys);
        
        for(Integer key: keys)  {
            System.out.println(key + " --> " + map.get(key));
        }
    }
}

Output:

[1, 3, 5, 7, 9, 11]
1 --> One
3 --> Three
5 --> Five
7 --> Seven
9 --> Nine
11 --> Eleven

Ví dụ: Sử dụng Comparator tuỳ biến để đảo ngược thứ tự các khoá.

TreeMap_reverseOrder_ex1.java

package org.o7planning.treemap.ex;

import java.util.Comparator;
import java.util.Set;
import java.util.TreeMap;

public class TreeMap_reverseOrder_ex1 {

    public static void main(String[] args) {
        Comparator<Integer> reverseOrderComparator = Comparator.reverseOrder();
        
        TreeMap<Integer, String> map = new TreeMap<>(reverseOrderComparator);
        //  
        map.put(5, "Five");
        map.put(3, "Three");
        map.put(9, "Nine");
        map.put(7, "Seven");
        map.put(1, "One");
        map.put(11, "Eleven");
        
        Set<Integer> keys = map.keySet();
        
        System.out.println(keys);
        
        for(Integer key: keys)  {
            System.out.println(key + " --> " + map.get(key));
        }
    }
}

Output:

[11, 9, 7, 5, 3, 1]
11 --> Eleven
9 --> Nine
7 --> Seven
5 --> Five
3 --> Three
1 --> One

Xem thêm các ví dụ khác về việc sử dụng Comparator tuỳ biến và cách điều hướng tìm kiếm khoá hoặc ánh xạ:

4. TreeMap với khoá null

TreeMap chỉ cho phép khoá null nếu nó được cung cấp một Comparator hỗ trợ việc so sánh khoá null với các khoá khác.

TreeMap_nullKey_ex1.java

package org.o7planning.treemap.ex;

import java.util.Comparator;
import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;

public class TreeMap_nullKey_ex1 {

    public static void main(String[] args) {
        // Comparator.nullsFirst
        // Comparator.nullsLast
        Comparator<String> comparator = Comparator.nullsFirst(Comparator.naturalOrder());

         // Create a SortedSet object.
        SortedMap<String, Integer> map = new TreeMap<String, Integer>(comparator);
 
        map.put(null, 0);
        map.put("B", 100);
        map.put("A", 200);
        map.put("F", 400);
        map.put("D", 500);
        map.put("E", 100);

        System.out.println("--- keySet ---");
        Set<String> keys = map.keySet();

        for (String key : keys) {
            System.out.println(key + " --> " + map.get(key));
        }
        
        System.out.println("--- entrySet ---");
        Set<Map.Entry<String,Integer>> entrySet = map.entrySet();
        
        for (Map.Entry<String,Integer> entry: entrySet) {
            System.out.println(entry.getKey() + " --> " + entry.getValue());
        }
    }
}

Output:

--- keySet ---
null --> 0
A --> 200
B --> 100
D --> 500
E --> 100
F --> 400
--- entrySet ---
null --> 0
A --> 200
B --> 100
D --> 500
E --> 100
F --> 400

Ví dụ: Viết một Comparator tuỳ biến hỗ trợ việc so sánh khoá null với các khoá khác:

TreeMap_nullKey_ex2.java

package org.o7planning.treemap.ex;

import java.util.Comparator;
import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;

public class TreeMap_nullKey_ex2 {

    public static void main(String[] args) {  
        Comparator<String> comparator = new StringNullComparator();

         // Create a SortedSet object.
        SortedMap<String, Integer> map = new TreeMap<String, Integer>(comparator);
 
        map.put(null, 0);
        map.put("B", 100);
        map.put("A", 200);
        map.put("F", 400);
        map.put("D", 500);
        map.put("E", 100);

        System.out.println("--- keySet ---");
        Set<String> keys = map.keySet();

        for (String key : keys) {
            System.out.println(key + " --> " + map.get(key));
        }
        
        System.out.println("--- entrySet ---");
        Set<Map.Entry<String,Integer>> entrySet = map.entrySet();
        
        for (Map.Entry<String,Integer> entry: entrySet) {
            System.out.println(entry.getKey() + " --> " + entry.getValue());
        }
    }
}
// The comparator supports null comparison.
class StringNullComparator implements Comparator<String> {

    @Override
    public int compare(String o1, String o2) {
        if(o1 == o2) {
            return 0; // o1 = o2
        }
        if(o1 == null)  {
            return -1; // o1 < o2
        }
        if(o2 == null)  {
            return 1; // o1 > o2
        }
        return o1.compareTo(o2);
    }
}

Output:

--- keySet ---
null --> 0
A --> 200
B --> 100
D --> 500
E --> 100
F --> 400
--- entrySet ---
null --> 0
A --> 200
B --> 100
D --> 500
E --> 100
F --> 400

Hướng dẫn và ví dụ Java TreeMap

1. TreeMap

2. TreeMap lưu trữ dữ liệu như thế nào?

3. Examples

4. TreeMap với khoá null

Các hướng dẫn Java Collections Framework

Các hướng dẫn Java Collections Framework

Các bài viết mới nhất