5. Hash Tables

Hash tables are an efficient method of storing a small number, $\ensuremath{\ensuremath{\mathit{n}}}$, of integers from a large range $U=\{0,\ldots,2^{\ensuremath{\ensuremath{\ensuremath{\mathit{w}}}}}-1\}$. The term hash table includes a broad range of data structures. The first part of this chapter focuses on two of the most common implementations of hash tables: hashing with chaining and 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. The second part of this chapter discusses how such hash codes are generated.

Some of the methods used in this chapter 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.