Giới thiệu bộ sưu tập TreeMap

Một ngày nọ ở trường đại học, tôi cần viết mã để sắp xếp họ của các bạn cùng lớp, dùng làm khóa cho dữ liệu cá nhân của họ, theo thứ tự tăng dần. Tôi đã dành rất nhiều thời gian cho việc này. Nhưng nếu tôi biết về lớp TreeMap hồi đó, tôi sẽ hoàn thành nhiệm vụ nhanh hơn nhiều.

Sơ đồ cây là gì ? Nó là một cấu trúc dữ liệu giống như từ điển lưu trữ các phần tử dưới dạng cặp khóa-giá trị, sắp xếp chúng theo khóa.

Nó có thể được sử dụng ở đâu và như thế nào? Chà, nó sẽ là lý tưởng cho cùng một nhiệm vụ với họ của các bạn cùng lớp của tôi. Nếu tôi cần lưu trữ các giá trị theo thứ tự tăng dần, thay vì viết thuật toán sắp xếp của riêng mình, tất cả những gì tôi phải làm là tạo một Sơ đồ cây và đặt các giá trị vào đó.

Nó sắp xếp các loại như Số nguyên và Chuỗi theo thứ tự tăng dần. Nhưng nếu bạn muốn đặt loại tùy chỉnh của riêng mình trong TreeMap thì lớp của bạn cần triển khai giao diện Có thể so sánh để nó triển khai phương thức so sánhTo() , cho biết cách sắp xếp các thể hiện của lớp của bạn.

public class Person implements Comparable<Person> {
 
    private String firstName;
    private String lastName;
 
    public Person(String firstName, String lastName) {
        this.firstName = firstName;
        this.lastName = lastName;
    }
 
    public String getFirstName() {
        return firstName;
    }
 
    public void setFirstName(String firstName) {
        this.firstName = firstName;
    }
 
  …
 
    @Override
    public int compareTo(Person person) {
        return person.getFirstName().compareTo(firstName);
    }
 
    @Override
    public String toString() {
        return "Person{" +
                "firstName='" + firstName + '\'' +
                ", lastName='" + lastName + '\'' +
                '}';
    }
}

Hãy ghi đè phương thức compareTo() để nó sắp xếp các giá trị theo tên theo thứ tự bảng chữ cái đảo ngược:

TreeMap map = new TreeMap<Person, String>();
 
map.put(new Person("AA","BB"), "aa");
map.put(new Person("BB","BB"), "aa");
map.put(new Person("DD","BB"), "aa");
map.put(new Person("CC","BB"), "aa");

Các giá trị sẽ được lưu trữ theo thứ tự sau:

Person{firstName='DD', lastName='BB'}
Person{firstName='CC', lastName='BB'}
Person{firstName='BB', lastName='BB'}
Person{firstName='AA', lastName='BB'}

Lớp TreeMap triển khai giao diện NavigableMap , từ đó mở rộng giao diện SortedMap . Điều này cho phép lớp TreeMap sử dụng cây để lưu trữ các giá trị theo thứ tự đã sắp xếp.

Nói một cách đơn giản, cây đỏ đen là một cấu trúc dữ liệu lưu trữ các giá trị trong cây con bên phải nếu chúng lớn hơn gốc và trong cây con bên trái nếu chúng nhỏ hơn. Việc triển khai này có thể tra cứu các giá trị trong cấu trúc rất nhanh chóng.

Cây đỏ đen tự cân bằng, vì vậy nó thay đổi cấu trúc khi mỗi giá trị mới được chèn vào. Giá trị gia tăng đầu tiên ban đầu được coi là gốc, nhưng một giá trị khác có thể trở thành gốc trong quá trình cân bằng.

Chà, bây giờ bạn đã biết TreeMap là gì và nó hoạt động như thế nào.

Hãy nhớ rằng TreeMap chỉ có thể lưu trữ các đối tượng có lớp triển khai giao diện So sánh được và ghi đè phương thức so sánhTo() .

Nhưng nếu chúng ta đang sử dụng các lớp của bên thứ ba được tải từ nhiều thư viện khác nhau và không thể triển khai Comparable trong đó thì sao? Có một giải pháp cho việc này: viết Bộ so sánh của riêng bạn .

Bộ so sánh là một giao diện có phương thức so sánh(). Chúng ta có thể sử dụng nó để so sánh các đối tượng và lưu trữ chúng trong TreeMap .

Comparator<Person> comparator = new Comparator<Person>() {
 
    @Override
    public int compare(Person person1, Person person2) {
        return person1.getFirstName().compareTo(person2.getFirstName());
    }
};
 
 
TreeMap map = new TreeMap<Person, String>(comparator);

Trong ví dụ này, chúng tôi đã tạo một Bộ so sánh tùy chỉnh và chuyển một Sơ đồ cây cho lớp.

Bắt đầu từ Java 8, chúng ta có thể viết điều này bằng biểu thức lambda:

TreeMap map = new TreeMap<Person, String>((Person person1, Person person2) -> person1.getFirstName().compareTo(person2.getFirstName()));

Nói cách khác, để lưu trữ các giá trị trong TreeMap , bạn cần chỉ định cách sắp xếp chúng. Có hai cách để làm điều này: triển khai Comparable hoặc triển khai Comparator của riêng bạn .

Nhưng nếu chúng ta cần đặt null vào TreeMap làm khóa thì sao? HashMap cho phép bạn làm điều này. Có, nhưng TreeMap xử lý việc này như thế nào?

TreeMap map = new TreeMap<Person, String>();
map.put (null, "Person");

Chạy mã này cho chúng tôi một lỗi:

Vấn đề là bên trong lớp TreeMap so sánh các giá trị bằng cách sử dụng phương thức compareTo() . Bạn chắc chắn có thể chuyển một giá trị null vào và mã sẽ biên dịch. Nhưng trong thời gian chạy, bạn sẽ gặp lỗi vì phương thức này sẽ được gọi trên một giá trị null , khiến cho một NullPulumException bị ném ra.

So sánh HashMap và TreeMap

Không giống như TreeMap , HashMap cho phép bạn lưu trữ null dưới dạng khóa. Cấu trúc có một vị trí cụ thể cho tất cả các khóa null . HashMap có thể lưu trữ các khóa null vì nó xác định vị trí của chúng dựa trên giá trị băm của chúng và việc tính toán giá trị băm không yêu cầu so sánh. Vì vậy, tất cả các khóa null đều có vị trí của chúng.

Vậy là bạn đã có nó — bây giờ bạn biết cách sử dụng khi cần lưu trữ các giá trị theo thứ tự đã sắp xếp và cách đặt quy tắc sắp xếp.