TreeSet supports two sorting methods: natural sorting and custom sorting. TreeSet uses natural sorting by default.
1. Natural sorting
TreeSet will call the compareTo(Object obj) method of the collection element to compare the size relationship between elements, and then arrange the collection elements in ascending order. This method is natural sorting. (Presponse for comparison: the two objects have the same type).
Java provides a Comparable interface, which defines a compareTo(Object obj) method, which returns an integer value. The class implementing the interface must implement the method. The object of the class implementing the interface can compare the size. When an object calls the method to compare with another object, for example obj1.comparTo(obj2), if the method returns 0, it means that the two objects are equal; if a positive integer is returned, it means that obj1 is greater than obj2; if the method is returned Returning a negative integer means obj1 is less than obj2.
Common Java classes implement Comparable interface and provide standards for comparative sizes. Common classes that implement Comparable interface:
If you try to add an object to a TreeSet, the object's class must implement the Comparable interface.
An error will be reported in the following program:
class Err { } public class TestTreeSetError { public static void main(String[] args) { TreeSet ts = new TreeSet(); //Add two Err objects to the TreeSet collection ts.add(ne w Err()); ts. add(new Err()); } }illustrate:
The above program tries to add 2 Err objects to the TreeSet collection. When adding the first object, there is no element in the TreeSet, so there is no problem; when adding the second Err object, TreeSet will call the compareTo(Object obj) of the object ) method is compared with other elements in the collection - if the corresponding class does not implement the Comparable interface, a ClassCastException will be raised. Moreover, when trying to remove the first element of the element from the TreeSet, a ClassCastException exception will still be raised.
When comparing objects using the compareTo(Object obj) method, the type of the compared object obj needs to be cast to the same type, because only two instances of the same class can compare the size. That is, the object added to the TreeSet should be of the same class, otherwise a ClassCastException will be raised. For example, when adding a string object to a TreeSet, this operation is completely normal. When adding the second Date object, TreeSet will call the compareTo(Object obj) method of the object to compare with other elements in the collection, and the program will throw an exception at this time.
In actual programming, programmers can define their own classes to add multiple types of objects to TreeSet, provided that the user-defined class implements the Comparable interface. When implementing this interface, no forced types are performed when implementing the compareTo(Object obj) method. Convert. However, when operating the collection data in TreeSet, ClassCastExceptio exceptions will still occur for elements of different types. (You will understand after reading carefully)
When an object is added to the TreeSet collection, TreeSet calls the object's compareTo(Object obj) method to compare the size with other objects in the container, and then determines its storage location based on the red and black tree algorithm. If two objects are compared equally by compareTo(Object obj), TreeSet considers them to store the same location.
For TreeSet collections, the criterion for determining that two objects are not equal is: two objects return false through the equals method comparison, or compareTo (Object obj) comparison does not return 0 - even if the two objects are the same object, TreeSet They will also be processed as two objects.
The following program shows:
//The Z class, rewritten the equals method, always returns false, //The compareTo(Object obj) method, always returns positive integer class Z implements Comparable { int age; public Z(int age) { this. age = age; } public boolean equals(Object obj) { return false; } public int compareTo(Object obj) { return 1; } } public class TestTreeSet { pub lic static void main(String[] args) { TreeSet set = new TreeSet (); Z z1 = new Z(6); set.add(z1); System.out.println(set.add(z1)); //The following outputs the set set and you will see 2 elements System.out .println(set); //Modify the age attribute of the first element of the set set ((Z)(set.first())).age = 9; //Output the age attribute of the last element of the set set, and Seeing also becomes 9 System.out.println(((Z)(set.last())).age); } }Program running results:
true
[TreeSet.Z@1fb8ee3, TreeSet.Z@1fb8ee3]
9
illustrate:
The same object is added twice in the program, because the equals() method of the z1 object always returns false, and the compareTo(Object obj) method always returns 1. In this way, TreeSet will think that the z1 object is different from itself, so add two z1 objects to the TreeSet. The two elements saved by the TreeSet object are actually the same element. Therefore, after modifying the age attribute of the first element in the TreeSet collection, the age attribute of the last element in the TreeSet collection also changes.
Summary : When you need to put an object into TreeSet, and rewrite the equals() method of the corresponding class of the object, you should ensure that the method has consistent results with the compareTo(Object obj) method. The rule is: If two objects pass When the equals method comparison returns true, the two objects should return 0 by comparing the compareTo (Object obj) method.
If two objects are compared by the equals method, but the two objects are compared by the compareTo(Object obj) method and do not return 0, this will cause TreeSet to save the two objects in different locations, so that both objects are It can be added successfully, which is a bit different from the rules of Set collections.
If two objects return 0 by comparing the compareTo(Object obj) method, but they return false by comparing the equals method: Because the two objects are equally compared with comparing the compareTo(Object obj) method, TreeSet will try to save them in The same location, but it actually doesn't work (otherwise there will be only one object left), so it's more troublesome to handle.
If a mutable object is added to a TreeSet and the subsequent program modifies the properties of the mutable object, causing it to change the size order with other objects, but the TreeSet will not adjust their order again, and may even cause it to be saved in the TreeSet These two objects, they return true by comparing equals method, and compareTo (Object obj) method returns 0.
The following program shows:
class R { int count; public R(int count) { this.count = count; } public String toString() { return "R(count attribute:" + count + ")"; } public boolean equals(Object obj) { if (obj instanceof R) { R r = (R)obj; if (r.count == this.count) { return true; } } return false; } public int hashCode() { return this.count ; } } public class TestHashSet2 { public static void main(String[] args) { HashSet hs = new HashSet(); hs.add(new R(5)); hs.add(new R(-3)); hs.add(new R(9)); hs.add(new R(-2)); //Print the TreeSet collection, the collection elements are ordered System.out.println(hs); //Take out the first element Iterator it = hs.iterator(); R first = (R)it.next(); // Assign a value to the count attribute of the first element first.count = -3; //Output count again and see that the element in TreeSet is in none Sequential state System.out.println(hs); hs.remove(new R(-3)); System.out.println(hs); //Output false System.out.println("whether hs contains count is -3 R object? " + hs.contains(new R(-3))); //Output false System.out.println("Does hs contain R object with count of 5?" + hs.contains(new R(5 ))); } }Program running results:
[R(count attribute:-3), R(count attribute:-2), R(count attribute:5), R(count attribute:9)]
[R(count attribute: 20), R(count attribute:-2), R(count attribute: 5), R(count attribute:-2)]
[R(count attribute: 20), R(count attribute:-2), R(count attribute: 5), R(count attribute:-2)]
[R(count attribute: 20), R(count attribute:-2), R(count attribute:-2)]
illustrate:
The R object in the above program is a normal rewrite of the equals method and comparable method class. Both methods use the count attribute of the R object as the basis for judgment. You can see that the first output of the program is arranged in an orderly manner. When the count property of the R object is changed, the output result of the program also changes and contains duplicate elements. Once the properties of variable elements in the TreeSet collection are changed, when the object is deleted in the view, TreeSet will fail to be deleted (even elements that are original in the collection have not been modified, but elements that are equal to the modified elements cannot be deleted). So delete the count
When an R object with -2, no elements are deleted; the program can delete an R object with count of 5, which indicates that TreeSet can delete objects that have no modified attributes and are not repeated with other modified attributes.
Summary: With HashSet, it will be very complex and error-prone when dealing with these objects. In order to make the program more robust, it is recommended that only immutable objects be placed in the HashSet and TreeSet collections.
2. Custom sorting
The natural sort of TreeSet is based on the size of the collection elements, and TreeSet arranges them in ascending order. If you need to implement custom sorting, such as descending order, you can use the Comparator interface. This interface contains an int compare (T o1, T o2) method, which is used to compare the sizes of o1 and o2.
If you need to implement customized sorting, you need to provide a Comparator object when creating a TreeSet collection object and provide a Comparator object to associate with the TreeSet collection, and the Comparator object is responsible for the sorting logic of the collection elements.
The following program shows:
class M { int age; public M(int age) { this.age = age; } public String toString() { return "M object (age:" + age + ")"; } } public class TestTreeSet3 { public static void main(String[] args) { TreeSet ts = new TreeSet(new Comparator() { public int compare(Object o1, Object o2) { M m1 = (M) o1; M m2 = (M) o2; if (m1. age > m2.age) { return -1; } else if (m1.age == m2.age) { return 0; } else { return 1; } } }); ts.add(new M(5)); ts.add(new M(-3)); ts.add(new M(9)); System.out.println(ts); } }Program running results:
[M object (age: 9), M object (age: 5), M object (age: -3)]
illustrate:
The above program creates an anonymous internal class object of the Comparator interface, which is responsible for the sorting of the ts collection. So when we add M objects to the ts collection, there is no need for the M class to implement the Comparable interface, because at this time, TreeSet does not need to compare the size through the M objects, but the Comparator object associated with TreeSet is responsible for the sorting of the collection elements. When using custom sorting, TreeSet sorts the collection elements regardless of the size of the collection element itself, but the Comparator object is responsible for the sorting rules of the collection elements.