Research work · 2019

Hash Tables

Rod Stephens

Abstract

This chapter describes hash tables more precisely and explains ways that one can implement hash tables in a program. A hash table with chaining uses a collection of entries called buckets to hold key values. Each bucket is the top of a linked list holding the items that map to that bucket. Another strategy for building hash tables is called open addressing. In open addressing, the values are stored in an array, and some sort of calculation serves as the hashing function, mapping values into positions in the array. Different variations of open addressing use different hashing functions and collision-resolution policies. In all cases, however, the collision-resolution policy produces a sequence of locations in the array for a value. In linear probing, the collision-resolution policy adds a constant number, called the stride and usually set to 1, to each location to generate a probe sequence.

DOI: 10.1002/9781119575955.ch8