Chapter 8


This chapter discusses dictionaries and their representations in various methods such as linear list representation, skip list representation and hash table representation. In this chapter the reasons and situations of collision occurrences and techniques to overcome the collisions are explained. Comparisons of chaining and open addressing, applications and ADT of dictionary are also explained in detail.


Dictionary contains data elements as pairs of the form (k, v), where k is the key and v is the value. The field key must be unique and is used to identify the data elements uniquely. No two pairs are allowed to have the same key.

A dictionary with duplicates is a dictionary which allows two or more (key, ...

Get Data Structures and Algorithms Using C++ now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.