Overview of Hash Tables

A hash table is a data structure that supports very fast element insertion, removal, and retrieval. A hash table that is properly configured for the elements it contains can support these operations in a fixed amount of time. This is unlike any other data structures and algorithms that we have examined.

A hash table is a type of map. Maps are associative structures. Conceptually, associative data structures store data in key-value pairs. This means that for every value stored there is a corresponding key used to access the value. A real world example of an associative data structure is a dictionary. In a dictionary, data is stored in key-value pairs. The keys are the words, and the values are the definitions. To access a definition, one must use the corresponding key.

Hash maps and hash sets are two different types of hash tables. Hash maps are associative structures that store key-value pairs, whereas hash sets are structures that keep track of the membership of items within a collection. Hash sets do not map keys to values. They merely store a collection of keys. A list of commonly misspelled words, for instance, could be stored using a hash set. In this example, there is no mapping of a key to a value like there was in the dictionary example. Each word serves as only a key. A hash set is then used to report whether or not a word exists in this list of words.