Think Data Structures

Chapter 12. TreeMap

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.

What’s Wrong with Hashing?

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 ...