This chapter presents the binary search tree, which is an efficient implementation of the
Map interface that is particularly useful if we want to keep the elements sorted.
At this point you should be familiar with the
Map interface and the
HashMap implementation provided by Java. And by making your own
Map using a hash table, you should understand how
HashMap works and why we expect its core methods to be constant time.
Because of this performance,
HashMap is widely used, but it is not the only implementation of
Map. There are a few reasons you might want another implementation:
Hashing can be slow, so even though
HashMap operations are constant time, the “constant” might be big.
Hashing works well if the hash function distributes the keys evenly among the sub-maps. But designing good hash functions is not easy, and if too many keys end up in the same sub-map, the performance of the
HashMap may be poor.
The keys in a hash table are not stored in any particular order; in fact, the order might change when the table grows and the keys are rehashed. For some applications, it is necessary, or at least useful, to keep the keys in order.
It is hard to solve all of these problems at the same time, but Java provides an implementation called
TreeMap that comes close:
It doesn’t use a hash function, so it avoids the cost of hashing and the difficulty of choosing a hash function.
TreeMap, the keys are are stored in a binary search tree ...