3. Dictionaries

A dictionary is a container of elements from a totally ordered universe that supports the basic operations of inserting/deleting elements and searching for a given element. In this chapter, we present hash tables which provide an efficient implicit realization of a dictionary. Efficient explicit implementations include binary search trees and balanced search trees. These are treated in detail in Chapter 4. First, we introduce the abstract data type Set which includes dictionaries, priority queues, etc. as subclasses.