Class TreeMap<K,V>
TreeMap là một cấu trúc dữ liệu trong Java được sử dụng để lưu trữ các cặp khóa-giá trị trong một thứ tự được sắp xếp, với hiệu suất cao nhờ triển khai dựa trên cây đỏ-đen (Red-Black Tree), một loại cây nhị phân cân bằng tự động. Điều này đảm bảo rằng các thao tác như containsKey, get, put, và remove tiêu tốn thời gian log(n), với n là số lượng phần tử trong map.
Cây đỏ-đen là một loại cây nhị phân tự cân bằng, nghĩa là cây sẽ tự động duy trì trạng thái cân bằng để đảm bảo các thao tác như tìm kiếm, thêm, hoặc xóa một phần tử đều diễn ra trong thời gian O(log n).
Các quy tắc về màu sắc của cây Đỏ-Đen
↳ 1. Mỗi nút có màu đen hoặc đỏ: Mỗi nút trong cây Đỏ-Đen phải được tô màu hoặc là đen hoặc là đỏ. Đây là điều kiện cơ bản và đơn giản của cây Đỏ-Đen.
↳ 2. Nút gốc (Root) luôn là đen: Nút gốc của cây luôn được tô màu đen. Điều này đảm bảo rằng cây luôn duy trì được tính chất Đỏ-Đen ngay từ nút đầu tiên.
↳ 3. Mọi nút lá (Nút null) đều là đen: Tất cả các nút lá (các nút không có con, thường được đại diện bởi các con trỏ null) đều được coi là đen. Điều này bao gồm cả các nút null nằm ngoài cây thực tế.
↳ 4. Hai nút đỏ liên tiếp không được xuất hiện: Không có hai nút đỏ liền kề trên một đường từ gốc đến lá, nghĩa là một nút đỏ không thể có con trực tiếp là nút đỏ. Nếu một nút đỏ có con, thì con của nó phải là nút đen.
↳ 5. Đường đi từ một nút đến các nút lá của nó phải có cùng số lượng nút đen: Tất cả các đường từ một nút bất kỳ đến các nút lá của nó phải có cùng số lượng nút đen, được gọi là "chiều cao đen" (black height). Điều này giúp cây luôn duy trì sự cân bằng về chiều cao, và ngăn cây trở nên quá mất cân bằng.
↳ 6. Chèn và xóa có thể thay đổi cấu trúc và màu sắc: Khi chèn hoặc xóa một nút, cây có thể trở nên mất cân bằng. Trong trường hợp này, các thao tác cân bằng (như xoay cây và đổi màu nút) sẽ được thực hiện để đảm bảo các quy tắc Đỏ-Đen vẫn được giữ nguyên.
Cấu trúc của một phần tử trong TreeMap
Một phần tử trong TreeMap trong Java được lưu trữ dưới dạng một nút (Node) trong một cây đỏ-đen (Red-Black Tree). Đây là một cây nhị phân tìm kiếm tự cân bằng, giúp TreeMap duy trì các phần tử theo thứ tự tự nhiên hoặc theo thứ tự của bộ so sánh tùy chỉnh. Mỗi nút (node) trong cây TreeMap đại diện cho một phần tử và thường bao gồm các thành phần sau:
↳ Key (Khóa): Key là giá trị duy nhất để xác định phần tử trong TreeMap. Key được sử dụng để so sánh các phần tử với nhau và xác định vị trí của chúng trong cây. Key không thể là null (trong khi HashMap cho phép null keys).
↳ Value (Giá trị): Value là thông tin được liên kết với Key và là giá trị bạn muốn lưu trữ và truy xuất qua Key. Value có thể là bất kỳ đối tượng nào, bao gồm cả null.
↳ Root (Gốc): Là nút đầu tiên được chèn vào cây, nơi bắt đầu của mọi thao tác tìm kiếm. Gốc là nút duy nhất trong cây không có nút cha (parent == null).
↳ Left Child (Con Trái): Nút con nằm bên trái của một nút cha, chứa các giá trị nhỏ hơn nút cha.
↳ Right Child (Con Phải): Nút con nằm bên phải của một nút cha, chứa các giá trị lớn hơn nút cha.
↳ Parent (Cha): Nút mà một nút con được kết nối đến. Mọi nút trong cây (trừ gốc) đều có một nút cha.
Đặc điểm nổi bật của TreeMap<K,V>
↳ Dựa trên Cây Đỏ-Đen (Red-Black Tree): TreeMap sử dụng cây đỏ-đen (red-black tree), một cấu trúc dữ liệu cây cân bằng tự động, để lưu trữ các cặp khóa-giá trị. Điều này giúp đảm bảo các phép toán cơ bản như tìm kiếm, chèn, và xóa có độ phức tạp thời gian là O(log n).
↳ Sắp xếp theo thứ tự tăng dần: Các phần tử trong TreeMap được sắp xếp theo thứ tự tăng dần của các khóa. Nếu bạn không cung cấp một Comparator, TreeMap sẽ sử dụng thứ tự tự nhiên của các khóa (được xác định bởi phương thức compareTo của lớp khóa).
↳ Chỉ cho phép khóa duy nhất: TreeMap chỉ cho phép các khóa duy nhất, nghĩa là không thể có hai phần tử với cùng một khóa. Tuy nhiên, nó có thể chứa nhiều giá trị null. Nếu cố gắng chèn một phần tử với khóa null, sẽ gây ra NullPointerException.
↳ Không đồng bộ (Non-Synchronized): TreeMap không được đồng bộ hóa (non-synchronized). Nếu nhiều luồng (threads) truy cập và sửa đổi TreeMap đồng thời, cần phải đồng bộ hóa bên ngoài. Điều này thường được thực hiện bằng cách đồng bộ hóa trên một đối tượng bao quanh TreeMap, hoặc sử dụng phương thức Collections.synchronizedSortedMap.
↳ Fail-fast Iterators: Các iterator trả về bởi TreeMap là fail-fast, nghĩa là chúng sẽ ném ra ngoại lệ ConcurrentModificationException nếu TreeMap bị thay đổi cấu trúc sau khi iterator được tạo ra, ngoại trừ việc thay đổi thông qua phương thức remove của chính iterator đó.
Khai báo Class TreeMap<K,V> trong Java
Để sử dụng Class TreeMap<K,V>, bạn cần import gói java.util vào đầu file Java của mình.
Cú pháp câu lệnh import:
Cú pháp
import java.util.TreeMap;
Cú pháp khai báo Class TreeMap<K,V>:
Cú pháp
public class TreeMap<K,V>
extends AbstractMap<K,V>
implements NavigableMap<K,V>, Cloneable, Serializable
Dưới đây là giải thích chi tiết về cú pháp khai báo này:
↳ public: Lớp TreeMap có thể được truy cập từ bất kỳ đâu trong chương trình.
↳ class TreeMap<K,V>: Khai báo một lớp có tên TreeMap, sử dụng generic với K là kiểu khóa và V là kiểu giá trị.
↳ extends AbstractMap<K,V>: TreeMap kế thừa từ lớp AbstractMap<K,V>. Lớp AbstractMap cung cấp một số phương thức cơ bản cho các lớp con để thực hiện giao diện Map, bao gồm các phương thức cơ bản như put, get, remove, và size. Điều này giúp TreeMap không cần phải triển khai tất cả các phương thức của Map từ đầu.
↳ implements NavigableMap<K,V>: TreeMap triển khai giao diện NavigableMap<K,V>, một phần của Java Collections Framework. Giao diện NavigableMap mở rộng SortedMap và cung cấp các phương thức bổ sung cho việc điều hướng các phần tử trong bản đồ theo thứ tự. Các phương thức này bao gồm:
↳ lowerEntry(), higherEntry(): Lấy mục có khóa nhỏ hơn hoặc lớn hơn khóa cho trước.
↳ floorEntry(), ceilingEntry(): Lấy mục có khóa nhỏ hơn hoặc bằng, hoặc lớn hơn hoặc bằng khóa cho trước.
↳ pollFirstEntry(), pollLastEntry(): Loại bỏ và trả về mục đầu tiên hoặc cuối cùng trong bản đồ.
↳ implementsCloneable: TreeMap triển khai giao diện Cloneable, cho phép các đối tượng TreeMap được sao chép (clone) bằng phương thức clone(). Điều này có nghĩa là bạn có thể tạo một bản sao của TreeMap hiện tại.
↳ implementsSerializable: TreeMap triển khai giao diện Serializable, cho phép các đối tượng của lớp này có thể được tuần tự hóa (serialized). Tuần tự hóa là quá trình chuyển đối tượng thành một chuỗi byte để lưu trữ hoặc truyền qua mạng. Điều này có nghĩa là bạn có thể lưu trữ một đối tượng TreeMap vào một tệp hoặc gửi nó qua mạng và khôi phục lại đối tượng đó sau này.
Các constructor của lớp TreeMap
Lớp TreeMap cung cấp các constructor để tạo một bản đồ được sắp xếp theo thứ tự tự nhiên hoặc theo bộ so sánh đã cho. Bạn có thể tạo một bản đồ rỗng hoặc một bản đồ chứa các mục nhập từ một bản đồ khác. Dưới đây là bốn constructor của lớp TreeMap:
↳ TreeMap(): Khởi tạo một TreeMap mới, rỗng, sử dụng thứ tự tự nhiên của các khóa của nó.
↳ TreeMap(Comparator<? super K> comparator): Khởi tạo một TreeMap mới, rỗng, được sắp xếp theo bộ so sánh đã cho.
↳ TreeMap(Map<? extends K, ? extends V> m): Khởi tạo một TreeMap mới chứa các ánh xạ giống như bản đồ đã cho, được sắp xếp theo thứ tự tự nhiên của các khóa của nó.
↳ TreeMap(SortedMap<K, ? extends V> m): Khởi tạo một TreeMap mới chứa các ánh xạ giống nhau và sử dụng thứ tự giống như bản đồ đã sắp xếp đã cho.
Ví dụ
// Tạo TreeMap theo thứ tự tự nhiên (sắp xếp theo chuỗi)
TreeMap<String, Integer> treeMap1 = new TreeMap<>();
// Tạo TreeMap theo bộ so sánh tùy chỉnh (sắp xếp theo độ dài chuỗi)
Comparator<String> comparator = Comparator.comparingInt(String::length);
TreeMap<String, Integer> treeMap2 = new TreeMap<>(comparator);
// Tạo TreeMap từ một HashMap
Map<String, Integer> map = new HashMap<>();
TreeMap<String, Integer> treeMap3 = new TreeMap<>(map);
// Tạo TreeMap từ một TreeMap khác
TreeMap<String, Integer> treeMap4 = new TreeMap<>(treeMap1);
}
Lưu ý:
TreeMap là một bản đồ được sắp xếp theo thứ tự tự nhiên hoặc theo bộ so sánh đã cho.
Các mục nhập trong TreeMap được lưu trữ theo thứ tự tăng dần của khóa.
Các phương thức chính trong lớp TreeMap
Lớp TreeMap cung cấp các phương thức để thao tác với các cặp khóa-giá trị trong một bản đồ được sắp xếp theo thứ tự tự nhiên hoặc theo bộ so sánh đã cho. Bạn có thể sử dụng các phương thức này để tìm kiếm, lấy, kiểm tra và duyệt qua các mục nhập trong bản đồ. Dưới đây là danh sách tất cả các phương thức của lớp TreeMap<K,V> trong Java:
↳ Map.Entry<K,V> ceilingEntry(K key): Trả về một ánh xạ khóa-giá trị được liên kết với khóa nhỏ nhất lớn hơn hoặc bằng khóa đã cho, hoặc null nếu không có khóa như vậy.
↳ K ceilingKey(K key): Trả về khóa nhỏ nhất lớn hơn hoặc bằng khóa đã cho, hoặc null nếu không có khóa như vậy.
↳ void clear(): Xóa tất cả các ánh xạ khỏi bản đồ này.
↳ Object clone(): Tạo một bản sao nông của TreeMap instance này.
↳ Comparator<? super K> comparator(): Trả về bộ so sánh được sử dụng để sắp xếp các khóa trong bản đồ này, hoặc null nếu bản đồ này sử dụng thứ tự tự nhiên của các khóa của nó.
↳ boolean containsKey(Object key): Trả về true nếu bản đồ này chứa một ánh xạ cho khóa đã cho.
↳ boolean containsValue(Object value): Trả về true nếu bản đồ này ánh xạ một hoặc nhiều khóa đến giá trị đã cho.
↳ NavigableSet<K> descendingKeySet(): Trả về một view NavigableSet theo thứ tự đảo ngược của các khóa có trong bản đồ này.
↳ NavigableMap<K,V> descendingMap(): Trả về một view theo thứ tự đảo ngược của các ánh xạ có trong bản đồ này.
↳ Set<Map.Entry<K,V>> entrySet(): Trả về một view Set của các ánh xạ có trong bản đồ này.
↳ Map.Entry<K,V> firstEntry(): Trả về một ánh xạ khóa-giá trị được liên kết với khóa nhỏ nhất trong bản đồ này, hoặc null nếu bản đồ trống.
↳ K firstKey(): Trả về khóa đầu tiên (thấp nhất) hiện có trong bản đồ này.
↳ Map.Entry<K,V> floorEntry(K key): Trả về một ánh xạ khóa-giá trị được liên kết với khóa lớn nhất nhỏ hơn hoặc bằng khóa đã cho, hoặc null nếu không có khóa như vậy.
↳ K floorKey(K key): Trả về khóa lớn nhất nhỏ hơn hoặc bằng khóa đã cho, hoặc null nếu không có khóa như vậy.
↳ void forEach(BiConsumer<? super K, ? super V> action): Thực hiện hành động đã cho cho mỗi mục nhập trong bản đồ này cho đến khi tất cả các mục nhập đã được xử lý hoặc hành động ném ra một ngoại lệ.
↳ V get(Object key): Trả về giá trị mà khóa đã cho được ánh xạ đến, hoặc null nếu bản đồ này không chứa ánh xạ nào cho khóa.
↳ SortedMap<K,V> headMap(K toKey): Trả về một view của phần của bản đồ này có các khóa nhỏ hơn strictly toKey.
↳ NavigableMap<K,V> headMap(K toKey, boolean inclusive): Trả về một view của phần của bản đồ này có các khóa nhỏ hơn (hoặc bằng, nếu inclusive là true) toKey.
↳ Map.Entry<K,V> higherEntry(K key): Trả về một ánh xạ khóa-giá trị được liên kết với khóa nhỏ nhất lớn hơn khóa đã cho, hoặc null nếu không có khóa như vậy.
↳ K higherKey(K key): Trả về khóa nhỏ nhất lớn hơn khóa đã cho, hoặc null nếu không có khóa như vậy.
↳ Set<K> keySet(): Trả về một view Set của các khóa có trong bản đồ này.
↳ Map.Entry<K,V> lastEntry(): Trả về một ánh xạ khóa-giá trị được liên kết với khóa lớn nhất trong bản đồ này, hoặc null nếu bản đồ trống.
↳ K lastKey(): Trả về khóa cuối cùng (cao nhất) hiện có trong bản đồ này.
↳ Map.Entry<K,V> lowerEntry(K key): Trả về một ánh xạ khóa-giá trị được liên kết với khóa lớn nhất nhỏ hơn khóa đã cho, hoặc null nếu không có khóa như vậy.
↳ K lowerKey(K key): Trả về khóa lớn nhất nhỏ hơn khóa đã cho, hoặc null nếu không có khóa như vậy.
↳ NavigableSet<K> navigableKeySet(): Trả về một view NavigableSet của các khóa có trong bản đồ này.
↳ Map.Entry<K,V> pollFirstEntry(): Loại bỏ và trả về một ánh xạ khóa-giá trị được liên kết với khóa nhỏ nhất trong bản đồ này, hoặc null nếu bản đồ trống.
↳ Map.Entry<K,V> pollLastEntry(): Loại bỏ và trả về một ánh xạ khóa-giá trị được liên kết với khóa lớn nhất trong bản đồ này, hoặc null nếu bản đồ trống.
↳ V put(K key, V value): Liên kết giá trị đã cho với khóa đã cho trong bản đồ này.
↳ void putAll(Map<? extends K, ? extends V> map): Sao chép tất cả các ánh xạ từ bản đồ đã cho vào bản đồ này.
↳ V remove(Object key): Xóa ánh xạ cho khóa đã cho khỏi bản đồ này nếu có.
↳ V replace(K key, V value): Thay thế mục nhập cho khóa đã cho chỉ khi nó hiện đang được ánh xạ đến một số giá trị.
↳ boolean replace(K key, V oldValue, V newValue): Thay thế mục nhập cho khóa đã cho chỉ khi nó hiện đang được ánh xạ đến giá trị đã cho.
↳ void replaceAll(BiFunction<? super K, ? super V, ? extends V> function): Thay thế giá trị của mỗi mục nhập bằng kết quả của việc gọi hàm đã cho trên mục nhập đó cho đến khi tất cả các mục nhập đã được xử lý hoặc hàm ném ra một ngoại lệ.
↳ int size(): Trả về số lượng ánh xạ khóa-giá trị trong bản đồ này.
↳ NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive): Trả về một view của phần của bản đồ này có các khóa trong khoảng từ fromKey đến toKey.
↳ SortedMap<K,V> subMap(K fromKey, K toKey): Trả về một view của phần của bản đồ này có các khóa trong khoảng từ fromKey, inclusive, đến toKey, exclusive.
↳ SortedMap<K,V> tailMap(K fromKey): Trả về một view của phần của bản đồ này có các khóa lớn hơn hoặc bằng fromKey.
↳ NavigableMap<K,V> tailMap(K fromKey, boolean inclusive): Trả về một view của phần của bản đồ này có các khóa lớn hơn (hoặc bằng, nếu inclusive là true) fromKey.
↳ Collection<V> values(): Trả về một view Collection của các giá trị có trong bản đồ này.
Ví dụ về cách sử dụng các phương thức put(), remove(), replace() và replaceAll()
Dưới đây là ví dụ về việc sử dụng các phương thức put(), remove(), replace() và replaceAll() của lớp TreeMap trong Java.
Ví dụ: Example.java
import java.util.TreeMap;
public class Example {
public static void main(String[] args) {
// Tạo một TreeMap với các khóa là Integer và giá trị là String
TreeMap<Integer, String> treeMap = new TreeMap<>();
// Thêm các phần tử vào TreeMap
treeMap.put(1, "A");
treeMap.put(2, "B");
treeMap.put(3, "C");
// Hiển thị TreeMap sau khi thêm các phần tử
System.out.println("TreeMap sau khi thêm các phần tử: " + treeMap);
// Xóa phần tử với khóa 2
treeMap.remove(2);
// Hiển thị TreeMap sau khi xóa phần tử
System.out.println("TreeMap sau khi xóa phần tử với khóa 2: " + treeMap);
// Thay thế giá trị cho khóa 1 chỉ khi giá trị hiện tại là "A"
treeMap.replace(1, "A", "Al");
// Hiển thị TreeMap sau khi thay thế giá trị
System.out.println("TreeMap sau khi thay thế giá trị cho khóa 1: " + treeMap);
// Thay thế giá trị của mỗi mục nhập bằng kết quả của việc gọi hàm
treeMap.replaceAll((key, value) -> value.toUpperCase());
// Hiển thị TreeMap sau khi thay thế tất cả giá trị
System.out.println("TreeMap sau khi thay thế tất cả giá trị: " + treeMap);
}
}
Kết quả của chương trình là:
TreeMap sau khi xóa phần tử với khóa 2: {1=A, 3=C}
TreeMap sau khi thay thế giá trị cho khóa 1: {1=Al, 3=C}
TreeMap sau khi thay thế tất cả giá trị: {1=AL, 3=C}
Ví dụ về các phương thức firstKey(), lastKey(), firstEntry() và lastEntry()
Dưới đây là ví dụ về việc sử dụng các phương thức firstKey(), lastKey(), firstEntry() và lastEntry() của lớp TreeMap trong Java. Các phương thức này rất hữu ích để truy xuất khóa hoặc mục nhập đầu tiên và cuối cùng trong một bản đồ được sắp xếp.
Ví dụ: Example.java
import java.util.TreeMap;
public class Example {
public static void main(String[] args) {
// Tạo một TreeMap với các khóa là Integer và giá trị là String
TreeMap<Integer, String> treeMap = new TreeMap<>();
// Thêm các phần tử vào TreeMap
treeMap.put(1, "A");
treeMap.put(2, "B");
treeMap.put(3, "Ch");
treeMap.put(4, "D");
// Hiển thị khóa đầu tiên và khóa cuối cùng
System.out.println("Khóa đầu tiên: " + treeMap.firstKey());
System.out.println("Khóa cuối cùng: " + treeMap.lastKey());
// Hiển thị mục nhập đầu tiên và mục nhập cuối cùng
System.out.println("Mục nhập đầu tiên: " + treeMap.firstEntry());
System.out.println("Mục nhập cuối cùng: " + treeMap.lastEntry());
}
}
Kết quả của chương trình là:
Khóa cuối cùng: 4
Mục nhập đầu tiên: 1=A
Mục nhập cuối cùng: 4=D
Ví dụ về các phương thức ceilingKey(), floorKey(), higherKey() và lowerKey()
Các phương thức ceilingKey(), floorKey(), higherKey() và lowerKey() trong lớp TreeMap của Java được sử dụng để tìm các khóa gần nhất với một khóa đã cho theo thứ tự sắp xếp. Dưới đây là một ví dụ để minh họa cách sử dụng các phương thức này.
Ví dụ: Example.java
import java.util.TreeMap;
public class Example {
public static void main(String[] args) {
// Tạo một TreeMap với các khóa là Integer và giá trị là String
TreeMap<Integer, String> treeMap = new TreeMap<>();
// Thêm các phần tử vào TreeMap
treeMap.put(40, "D");
treeMap.put(50, "E");
// Các khóa để tìm kiếm
Integer[] keysToFind = {35, 45};
// Hiển thị kết quả tìm kiếm cho mỗi khóa
for (Integer key : keysToFind) {
System.out.println("Khóa: " + key);
System.out.println("Ceiling Key: " + treeMap.ceilingKey(key)); // Khóa nhỏ nhất >= key
System.out.println("Floor Key: " + treeMap.floorKey(key)); // Khóa lớn nhất <= key
System.out.println("Higher Key: " + treeMap.higherKey(key)); // Khóa nhỏ nhất > key
System.out.println("Lower Key: " + treeMap.lowerKey(key)); // Khóa lớn nhất < key
System.out.println();
}
}
}
Kết quả của chương trình là:
Ceiling Key: 40
Floor Key: null
Higher Key: 40
Lower Key: null
Khóa: 45
Ceiling Key: 50
Floor Key: 40
Higher Key: 50
Lower Key: 40
Ví dụ về các phương thức ceilingEntry(), floorEntry(), higherEntry() và lowerEntry()
Các phương thức ceilingEntry(), floorEntry(), higherEntry() và lowerEntry() trong lớp TreeMap được sử dụng để tìm các mục nhập gần nhất với một khóa đã cho, theo thứ tự sắp xếp. Dưới đây là một ví dụ về cách sử dụng các phương thức này.
Ví dụ: Example.java
import java.util.Map;
import java.util.TreeMap;
public class Example {
public static void main(String[] args) {
// Tạo một TreeMap với các khóa là Integer và giá trị là String
TreeMap<Integer, String> treeMap = new TreeMap<>();
// Thêm các phần tử vào TreeMap
treeMap.put(10, "A");
treeMap.put(20, "B");
// Các khóa để tìm kiếm
Integer[] keysToFind = {15, 25};
// Hiển thị kết quả tìm kiếm cho mỗi khóa
for (Integer key : keysToFind) {
System.out.println("Khóa: " + key);
Map.Entry<Integer, String> ceilingEntry = treeMap.ceilingEntry(key);
Map.Entry<Integer, String> floorEntry = treeMap.floorEntry(key);
Map.Entry<Integer, String> higherEntry = treeMap.higherEntry(key);
Map.Entry<Integer, String> lowerEntry = treeMap.lowerEntry(key);
System.out.println("Ceiling Entry: " + (ceilingEntry != null ? ceilingEntry : "null"));
System.out.println("Floor Entry: " + (floorEntry != null ? floorEntry : "null"));
System.out.println("Higher Entry: " + (higherEntry != null ? higherEntry : "null"));
System.out.println("Lower Entry: " + (lowerEntry != null ? lowerEntry : "null"));
System.out.println();
}
}
}
Kết quả của chương trình là:
Ceiling Entry: 20=B
Floor Entry: 10=A
Higher Entry: 20=B
Lower Entry: 10=A
Khóa: 25
Ceiling Entry: null
Floor Entry: 20=B
Higher Entry: null
Lower Entry: 20=B
Ví dụ về các phương thức subMap(), headMap() và tailMap()
Các phương thức subMap(), headMap() và tailMap() trong lớp TreeMap cho phép bạn tạo các phần con của bản đồ dựa trên các phạm vi khóa. Dưới đây là các phương thức và ví dụ về cách sử dụng chúng:
Ví dụ: Example.java
import java.util.SortedMap;
import java.util.TreeMap;
public class Example {
public static void main(String[] args) {
// Tạo một TreeMap với các khóa là Integer và giá trị là String
TreeMap<Integer, String> treeMap = new TreeMap<>();
// Thêm các phần tử vào TreeMap
treeMap.put(1, "One");
treeMap.put(2, "Two");
treeMap.put(3, "Three");
treeMap.put(4, "Four");
treeMap.put(5, "Five");
treeMap.put(6, "Six");
treeMap.put(7, "Seven");
// subMap: Khóa từ 2 (bao gồm) đến 5 (không bao gồm)
SortedMap<Integer, String> subMap = treeMap.subMap(2, 5);
System.out.println("SubMap (2, 5): " + subMap);
// headMap: Khóa nhỏ hơn 4 (không bao gồm)
SortedMap<Integer, String> headMap = treeMap.headMap(4);
System.out.println("HeadMap (4): " + headMap);
// tailMap: Khóa từ 4 (bao gồm) trở đi
SortedMap<Integer, String> tailMap = treeMap.tailMap(4);
System.out.println("TailMap (4): " + tailMap);
}
}
Kết quả của chương trình là:
HeadMap (4): {1=One, 2=Two, 3=Three}
TailMap (4): {4=Four, 5=Five, 6=Six, 7=Seven}
Ví dụ về các phương thức navigableKeySet(), descendingKeySet() và descendingMap()
Dưới đây là ví dụ về cách sử dụng các phương thức navigableKeySet(), descendingKeySet() và descendingMap() của lớp TreeMap trong Java. Các phương thức này thuộc về giao diện NavigableMap và cung cấp các tính năng điều hướng hữu ích.
Ví dụ: Example.java
import java.util.NavigableMap;
import java.util.NavigableSet;
import java.util.TreeMap;
public class Example {
public static void main(String[] args) {
// Tạo một TreeMap với các khóa là Integer và giá trị là String
TreeMap<Integer, String> treeMap = new TreeMap<>();
// Thêm các phần tử vào TreeMap
treeMap.put(1, "One");
treeMap.put(2, "Two");
treeMap.put(3, "Three");
treeMap.put(4, "Four");
treeMap.put(5, "Five");
treeMap.put(6, "Six");
treeMap.put(7, "Seven");
// NavigableKeySet: Trả về một view NavigableSet của các khóa có trong TreeMap này
NavigableSet<Integer> navigableKeySet = treeMap.navigableKeySet();
System.out.println("Navigable Key Set: " + navigableKeySet);
// DescendingKeySet: Trả về một view NavigableSet theo thứ tự đảo ngược của các khóa có trong TreeMap này
NavigableSet<Integer> descendingKeySet = treeMap.descendingKeySet();
System.out.println("Descending Key Set: " + descendingKeySet);
// DescendingMap: Trả về một view theo thứ tự đảo ngược của các ánh xạ có trong TreeMap này
NavigableMap<Integer, String> descendingMap = treeMap.descendingMap();
System.out.println("Descending Map: " + descendingMap);
}
}
Kết quả của chương trình là:
Descending Key Set: [7, 6, 5, 4, 3, 2, 1]
Descending Map: {7=Seven, 6=Six, 5=Five, 4=Four, 3=Three, 2=Two, 1=One}
Ví dụ về các phương thức pollFirstEntry() và pollLastEntry()
Dưới đây là ví dụ về cách sử dụng các phương thức pollFirstEntry() và pollLastEntry() của lớp TreeMap trong Java. Các phương thức này cho phép bạn loại bỏ và trả về mục nhập đầu tiên hoặc cuối cùng của bản đồ.
Ví dụ: Example.java
import java.util.Map;
import java.util.TreeMap;
public class Example {
public static void main(String[] args) {
// Tạo một TreeMap với các khóa là Integer và giá trị là String
TreeMap<Integer, String> treeMap = new TreeMap<>();
// Thêm các phần tử vào TreeMap
treeMap.put(1, "One");
treeMap.put(2, "Two");
treeMap.put(3, "Three");
treeMap.put(4, "Four");
treeMap.put(5, "Five");
// In TreeMap trước khi sử dụng pollFirstEntry() và pollLastEntry()
System.out.println("TreeMap trước khi gọi pollFirstEntry() và pollLastEntry(): " + treeMap);
// Loại bỏ và trả về mục nhập đầu tiên trong TreeMap
Map.Entry<Integer, String> firstEntry = treeMap.pollFirstEntry();
System.out.println("Mục nhập đầu tiên bị loại bỏ: " + firstEntry);
// Loại bỏ và trả về mục nhập cuối cùng trong TreeMap
Map.Entry<Integer, String> lastEntry = treeMap.pollLastEntry();
System.out.println("Mục nhập cuối cùng bị loại bỏ: " + lastEntry);
// In TreeMap sau khi gọi pollFirstEntry() và pollLastEntry()
System.out.println("TreeMap sau khi gọi pollFirstEntry() và pollLastEntry(): " + treeMap);
}
}
Kết quả của chương trình là:
Mục nhập đầu tiên bị loại bỏ: 1=One
Mục nhập cuối cùng bị loại bỏ: 5=Five
TreeMap sau khi gọi pollFirstEntry() và pollLastEntry(): {2=Two, 3=Three, 4=Four}
Ví dụ về việc sử dụng Iterator với TreeMap
Dưới đây là ví dụ về cách sử dụng Iterator để duyệt các phần tử của TreeMap trong Java.
Ví dụ: Example.java
import java.util.Iterator;
import java.util.Map;
import java.util.TreeMap;
public class Example {
public static void main(String[] args) {
// Tạo một TreeMap với các khóa là Integer và giá trị là String
TreeMap<Integer, String> treeMap = new TreeMap<>();
// Thêm các phần tử vào TreeMap
treeMap.put(1, "One");
treeMap.put(2, "Two");
treeMap.put(3, "Three");
treeMap.put(4, "Four");
treeMap.put(5, "Five");
// Duyệt qua các phần tử của TreeMap bằng cách sử dụng Iterator
System.out.println("Duyệt các phần tử của TreeMap:");
// Duyệt qua các mục nhập (entry) của TreeMap
Iterator<Map.Entry<Integer, String>> entryIterator = treeMap.entrySet().iterator();
while (entryIterator.hasNext()) {
Map.Entry<Integer, String> entry = entryIterator.next();
System.out.println("Khóa: " + entry.getKey() + ", Giá trị: " + entry.getValue());
}
// Duyệt qua các khóa của TreeMap
Iterator<Integer> keyIterator = treeMap.keySet().iterator();
System.out.println("\nDuyệt các khóa của TreeMap:");
while (keyIterator.hasNext()) {
Integer key = keyIterator.next();
System.out.println("Khóa: " + key);
}
// Duyệt qua các giá trị của TreeMap
Iterator<String> valueIterator = treeMap.values().iterator();
System.out.println("\nDuyệt các giá trị của TreeMap:");
while (valueIterator.hasNext()) {
String value = valueIterator.next();
System.out.println("Giá trị: " + value);
}
}
}
Kết quả của chương trình là:
Khóa: 1, Giá trị: One
Khóa: 2, Giá trị: Two
Khóa: 3, Giá trị: Three
Khóa: 4, Giá trị: Four
Khóa: 5, Giá trị: Five
Duyệt các khóa của TreeMap:
Khóa: 1
Khóa: 2
Khóa: 3
Khóa: 4
Khóa: 5
Duyệt các giá trị của TreeMap:
Giá trị: One
Giá trị: Two
Giá trị: Three
Giá trị: Four
Giá trị: Five
Ví dụ về cách sử dụng TreeMap trong Java với các lớp do người dùng tự định nghĩa
Dưới đây là ví dụ về cách sử dụng TreeMap trong Java với các lớp do người dùng tự định nghĩa. Ví dụ này sử dụng một lớp Person để làm khóa và một lớp Address để làm giá trị.
Ví dụ: Example.java
import java.util.Map;
import java.util.TreeMap;
// Lớp Person làm khóa trong TreeMap
class Person implements Comparable<Person> {
private String name;
private int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public int getAge() {
return age;
}
@Override
public int compareTo(Person other) {
// So sánh theo độ tuổi
return Integer.compare(this.age, other.age);
}
@Override
public String toString() {
return name + " (" + age + " tuổi)";
}
}
// Lớp Address làm giá trị trong TreeMap
class Address {
private String street;
private String city;
public Address(String street, String city) {
this.street = street;
this.city = city;
}
public String getStreet() {
return street;
}
public String getCity() {
return city;
}
@Override
public String toString() {
return street + ", " + city;
}
}
public class Example {
public static void main(String[] args) {
// Tạo TreeMap với Person làm khóa và Address làm giá trị
TreeMap<Person, Address> treeMap = new TreeMap<>();
// Thêm các phần tử vào TreeMap
treeMap.put(new Person("A", 30), new Address("123 El", "Sp"));
treeMap.put(new Person("B", 25), new Address("456 M", "Sh"));
treeMap.put(new Person("C", 35), new Address("789 O", "Ca"));
// Duyệt qua các phần tử của TreeMap
System.out.println("Danh sách các người và địa chỉ:");
for (Map.Entry<Person, Address> entry : treeMap.entrySet()) {
Person person = entry.getKey();
Address address = entry.getValue();
System.out.println("Người: " + person + ", Địa chỉ: " + address);
}
// Tìm kiếm và hiển thị thông tin của một người
Person searchKey = new Person("B", 25);
Address address = treeMap.get(searchKey);
if (address != null) {
System.out.println("\nThông tin của B:");
System.out.println("Địa chỉ: " + address);
} else {
System.out.println("\nKhông tìm thấy thông tin của B.");
}
}
}
Kết quả của chương trình là:
Người: B (25 tuổi), Địa chỉ: 456 M, Sh
Người: A (30 tuổi), Địa chỉ: 123 El, Sp
Người: C (35 tuổi), Địa chỉ: 789 O, Ca
Thông tin của B:
Địa chỉ: 456 M, Sh
So sánh giữa HashMap, Hashtable, LinkedHashMap và TreeMap
Dưới đây là một bảng so sánh giữa HashMap, Hashtable, LinkedHashMap, và TreeMap trong Java:
| Đặc Điểm | HashMap | Hashtable | LinkedHashMap | TreeMap |
|---|---|---|---|---|
| Kế thừa | AbstractMap<K,V> | Dictionary<K,V> | HashMap<K,V> | AbstractMap<K,V> |
| Triển khai giao diện | Map<K,V> | Map<K,V> | Map<K,V>, NavigableMap<K,V> | NavigableMap<K,V> |
| Cấu trúc dữ liệu | Hash table | Hash table | Hash table với danh sách liên kết | Cây đỏ-đen (Red-Black Tree) |
| Thứ tự duy trì | Không duy trì thứ tự | Không duy trì thứ tự | Thứ tự theo cách chèn (Insertion Order) | Thứ tự theo khóa (Ascending Order) |
| Cho phép khóa null | Có (1 khóa null) | Không | Không (0 khóa null) | Không |
| Cho phép giá trị null | Có (nhiều giá trị null) | Có (nhiều giá trị null) | Có (nhiều giá trị null) | Có (nhiều giá trị null) |
| Tốc độ thực thi | Tốt nhất cho các thao tác cơ bản (O(1)) | Tốt nhất cho các thao tác cơ bản (O(1)) | Hơi chậm hơn HashMap do danh sách liên kết | O(log n) cho các thao tác cơ bản |
| Synchronized | Không đồng bộ | Đồng bộ (Synchronized) | Không đồng bộ | Không đồng bộ |
Hy vọng bảng so sánh này giúp bạn nắm rõ các đặc điểm khác nhau giữa các lớp HashMap, Hashtable, LinkedHashMap, và TreeMap.
Như vậy, chúng ta đã tìm hiểu các phương thức chính của lớp TreeMap. Với khả năng tự động sắp xếp các cặp khóa-giá trị, TreeMap là lựa chọn hoàn hảo khi bạn cần một Map có trật tự và khả năng truy xuất dữ liệu theo thứ tự tự nhiên hoặc theo một quy tắc so sánh tùy chỉnh. Hiểu rõ cách TreeMap sử dụng cấu trúc cây đỏ-đen để duy trì sự sắp xếp sẽ giúp bạn quản lý dữ liệu một cách hiệu quả trong các tình huống đòi hỏi thứ tự rõ ràng.