Hash tables - Data Structures and Problem Solving Using Java - page 773

chapter 20

hash tables

I n Chapter 19 we discussed the binary search tree, which allows various
operations on a set of elements. In this chapter we discuss the hash table,
which supports only a subset of the operations allowed by binary search trees.
The implementation of hash tables is frequently called hashing, and it per-
forms insertions, deletions, and finds in constant average time.
Unlike with the binary search tree, the average-case running time of hash
table operations is based on statistical properties rather than the expectation of
random-looking input. This improvement is obtained at the expense of a loss
of ordering information among the elements: Operations such as findMin and
findMax and the printing of an entire table in sorted order in linear time are not
supported. Consequently, the hash table and binary search tree have some-
what different uses and performance properties.
In this chapter, we show

Several methods of implementing the hash table

n

Analytical comparisons of these methods

n

Some applications of hashing

n

Comparisons of hash tables and binary search trees

n