What is TreeMap in Java


15.7 Sorted Collections



15.7.1 Comparable and Comparator

The and collections presented so far were unsorted, i.e. their iterators did not return the elements in any particular order. In contrast, an iterator returns the elements in the order of their index numbers. In the JDK there is now also the possibility to sort the elements of one or one. Either the natural order of the elements can be used, or the elements can be sorted using an explicit comparison object.

With the natural order, it must be ensured that all elements of the collection have a method and that any two elements can be compared with one another without causing a type error. To do this, the elements must implement the interface from the package:

has only a single method called to compare the current item with another.

  • must return a value less than 0 if the current element in front the one to be compared.
  • must return a value greater than 0 if the current element is Behind the one to be compared.
  • must return 0 if the current element and the one to be compared equal are.

The second way to sort a set of elements is to pass an object of the type to the constructor of the Collection class. is an interface that only defines a single method:

The transferred object takes on the task of a "comparison function" whose method is always called when it is necessary to determine the order in which any two elements are related to one another.

15.7.2 SortedSet and TreeSet

The interface was derived from this in order to implement sorted quantities. It adds some interesting methods to the basic interface:

Object first () Object last () SortedSet headSet (Object toElement) SortedSet subSet (Object fromElement, Object toElement) SortedSet tailSet (Object fromElement) java.util.SortedSet

With and the first or last element of the set (according to the sorting order) can be obtained. The other methods are used to construct subsets from the original set based on the sorting of the elements:

  • returns all elements that are really smaller than the element passed as an argument.
  • returns all elements that are greater than or equal to the element passed as an argument.
  • returns all elements that are greater than or equal to and less than.

In addition to the interface described here, the documentation for a number of constructors requires:

  • A parameterless constructor creates an empty set, the (future) elements of which are sorted according to their natural order.
  • A constructor with an argument of the type creates an empty set, the (future) elements of which are sorted with respect to the order given by the given order.
  • A constructor with one argument of type creates a set that contains all the unique elements of the collection passed as an argument in their natural order.
  • A constructor with an argument of the type creates a set with the same elements and the same sorting as the set passed as an argument.

The only class in the JDK that implements the interface is. It implements the sorted set using the class. This uses one Red-Black-Tree as a data structure, i.e. a tree that is protected from degenerating into a linear list in extreme cases by an imaginary red-black coloring of its nodes and special insert and delete functions. All basic operations can be carried out in logarithmic time with regard to the number of elements in the tree and are therefore quite fast even with large numbers of elements.

What is more interesting to us is the ability to generate a sorted iterator. Let's look at an example of this. The following program creates a sorted set and inserts some strings unsorted. Then the strings are output with the help of an iterator:

001 / * Listing1508.java * / 002 003 import java.util. *; 004 005 publicclass Listing 1508 006 {007 publicstaticvoid main (String [] args) 008 {009 // Construct the Set010 TreeSet s = new TreeSet (); 011 s.add ("Kiwi"); 012 s.add ("cherry"); 013 s.add ("pineapple"); 014 s.add ("lemon"); 015 s.add ("grapefruit"); 016 s.add ("banana"); 017 // Sorted output 018 Iterator it = s.iterator (); 019 while (it.hasNext ()) {020 System.out.println ((String) it.next ()); 021} 022} 023}Listing1508.java
Listing 15.8. The TreeSet Class

The output of the program is: pineapple banana grapefruit cherry kiwi lemon

The iterator has returned the elements in alphabetical order. The reason for this is that the class has implemented the interface since JDK 1.2 and provides a method with which the character strings are arranged in lexicographical order. If, on the other hand, the elements of our set are to be sorted backwards, the existing method is not suitable. Instead, an object is simply passed to the constructor whose method has been implemented in such a way that two strings to be compared are judged as ascending if and only if they are in descending order according to their lexicographical order. The following listing shows this using the example of the class:

001 / * Listing1509.java * / 002 003 import java.util. *; 004 005 publicclass Listing 1509 006 {007 publicstaticvoid main (String [] args) 008 {009 // Construct the Set010 TreeSet s = new TreeSet (new ReverseStringComparator ()); 011 s.add ("Kiwi"); 012 s.add ("cherry"); 013 s.add ("pineapple"); 014 s.add ("lemon"); 015 s.add ("grapefruit"); 016 s.add ("banana"); 017 // Backward sorted output 018 Iterator it = s.iterator (); 019 while (it.hasNext ()) {020 System.out.println ((String) it.next ()); 021} 022} 023} 024 025 class ReverseStringComparator 026 implements Comparator 027 {028 publicint compare (Object o1, Object o2) 029 {030 return ((String) o2) .compareTo ((String) o1); 031} 032}Listing1509.java
Listing 15.9: Sorting backwards with a comparator

The program now outputs the elements in reverse order: Lemon Kiwi Cherry Grapefruit Banana Pineapple

Any sorting of the elements of a can be achieved with the help of a comparator. If a is passed to the constructor, the method is no longer used at all, but the sorting takes place exclusively with the help of the method of the object. For example, elements that do not implement the interface can also be saved in one.

15.7.3 SortedMap and TreeMap

Besides an assorted one, there is also an assorted one. The interface is structured analogously to and contains the following methods:

Object first () Object last () SortedMap headMap (Object toElement) SortedMap subMap (Object fromElement, Object toElement) SortedMap tailMap (Object fromElement) java.util.SortedMap

As a concrete implementation of there is the class that works analogously. The methods and deliver collections whose iterators deliver their elements in ascending order. With one, you can either work with the natural order of the keys or force a different sort order by passing an object to the constructor.