TreeMap trong Java

NỘI DUNG BÀI VIẾT

TreeMap trong Java là một trong những implement Map và nó là một phần của Java Collections Framework.

Một số điểm quan trọng cần nhớ về TreeMap trong Java:

Ngoài việc triển khai interface Map, TreeMap cũng thực hiện NavigableMap và gián tiếp triển khai interface SortedMap. TreeMap cũng mở rộng AbstractMaplớp.
Các mục nhập TreeMap được sắp xếp theo thứ tự tự nhiên của các khóa của nó. Nó cũng cung cấp một phương thức khởi tạo để cung cấp Collection được sử dụng để đặt hàng. Vì vậy, nếu bạn đang sử dụng bất kỳ lớp nào làm khóa, hãy đảm bảo rằng lớp đó đang triển khai giao diện Có thể so sánh để sắp xếp tự nhiên. Kiểm tra các câu hỏi phỏng vấn bộ sưu tập java để hiểu tầm quan trọng của các phương pháp này.
Việc triển khai Java TreeMap cung cấp chi phí thời gian log (n) được đảm bảo cho các hoạt động chứa, lấy, đặt và loại bỏ các hoạt động chứa khóa, lấy, đặt và gỡ bỏ.
TreeMap không được đồng bộ hóa và do đó không an toàn cho chuỗi. Đối với môi trường đa luồng, bạn có thể nhận được một phương pháp đồng bộ hóa được bao bọc bằng cách sử dụng Collections.synchronizedSortedMap.
Các phương thức TreeMap để lấy bộ khóa và giá trị trả về Iterator có bản chất là không nhanh, vì vậy bất kỳ sửa đổi đồng thời nào cũng sẽ ném ra ConcurrentModificationException.
TreeMap trong Java không cho phép các khóa rỗng, tuy nhiên, bạn có thể có nhiều giá trị null được liên kết với các khóa khác nhau.

Ví dụ về TreeMap trong Java

Hãy xem chương trình ví dụ của java TreeMap để thấy nó được sắp xếp tự nhiên trong hoạt động.


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

public class JavaTreeMapExample {

	public static void main(String[] args) {
		
		Map<Integer,String> map = new TreeMap<>();
		
		map.put(10, "10");
		map.put(1, "1");
		map.put(5, "5");
		
		System.out.println(map);
		
		map = new TreeMap<>(new Comparator<Integer>() {

			@Override
			public int compare(Integer x, Integer y) {
				return (x > y) ? -1 : ((x == y) ? 0 : 1);
			}
			
		});
		map.put(10, "10");
		map.put(1, "1");
		map.put(5, "5");
		System.out.println(map);

	}

}
Code language: JavaScript (javascript)

Nó sẽ tạo ra sản lượng dưới đây.


{1=1, 5=5, 10=10}
{10=10, 5=5, 1=1}

Lưu ý rằng khi chúng tôi không cung cấp Bộ so sánh trong khi tạo Sơ đồ cây, nó đang sử dụng compareTophương thức Số nguyên để sắp xếp các khóa. Đó là lý do tại sao các phím có thứ tự tăng dần mặc dù chúng ta chèn nó theo bất kỳ thứ tự nào.

Lần tới, chúng tôi sẽ cung cấp triển khai Comparator để đảo ngược thứ tự và nó đang được TreeMap sử dụng. Vì vậy, các khóa được lưu trữ theo thứ tự giảm dần.

Để đơn giản, tôi đang cung cấp một triển khai lớp ẩn danh của Comparator ở trên, chúng ta có thể sử dụng các biểu thức lambda để làm điều tương tự trong một dòng duy nhất.


map = new TreeMap<>((x,y) -> {return (x > y) ? -1 : ((x == y) ? 0 : 1);});
Code language: JavaScript (javascript)

TreeMap so với HashMap

TreeMap và HashMap đều triển khai giao diện Bản đồ và một phần của khung thu thập. Hãy xem xét một số điểm khác biệt giữa TreeMap và HashMap.

Các mục nhập TreeMap được sắp xếp theo thứ tự tự nhiên của các khóa trong khi HashMap không lưu trữ các mục nhập theo bất kỳ thứ tự nào.
TreeMap không cho phép khóa null trong khi chúng ta có thể có một khóa null trong HashMap.
Vì TreeMap lưu trữ các mục nhập theo cách được sắp xếp nên HashMap sẽ chậm hơn một chút trong việc lưu trữ và truy xuất các đối tượng.
TreeMap sử dụng triển khai NavigableMap dựa trên cây Đỏ-đen trong khi HashMap sử dụng triển khai thuật toán băm.
TreeMap triển khai NavigableMap, vì vậy bạn sẽ nhận được một số tính năng bổ sung không có trong HashMap. Ví dụ – sơ đồ phụ, khóa đầu tiên, khóa cuối cùng, bản đồ đầu, bản đồ đuôi, v.v.

Khi nào sử dụng TreeMap trong Java?

Hầu hết thời gian HashMap sẽ đủ để sử dụng như việc triển khai Bản đồ trong chương trình của bạn. Nhưng nếu bạn có một số yêu cầu đặc biệt liên quan đến sắp xếp, tìm khóa tiếp theo thấp hơn và cao hơn, làm việc trên một sơ đồ con thì bạn có thể sử dụng TreeMap.

Hãy xem một chương trình ví dụ TreeMap đơn giản cho thấy cách sử dụng các phương thức NavigableMap.


import java.util.Map;
import java.util.Map.Entry;
import java.util.TreeMap;

public class JavaTreeMapNavigationExamples {

	public static void main(String[] args) {
		
		//we have to define object as TreeMap to use NavigableMap functions
		TreeMap<Integer,String> map = new TreeMap<>();
		for(int i=0;i<10;i++) {
			map.put(i, i+"");
		}
		
		System.out.println(map);
		
		//find id closest to 5, lower and higher
		Entry<Integer,String> entry = map.lowerEntry(5);
		System.out.println("Closest Lower key than 5 is "+entry);
		entry = map.higherEntry(5);
		System.out.println("Closest Higher key than 5 is "+entry);
		
		System.out.println("Closest Lower key than 4 is "+map.lowerKey(4));
		
		entry = map.floorEntry(5);
		System.out.println("Closest floor entry than 5 is "+entry);
		
		entry = map.ceilingEntry(4);
		System.out.println("Closest ceiling key than 4 is "+entry);
		
		entry = map.firstEntry();
		System.out.println("First Entry is "+entry);

		entry = map.lastEntry();
		System.out.println("Last Entry is "+entry);
		
		Map<Integer, String> reversedMap = map.descendingMap();
		System.out.println("Reversed Map: "+reversedMap);
		
		//poll and remove first, last entries
		entry = map.pollFirstEntry();
		System.out.println("First Entry is "+entry);
		entry = map.pollLastEntry();
		System.out.println("Last Entry is "+entry);
		System.out.println("Updated Map: "+map);
		
		//submap example
		Map<Integer, String> subMap = map.subMap(2, true, 6, true);
		System.out.println("Submap: "+subMap);
		
		subMap = map.headMap(5, true);
		System.out.println("HeadMap: "+subMap);

		subMap = map.tailMap(5, true);
		System.out.println("TailMap: "+subMap);
	}

}
Code language: JavaScript (javascript)

Khi chúng ta thực hiện chương trình ví dụ TreeMap ở trên, nó sẽ tạo ra kết quả sau.


{0=0, 1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8, 9=9}
Closest Lower key than 5 is 4=4
Closest Higher key than 5 is 6=6
Closest Lower key than 4 is 3
Closest floor entry than 5 is 5=5
Closest ceiling key than 4 is 4=4
First Entry is 0=0
Last Entry is 9=9
Reversed Map: {9=9, 8=8, 7=7, 6=6, 5=5, 4=4, 3=3, 2=2, 1=1, 0=0}
First Entry is 0=0
Last Entry is 9=9
Updated Map: {1=1, 2=2, 3=3, 4=4, 5=5, 6=6, 7=7, 8=8}
Submap: {2=2, 3=3, 4=4, 5=5, 6=6}
HeadMap: {1=1, 2=2, 3=3, 4=4, 5=5}
TailMap: {5=5, 6=6, 7=7, 8=8}
Code language: JavaScript (javascript)

Tổng kết

Đó là tất cả để cập nhật nhanh cho TreeMap trong Java, tôi hy vọng bạn thích đọc nó. Chúc bạn học tốt.

Nguồn video: DailyCodingTutorials

TreeMap trong Java