ChainedHashTable: Hashing with Chaining

Hash tables overview

Hash tables are an efficient method of storing a small number, n, of integers from a large range $U = \{0,...,2^{w}− 1\}$. The term hash table includes a broad range of data structures. This lesson focuses on two of the most common implementations of hash tables:

• Hashing with chaining
• Linear probing

Very often, hash tables store types of data that are not integers. In this case, an integer hash code is associated with each data item and is used in the hash table. There are various ways of how such hash codes are generated.

Some of the methods used for hashing require random choices of integers in some specific range. In the code samples, some of these random integers are hard-coded constants. These constants were obtained using random bits generated from atmospheric noise.

The ChainedHashTable structure

A ChainedHashTable data structure uses hashing with chaining to store data as an array, t, of lists. An integer, n, keeps track of the total number of items in all lists. See the below figure: