| Chapter 7. Hash Tables | ||
|---|---|---|
 | Part I. C Programming |  |
| Chapter 7. Hash Tables | ||
|---|---|---|
| | Part I. C Programming | |
Table of Contents
The hash tables are data structures used to store a high number of data and execute search and insert operations efficiently. A hash table stores a set of pairs “(key, value)”. The key is unique for each element in the table and is used when searching for a specific value.
A dictionary is an example of structure that can be implemented with a Hash table. For each pair, the key is the word to search, and the value contains its meaning. The use of this data structure is so common when developing applications, that are basic data types in some languages.
Let us suppose an application that must manipulate a very
large number of pairs (key, value). These pairs are created on
demand by the application, they are manipulated and destroyed. The
manipulation consists mainly on searching if the application already
contains a given pair (key, value), and if not, it is added to
the table.
For example, there is an application in a mobile phone that uses the camera to detect a passport number. For each passport, and additional comment is stored. The application must implement the following operations:
Create an empty passport table.
Given a passport number, search if it is in the table.
Given a passport number and a remark, store this pair
(key, value) in the table. It is assumed that there is no
previous information about this passport number in the table.
| |  | |
| 6.12.4. Word Set Management |  | 7.2. Possible Implementations |