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.

Inside the

`TreeMap`

, the keys are are stored in a**binary search tree ...**

Start Free Trial

No credit card required