Solve the sorting problem of TreeSet class

TreeSet supports two sorts: natural sort and custom sort. TreeSet USES natural sort by default.

1. Natural sorting

TreeSet calls the compareTo(Object obj) method of the collection elements to compare the size relationships between the elements, and then arranges the collection elements in ascending order, which is natural sort. The premise of comparison: the two objects have the same type.

Java provides a Comparable interface that defines a compareTo (Object obj) method that returns an integer value that must be implemented by the class that implements the interface so that the Object of the class that implements the interface can be compared. When an object calls this method to compare with another object, such as obj1.comparTo(obj2), if the method returns 0, the two objects are equal. If a positive integer is returned, obj1 is greater than obj2. If the method returns a negative integer, obj1 is less than obj2.

The Java common class implements the Comparable interface and provides a standard for comparing sizes. Common classes that implement the Comparable interface:

BigDecimal, BigIneger, and all numeric counterpart wrapper classes: compare by the size of their numeric counterparts. Character: compares characters by their UNICODE value. Boolean: true corresponds to a wrapper class instance that is greater than false. String: compares characters in a String by their UNICODE values. Date, Date, Date, Date, Date, Date, Date, Date, Date, Date, Date

If you try to add an object to TreeSet, the object's class must implement the Comparable interface.

The following program will report an error:

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(new Err()); 
ts.add(new Err()); 
} 
} 

Description:

The program above tried to add two Err objects to the TreeSet collection. When the first object was added, there were no elements in TreeSet, so there was no problem. When a second Err Object is added, TreeSet calls the compareTo(Object obj) method of that Object to compare with the other elements in the collection -- a ClassCastException is thrown if the corresponding class does not implement the Comparable interface. And when you try to fetch the first element from TreeSet, you still throw a ClassCastException.

When comparing objects using the compareTo(Object obj) method, both objects need to be cast to the same type because only two instances of the same class can compare sizes. That is, objects of the same class should be added to TreeSet, otherwise a ClassCastException will be thrown. For example, when you add a string object to TreeSet, this is perfectly normal. When a second Date Object is added, the TreeSet calls the compareTo(Object obj) method of that Object to compare it with other elements in the collection, and the program throws an exception.

In real 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 without casting the compareTo(Object obj) method. But the ClassCastExceptio exception still occurs for different types of elements when working with the collection data in TreeSet. (read carefully and you will understand)

When an Object is added to a TreeSet collection, the TreeSet calls the Object's compareTo(Object obj) method to compare its size with other objects in the container, and then decides where to store it based on the red-black tree algorithm. If two objects are compared equal through compareTo(Object obj), TreeSet considers them to store the same location.

For TreeSet collections, the criteria for determining that two objects are not equal are: two objects return false by comparing equals, or no 0 by compareTo (Object obj) -- even if two objects are the same, TreeSet treats them as two objects.

The following procedure is shown:

//Class Z, which overrides the equals method, always returns false,
//Overrides the compareTo(Object obj) method, always returning a 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 
{ 
public static void main(String[] args) 
{ 
TreeSet set = new TreeSet(); 
Z z1 = new Z(6); 
set.add(z1); 
System.out.println(set.add(z1)); 
//When you print the set set, you will see that there are two elements
System.out.println(set); 
//Modify the age attribute for the first element of the set collection
((Z)(set.first())).age = 9; 
//Output the age attribute of the last element in the set set, and you'll see that it also becomes 9
System.out.println(((Z)(set.last())).age); 
} 
} 

  Program running results:

True,
[TreeSet. Z @ 1 fb8ee3 TreeSet. Z @ 1 fb8ee3]
9
Description:

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. This way the TreeSet will think that the z1 object is different from itself, so two z1 objects are added to the TreeSet. The TreeSet object holds two elements that are actually the same. So when you modify the age attribute of the first element in the TreeSet set, the age attribute of the last element in the TreeSet set changes as well.

conclusion : when you need to put an Object into TreeSet, when you override the equals() method of the corresponding class of the Object, you should ensure that the method has the same result as the compareTo(Object obj) method. The rule is that if two objects return true by equals, the two objects should return 0 by compareTo(Object obj) method.

If two objects return true by equals, but the two objects do not return 0 by compareTo(Object obj), this causes TreeSet to save the two objects in different locations so that both objects can be added successfully, which is somewhat different from the Set Set rules.

If two objects through the compareTo (Object obj) method compare the returns 0, but they will be more trouble by comparing with the equals method returns false, because the two objects through compareTo (Object obj) method to compare equal, TreeSet will attempt to save them in the same place, but in fact no (or only one Object), so to handle more troublesome.

If a mutable Object is added to the TreeSet, behind and program to modify the attributes of the Object the variable, causing it to change the size of the Object with the other order, but the TreeSet will not adjust their order again, and may even cause the TreeSet kept in these two objects, they through comparing the equals method returns true, compareTo (Object obj) method returns 0.

The following procedure is shown:

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, whose elements are ordered
System.out.println(hs); 
//Take 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 you'll see that the elements in the TreeSet are out of order
System.out.println(hs); 
hs.remove(new R(-3)); 
System.out.println(hs); 
//Output is false
System.out.println("hs Does it include count for -3 the R Objects? " + hs.contains(new R(-3))); 
//Output is false
System.out.println("hs Does it include count for 5 the R Objects? " + hs.contains(new R(5))); 
 
} 
} 
 

Program running results:

[R (count property: - 3), R (count property: - 2), R (count property: 5), R (count property: 9)]
[R (count property: 20), R (count property: - 2), R (count property: 5), R (count property: - 2)]
[R (count property: 20), R (count property: - 2), R (count property: 5), R (count property: - 2)]
[R(count attribute :20), R(count attribute :-2), R(count attribute :-2)]
Description:

The R object in the program above is a class that normally overrides the equals and comparable methods, both of which rely on the count attribute of the R object. You can see that the first output of the program is ordered. When the count attribute of the R object is changed, the output of the program also changes and contains duplicate elements. Once the attributes of a mutable element in the TreeSet collection are changed, when the view deletes the object, the TreeSet will also fail to delete (even if the original attributes of the collection are not modified, but the elements equal to the modified elements cannot be deleted), so the count is removed

When R object is -2, no element is deleted; The program can delete R objects with count of 5, which indicates that TreeSet can delete objects that are not modified and do not duplicate with other objects with modified properties.

Summary: hashsets are very complex and error-prone when dealing with these objects. To make the program more robust, it is recommended that only immutable objects be placed in the HashSet and TreeSet collections.

2. Customized sorting

The natural ordering of TreeSet is based on the size of the collection elements, and TreeSet orders them in ascending order. If you need to implement custom sorting, such as descending, you can use the Comparator interface. This interface contains an int compare (T o1, T o2) method that compares the sizes of o1 and o2.

If you need to implement custom sorting, when you create a TreeSet collection object, you need to provide a Comparator object associated with the TreeSet collection, which takes care of the sorting logic for the collection elements.

The following procedure is shown:

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)]
Description:

An anonymous internal class object of the Comparator interface is created in the program above, which is responsible for sorting the ts collection. So when we add M objects to the ts collection, we don't need the M class to implement the Comparable interface, because TreeSet doesn't need to compare sizes by M objects, but instead the Comparator object associated with TreeSet takes care of sorting the collection elements. With custom sorting, TreeSet sorts collection elements regardless of the size of the collection elements themselves, but the Comparator object is responsible for sorting the collection elements.