Các tính năng của TreeMap trong Java

Nếu bạn đang đọc bài viết này thì rất có thể bạn đã quen với giao diện Bản đồ và cách sử dụng nó. Nếu không thì bạn đi đây. Hôm nay chúng ta sẽ nói về các tính năng triển khai của TreeMap và cụ thể hơn là nó khác với HashMap như thế nào và cách sử dụng nó một cách chính xác.

So sánh TreeMap, HashMap và LinkedHashMap

Việc triển khai giao diện Map được sử dụng phổ biến nhất là HashMap . Nó dễ sử dụng và đảm bảo khả năng truy cập dữ liệu nhanh chóng, khiến nó trở thành ứng cử viên tốt nhất cho hầu hết các tác vụ. Hầu hết, nhưng không phải tất cả. Đôi khi cần lưu trữ dữ liệu ở dạng có cấu trúc với khả năng điều hướng qua nó. Trong trường hợp này, một triển khai khác của giao diện Map sẽ được giải cứu - TreeMap . TreeMap triển khai giao diện NavigableMap , kế thừa từ SortedMap , sau đó kế thừa từ giao diện Map . Bằng cách triển khai các giao diện NavigableMap và SortedMap , TreeMap có được chức năng bổ sung mà HashMap không có , nhưng điều này phải trả giá về mặt hiệu suất. Ngoài ra còn có lớp LinkedHashMap , lớp này cũng cho phép bạn lưu trữ dữ liệu theo một thứ tự nhất định - theo thứ tự chúng được thêm vào. Để giúp bạn hiểu sự khác biệt giữa ba lớp này, hãy xem bảng này: Như bạn có thể thấy, các lớp này có nhiều điểm chung nhưng cũng có một số điểm khác biệt. Mặc dù lớp này TreeMaplà lớp đa chức năng nhất nhưng không phải lúc nào nó cũng được lưu trữ nulldưới dạng khóa. Ngoài ra, thời gian truy cập vào các phần tử TreeMap sẽ lâu nhất. Vì vậy, nếu không có nhu cầu lưu trữ dữ liệu ở dạng đã sắp xếp thì nên sử dụng HashMapor LinkedHashMap.

Cây mun đỏ

Như bạn có thể nhận thấy, bên dưới TreeMapnó sử dụng cấu trúc dữ liệu được gọi là cây đỏ đen. Việc lưu trữ dữ liệu trong cấu trúc này đảm bảo thứ tự lưu trữ dữ liệu. Cây này là gì? Hãy tìm ra nó! Hãy tưởng tượng rằng bạn cần lưu trữ các cặp Chuỗi Số. Các số 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93, 101 sẽ là chìa khóa. Nếu bạn lưu trữ dữ liệu trong danh sách truyền thống và cần tìm một phần tử có khóa 101, bạn sẽ cần phải lặp qua tất cả 13 phần tử để tìm thấy nó. Đối với 13 yếu tố, điều này không quan trọng; khi làm việc với một triệu yếu tố, chúng ta sẽ gặp rắc rối lớn. Để giải quyết những vấn đề như vậy, các lập trình viên sử dụng cấu trúc dữ liệu phức tạp hơn một chút. Vì vậy, hãy gặp cây đỏ đen!

https://algorithmtutor.com/Data-Structures/Tree/Red-Black-Trees/

Việc tìm kiếm phần tử bắt buộc bắt đầu từ gốc của cây, trong trường hợp của chúng tôi là 61. Tiếp theo, một so sánh được thực hiện với giá trị được yêu cầu. Nếu giá trị của chúng tôi nhỏ hơn thì chúng tôi chuyển sang bên trái, nếu giá trị lớn hơn thì chúng tôi chuyển sang bên phải. Điều này xảy ra cho đến khi chúng ta tìm thấy giá trị cần thiết hoặc gặp một phần tử có giá trị null(một chiếc lá của cây). Màu đỏ và đen được sử dụng để giúp cây dễ di chuyển và giữ thăng bằng hơn. Có những quy tắc phải luôn được tuân theo khi xây dựng cây đỏ đen:

• Rễ nên có màu đen.
• Lá của cây phải có màu đen.
• Một nút màu đỏ phải có hai nút con màu đen.
• Một nút đen có thể có bất kỳ nút con nào.
• Đường đi từ một nút đến các lá của nó phải chứa cùng số nút đen.
• Các nút mới được thêm vào thay cho các lá.

Nếu bạn xem xét các quy tắc 3, 4 và 5 cùng nhau, bạn có thể hiểu các nút tô màu tăng tốc độ điều hướng trong cây như thế nào: đường đi qua các nút màu đen luôn ngắn hơn so với các nút màu đỏ. Do đó, tổng kích thước của cây được xác định bởi số lượng nút đen và kích thước này được gọi là “chiều cao đen”. Cây đỏ đen được triển khai bằng các ngôn ngữ lập trình khác nhau. Có rất nhiều cách triển khai Java trên Internet, vì vậy chúng ta sẽ không nghiên cứu nó lâu mà sẽ tiếp tục làm quen với chức năng này TreeMap.

Các phương thức bắt nguồn từ giao diện SortedMap và NavigableMap

Giống như HashMap, TreeMapnó thực hiện giao diện Map, có nghĩa là nó TreeMapcó tất cả các phương thức HashMap. Nhưng ngoài ra, TreeMapnó còn triển khai các giao diện SortedMapvà NavigableMapthu được các chức năng bổ sung từ chúng. SortedMap- giao diện mở rộng Mapvà thêm các phương thức liên quan đến tập dữ liệu được sắp xếp:

• firstKey(): trả về khóa của phần tử đầu tiên của bản đồ;
• lastKey(): trả về khóa của phần tử cuối cùng;
• headMap(K end): trả về một bản đồ chứa tất cả các phần tử của bản đồ hiện tại, từ đầu đến phần tử có khóa end;
• tailMap(K start): trả về một bản đồ chứa tất cả các phần tử của phần tử hiện tại, bắt đầu bằng phần tử startvà kết thúc bằng phần tử cuối;
• subMap(K start, K end): trả về một bản đồ chứa tất cả các phần tử của phần tử hiện tại, bắt đầu bằng phần tử startvà kết thúc bằng phần tử có khóa end.

NavigableMap- một giao diện mở rộng SortedMapvà thêm các phương thức điều hướng giữa các thành phần bản đồ:

• firstEntry(): trả về cặp khóa-giá trị đầu tiên;
• lastEntry(): trả về cặp khóa-giá trị cuối cùng;
• pollFirstEntry(): trả về và loại bỏ cặp đầu tiên;
• pollLastEntry(): trả về và xóa cặp cuối cùng;
• ceilingKey(K obj): Trả về khóa k nhỏ nhất lớn hơn hoặc bằng khóa obj. Nếu không có khóa đó, trả về null;
• floorKey(K obj): Trả về khóa k lớn nhất nhỏ hơn hoặc bằng khóa obj. Nếu không có khóa đó, trả về null;
• lowerKey(K obj): Trả về khóa k lớn nhất nhỏ hơn khóa obj. Nếu không có khóa đó, trả về null;
• higherKey(K obj): Trả về khóa k nhỏ nhất lớn hơn khóa obj. Nếu không có khóa đó, trả về null;
• ceilingEntry(K obj): tương tự như phương thức deskKey(K obj), nhưng trả về một cặp khóa-giá trị (hoặc null);
• floorEntry(K obj): tương tự như phương thức FloorKey(K obj) nhưng trả về một cặp khóa-giá trị (hoặc null);
• lowerEntry(K obj): tương tự như phương thức lowKey(K obj), nhưng trả về một cặp khóa-giá trị (hoặc null);
• higherEntry(K obj): tương tự như phương thức HigherKey(K obj) nhưng trả về một cặp khóa-giá trị (hoặc null);
• descendingKeySet(): trả về một NavigableSet chứa tất cả các khóa được sắp xếp theo thứ tự ngược lại;
• descendingMap(): trả về một NavigableMap chứa tất cả các cặp được sắp xếp theo thứ tự ngược lại;
• navigableKeySet(): trả về một đối tượng NavigableSet chứa tất cả các khóa theo thứ tự lưu trữ;
• headMap(K upperBound, boolean incl): trả về bản đồ chứa các cặp từ đầu đến phần tử UpperBound. Đối số incl chỉ định xem phần tử UpperBound có nên được đưa vào bản đồ được trả về hay không;
• tailMap(K lowerBound, boolean incl): chức năng tương tự như phương thức trước, chỉ trả về các cặp từ lowBound đến cuối;
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl): Như trong các phương thức trước, các cặp từ lowBound đến UpperBound được trả về, các đối số lowIncl và highIncl chỉ định xem có bao gồm các phần tử ranh giới trong bản đồ mới hay không.

Trong bản thân quá trình triển khai TreeMap, ngoài các hàm tạo mà chúng ta quen thuộc, một hàm tạo khác được thêm vào, chấp nhận một thể hiện của bộ so sánh. Bộ so sánh này sẽ chịu trách nhiệm về thứ tự lưu trữ các phần tử.

Ví dụ về việc sử dụng TreeMap

Sự phong phú của các phương pháp bổ sung như vậy có vẻ không cần thiết, nhưng chúng thường hữu ích hơn nhiều so với ban đầu. Hãy cùng bạn xem ví dụ này. Hãy tưởng tượng rằng chúng ta làm việc trong bộ phận tiếp thị của một công ty lớn và chúng ta có cơ sở dữ liệu về những người mà chúng ta muốn hiển thị quảng cáo. Có hai sắc thái cho điều này:

• chúng ta cần theo dõi số lần hiển thị đối với mỗi người;
• Thuật toán hiển thị quảng cáo cho trẻ vị thành niên là khác nhau.

Hãy tạo một lớp Personsẽ lưu trữ tất cả thông tin có sẵn về một người:

public class Person {
   public String firstName;
   public String lastName;
   public int age;

   public Person(String firstName, String lastName, int age) {
       this.firstName = firstName;
       this.lastName = lastName;
       this.age = age;
   }
}

Chúng tôi thực hiện logic trong lớp Main:

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

public class Main {
   public static void main(String[] args) {
      TreeMap<Person, Integer> map = new TreeMap<>(Comparator.comparingInt(o -> o.age));
      map.put(new Person("John", "Smith", 17), 0);
      map.put(new Person("Ivan", "Petrenko", 65), 0);
      map.put(new Person("Pedro", "Escobar", 32), 0);
      map.put(new Person("Radion", "Pyatkin", 14), 0);
      map.put(new Person("Sergey", "Vashkevich", 19), 0);

      Person firstAdultPerson = map.navigableKeySet().stream().filter(person -> person.age>18).findFirst().get();

       Map<Person, Integer> youngPeopleMap = map.headMap(firstAdultPerson, false);
       Map<Person, Integer> adultPeopleMap = map.tailMap(firstAdultPerson, true);
       showAdvertisementToYoung(youngPeopleMap);
       showAdvertisementToAdult(adultPeopleMap);
   }

   public static void showAdvertisementToYoung(Map map){}
   public static void showAdvertisementToAdult(Map map){}
}

Trong lớp Mainchúng tôi tạo TreeMap, keymột người cụ thể ở đâu và valuesố lần hiển thị quảng cáo trong tháng này. Trong hàm tạo, chúng ta chuyển một bộ so sánh sẽ sắp xếp mọi người theo độ tuổi. Điền vào mapcác giá trị ngẫu nhiên. Bây giờ chúng ta cần tham chiếu đến người lớn đầu tiên trong kho dữ liệu nhỏ của chúng ta. Chúng tôi thực hiện việc này bằng API luồng. Sau này, chúng tôi nhận được hai bản đồ độc lập mà chúng tôi chuyển cho các phương thức hiển thị quảng cáo. Có rất nhiều cách để giải quyết vấn đề này. Kho phương pháp của lớp TreeMapcho phép bạn phát minh ra các giải pháp phù hợp với mọi sở thích. Không cần thiết phải nhớ tất cả vì bạn luôn có thể sử dụng tài liệu hoặc gợi ý từ môi trường phát triển. Đó là tất cả! Tôi hy vọng giờ đây bạn đã hiểu rõ bài học này TreeMapvà bạn sẽ tìm thấy ứng dụng chính xác của nó trong việc giải quyết các vấn đề thực tế.