A Textbook of Data Structures and Algorithms, Volume 3

13Hash Tables

13.1. Introduction

The data structures of binary search trees, AVL trees, B trees, tries, red-black trees and splay trees discussed so far in the book (Volume 2) are tree-based data structures. These are nonlinear data structures and serve to capture the hierarchical relationship that exists between the elements forming the data structure. However, there are applications that deal with linear or tabular forms of data, devoid of any superior-subordinate relationship. In such cases, employing these data structures would be superfluous. Hash tables are one among such data structures which favor efficient storage and retrieval of data elements that are linear in nature.

13.1.1. Dictionaries

Dictionary is a collection of data elements uniquely identified by a field called a key. A dictionary supports the operations of search, insert and delete. The ADT of a dictionary is defined as a set of elements with distinct keys supporting the operations of search, insert, delete and create (which creates an empty dictionary). While most dictionaries deal with distinct keyed elements, it is not uncommon to find applications calling for dictionaries with duplicate or repeated keys. In this case, it is essential that the dictionary evolves rules to resolve the ambiguity that may arise while searching for or deleting data elements with duplicate keys.

A dictionary supports both sequential and random access. Sequential access is one in which the data elements of the dictionary are ...