Hashing

In Previous Chapter, we discussed the search tree ADT, which allowed various operations on a set of elements. In this chapter, we discuss the hash table ADT, which supports only a subset of the operations allowed by binary search trees.

The implementation of hash tables is frequently called hashing. Hashing is a technique used for performing insertions, deletions and finds in constant average time. Tree operations that require any ordering information among the elements are not supported efficiently. Thus, operations such as find_min, find_max, and the printing of the entire table in sorted order in linear time are not supported.

• The central data structure in this chapter is the hash table. We will See several methods of implementing the hash table.

• Compare these methods analytically.

• Show numerous applications of hashing.

• Compare hash tables with binary search trees.