Java Reference
In-Depth Information
entriesissomewhatslowerthanwiththeother
Map
implementations(whicharenotsor-
ted) because links must be traversed.
Note
Check out Wikipedia's “Red-black tree” entry (
ht-
tp://en.wikipedia.org/wiki/Red-black_tree
)tolearnaboutred-black
trees.
TreeMap
supplies four constructors:
•
TreeMap()
createsanew,emptytreemapthatissortedaccordingtothenat-
ural ordering of its keys. All keys inserted into the map must implement the
Comparable
interface.
•
TreeMap(Comparator<? super K> comparator)
creates a new,
emptytreemapthatissortedaccordingtothespecified
comparator
.Passing
null
to
comparator
implies that natural ordering will be used.
•
TreeMap(Map<? extends K, ? extends V> m)
createsanewtree
mapcontaining
m
'sentries,sortedaccordingtothenaturalorderingofitskeys.
All keys inserted into the new map must implement the
Comparable
inter-
face.Thisconstructorthrows
ClassCastException
when
m
'skeysdonot
implement
Comparable
orarenotmutuallycomparable,and
NullPoint-
erException
when
m
contains the null reference.
•
TreeMap(SortedMap<K, ? extends V> sm)
createsanewtreemap
containingthesameentriesandusingthesameorderingas
sm
.(Idiscusssorted
maps later in this chapter.) This constructor throws
NullPointerExcep-
tion
when
sm
contains the null reference.
Listing 5-18
demonstrates a tree map.
Listing 5-18.
Sorting a map's entries according to the natural ordering of their
String
-based
keys
import java.util.Map;
import java.util.TreeMap;
class TreeMapDemo
{
public static void main(String[] args)
{
Map<String, Integer> msi = new TreeMap<>();