Java Reference
In-Depth Information
699
Chapter 16 Advanced Data Structures
C
HAPTER
G
OALS
ȗ To learn about the set and map data types
ȗ To understand the implementation of hash tables
ȗ To be able to program hash functions
ȗ To learn about binary trees
ȗ To be able to use tree sets and tree maps
ȗ To become familiar with the heap data structure
ȗ To learn how to implement the priority queue data type
ȗ To understand how to use heaps for sorting
In this chapter we study data structures that are more complex than arrays or lists.
These data structures take control of organizing their elements, rather than keeping
them in a fixed position. In return, they can offer better performance for adding,
removing, and finding elements.
You will learn about the abstract set and map data types and the implementations
that the standard library offers for these abstract types. You will see how two
completely different implementationsȌhash tables and treesȌcan be used to
implement these abstract types efficiently.
699
700
16.1 Sets
In the preceding chapter you encountered two important data structures: arrays and
lists. Both have one characteristic in common: These data structures keep the
elements in the same order in which you inserted them. However, in many
applications, you don't really care about the order of the elements in a collection. For
example, a server may keep a collection of objects representing available printers (see
Figure 1
). The order of the objects doesn't really matter.
