Sắp xếpBản đồ

Bản đồ được sắp xếp

Trong bài học này, chúng ta sẽ nghiên cứu về giao diện SortedMap . Chúng ta sẽ khám phá các phương pháp mới xuất hiện trong giao diện này, cũng như các tính năng của một triển khai SortedMap — TreeMap — và sự khác biệt giữa các triển khai, cũng như ưu điểm của chúng so với HashMap .

Hãy xem hệ thống phân cấp của bản đồ trông như thế nào. Đặc biệt chú ý đến giao diện SortedMap và triển khai TreeMap của nó — chúng là trọng tâm của chúng ta ngày hôm nay:

Giao diện SortedMap mở rộng giao diện Bản đồ . Theo nhiều cách, nó tương tự như SortedSet (do đó mở rộng Set ), vì cả hai đều mô tả chức năng tương tự để lưu trữ và sử dụng các giá trị được sắp xếp.

SortedSet hoạt động với và lưu trữ<TValue>, nhưng SortedMap lưu trữ<TKey, TValue>. Đó là một bản đồ lưu trữ tất cả các phần tử của nó theo thứ tự tăng dần của các khóa.

Giao diện SortedMap mở rộng Map . Nó thêm các phương pháp sau:

lớp TreeMap

Lớp TreeMap là một triển khai của giao diện SortedMap . Nghĩa là, TreeMap thực hiện tất cả các phương thức được SortedMap thêm vào cũng như các phương thức tiêu chuẩn từ giao diện Bản đồ .

Bạn có thể tạo một đối tượng TreeMap bằng cách sử dụng các hàm tạo như sau:

• TreeMap() : tạo một bản đồ trống được triển khai dưới dạng cây;

• TreeMap(Map<? extends TKey, ? extends TValue> map) : tạo một cây và thêm tất cả các thành phần từ bản đồ đầu vào;

• TreeMap(SortedMap<TKey, ? extends TValue> smap) : tạo một cây và thêm tất cả các phần tử từ bản đồ được sắp xếp đầu vào;

• TreeMap(Comparator<? super TKey> comparator) : tạo một cây trống — bộ so sánh sẽ được sử dụng để sắp xếp tất cả các phần tử khi chúng được thêm vào sau đó.

Ở đây TKey là loại khóa trong các cặp được lưu trữ và TValue là loại giá trị trong các cặp được lưu trữ trong TreeMap .

Bộ so sánh khá quan trọng đối với SortedMap / TreeMap . Nó thiết lập các quy tắc để sắp xếp — hoặc sắp xếp — bản đồ của chúng tôi. Nếu chúng tôi không cung cấp bộ so sánh, thì thứ tự tự nhiên của các khóa sẽ được sử dụng khi chúng tôi tạo SortedMap .

Thêm phần tử vào TreeMap

Các phần tử được thêm vào bản đồ dưới dạng các cặp bằng cách sử dụng phương thức put() . Khóa được truyền dưới dạng đối số đầu tiên và giá trị được truyền dưới dạng đối số thứ hai. Ví dụ: giả sử chúng ta muốn tạo danh sách sinh viên và điểm của họ.

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

map.put("Anthony", 5);
map.put("Sara", 5);
map.put("Roxy", 5);
map.put("Jeff", 4);
map.put("Nick", 4);
map.put("Oliver", 3);
map.put("Oliver", 5);

System.out.println(map);

Kết quả:

Khi chúng tôi thêm một cặp khóa-giá trị, nếu khóa đã tồn tại trong bộ sưu tập thì giá trị cũ sẽ được thay thế bằng giá trị mới. Hành vi này được minh họa trong ví dụ của chúng tôi với hai cặp có cùng khóa — ("Oliver", 3) và ("Oliver", 5) .

Hãy xem một ví dụ với Bộ so sánh mà chúng ta tạo. Giả sử chúng ta muốn lưu trữ các phần tử được sắp xếp theo độ dài của chuỗi khóa. Nếu độ dài của các khóa bằng nhau, thì chúng ta sẽ sắp xếp theo thứ tự bảng chữ cái (thứ tự tự nhiên của chuỗi):

class LengthComparator implements Comparator<String> {
  public int compare(String o1, String o2) {
    Integer lenghComparedResult = Integer.compare(o1.length(), o2.length());
    return lenghComparedResult != 0 ? lenghComparedResult : o1.compareTo(o2);
  }
}

SortedMap<String, Integer> lengthComparedMap = new TreeMap<String, Integer>(new LengthComparator());

lengthComparedMap.put("Jeff", 4);
lengthComparedMap.put("Oliver", 5);
lengthComparedMap.put("Roxy", 4);
lengthComaredMap.put("Jan", 4);

Đây là chuỗi kết quả:

Hành vi này làm cho Sơ đồ cây giống như một mảng hoặc danh sách được sắp xếp có chỉ số là từ ( Chuỗi ) thay vì số.

Các phương thức SortedMap trong lớp TreeMap

1. Nếu bạn cần lấy key của sinh viên đầu tiên, bạn có thể sử dụng phương thức firstKey() :

   
   String firstKey = map.firstKey();
   	System.out.println("First key → " + firstKey);
   

   Kết quả: Phím đầu tiên → Anthony

2. Nếu bạn cần lấy key của sinh viên cuối cùng, bạn có thể sử dụng phương thức lastKey() :

   
   String lastKey = map.lastKey();
   System.out.println("Last key → " + lastKey);
   

   Kết quả: Chìa khóa cuối cùng → Jeff

3. Nhận tất cả các đối tượng theo sau đối tượng bằng khóa " Sara ":

   
   Map<String, Integer> tailMap = map.tailMap("Sara");
            	System.out.println("tailMap: " + tailMap);
   

   Kết quả: tailMap: {Sara=5, Jeff=4}

4. Nhận tất cả các đối tượng đứng trước đối tượng bằng khóa " Nick ":

   
   System.out.println("headMap: " + headMap);
    Map<String, Integer> headMap = map.headMap("Nick");
   

   Kết quả: headMap: {Anthony=5}

5. Lấy tất cả các đối tượng đến sau đối tượng có khóa " Oliver " và đến trước đối tượng có khóa " Sara ":

   
   Map<String, Integer> subMap = map.subMap("Oliver", "Sara");	
   System.out.println("subMap: " + subMap);
   

   Kết quả: Bản đồ con: {Oliver=5, Roxy=5}

So sánh HashMap và SortedMap/TreeMap

Hãy nói về cách các phần tử được sắp xếp và lưu trữ:

• Vì HashMap không đảm bảo cho chúng ta về thứ tự khi lặp, nên thứ tự có thể thay đổi hoàn toàn khi các phần tử mới được thêm vào.

• Trong TreeMap , thứ tự dựa trên "thứ tự tự nhiên" của các khóa theo phương thức compareTo() của chúng (hoặc Bộ so sánh mà chúng tôi cung cấp). Ngoài ra, đừng quên rằng TreeMap triển khai giao diện SortedMap , giao diện này chứa các phương thức phụ thuộc vào thứ tự sắp xếp này.

Bây giờ chúng ta chuyển sang xem xét hiệu suất và tốc độ:

• HashMap là một bản đồ dựa trên các khóa băm. Nó có thể chèn và lấy các phần tử trongO(1), thời gian không đổi. Để hỗ trợ điều này, các khóa phải triển khaihashCode()vàequals().

• TreeMap là một bản đồ dựa trên cây. Thao tác chèn và tìm nạp của nó mất thời gian logarit, tức làO(log n), phụ thuộc vào số lượng phần tử trong bản đồ. Điều này là cần thiết để các phần tử có một số loại cơ chế so sánh được cung cấp bởi khóa của chúng tôi hoặc Bộ so sánh bên ngoài. Cơ chế này xác định thứ tự lặp lại.

Và những yếu tố này giúp chúng tôi quyết định nên sử dụng bộ sưu tập nào và khi nào.

Nếu chúng ta cần lưu trữ các giá trị theo một thứ tự nhất định, thì sự lựa chọn là hiển nhiên — chúng ta cần một SortedMap . Mặc dù chậm hơn một chút so với HashMap nhưng nó thực hiện các nhiệm vụ quan trọng đối với chúng tôi.

Như đã đề cập trước đó, SortedMap có thể cung cấp cho chúng tôi khóa hoặc giá trị đầu tiên (hoặc cuối cùng) hoặc cặp khóa-giá trị trong bản đồ của chúng tôi, bất kể giá trị đó được thêm vào khi nào. Việc triển khai HashMap không thể thực hiện việc này.

Ví dụ, hãy xem xét một bản đồ có khóa (tên của học sinh) và giá trị (điểm của họ). Giả sử chúng ta muốn làm việc với một danh sách theo thứ tự bảng chữ cái đảo ngược.

1.

SortedMap<String, Integer> sorted = new TreeMap<String,Integer>(Comparator.reverseOrder());
sorted.put("Anthony", 5);
sorted.put("Sara", 5);
sorted.put("Jeff", 4);

String firstKeyFromSortedMapVariant = sorted.firstKey();

Integer markFromSortedMap = sorted.get(firstKeyFromSortedMapVariant);
System.out.println(firstKeyFromSortedMapVariant + " - " + markFromSortedMap);

2.

HashMap<String, Integer> hash = new HashMap<String,Integer>();
hash.put("Anthony", 5);
hash.put("Sara", 5);
hash.put("Jeff", 4);

SortedSet<String> keySetOfHashMap = new TreeSet<String>(Comparator.reverseOrder());
// Or sort manually, storing elements in an array or list (preserving the insertion order)
keySetOfHashMap.addAll(hash.keySet());
String firstKeyFromHashMapVariant = keySetOfHashMap.first();


Integer markFromHashMap = hash.get(firstKeyFromHashMapVariant);
System.out.println(firstKeyFromHashMapVariant + " - " + markFromHashMap);

Ví dụ cho thấy rằng việc sử dụng HashMap làm cho nhiệm vụ trở nên phức tạp hơn, vì HashMap không đảm bảo thứ tự lưu trữ cũng như thứ tự lấy các phần tử từ bản đồ.