Hashing and Sets

Hash tables are containers that represent a collection of objects inserted at computed index locations. Each object inserted in the hash table is associated with a hash index. The process of hashing involves the computation of an integer index (the hash index) for a given object (such as a string). If designed properly, the hash computation (1) should be fast, and (2) when done repeatedly for a set of keys to be inserted in a hash table should produce hash indices uniformly distributed across the range of index values for the hash table. The term “hashing” is derived from the observation that there should be little if any obvious association between the object being inserted and its hash index. Two closely related objects such as the strings “time” and “lime” should generally produce unrelated hash indices. Thus hashing involves distributing objects into what appears to be random (but reproducible) locations in the table. When two distinct objects produce the same hash index, we refer to this as a collision . Clearly the two objects cannot be placed at the same index location in the table. A collision resolution algorithm must be designed to place the second object at a location distinct from the first when their hash indices are identical. The two fundamental problems associated with the construction of hash tables are: the design of an efficient hash function that distributes the index values of inserted objects uniformly across the table […]