The next data structure we consider is the hash table. A hash table is a data structure for the storage of records. It provides a means for rapid searching for a record with a given key value and adapts well to the insertion and deletion of records. Many compilers, for example, use hash tables to implement their symbol tables. They are also used extensively in systems where the primary objective is information retrieval. Thus nametable of Chapter 6 or a dictionary of words might be implemented in a hash table.
To illustrate the need for hash tables, suppose we want to store 1,000 records representing 1,000 customer accounts. Assume that each record has an account number as its key and, since we control account numbers, they range from 1 to 1,000. The solution is simple. Store the record with key value i in element i of an array data. Then, given a key value to search for (say, 836), go directly to element 836 of data to find it. What could be a quicker search? We are given a record and know immediately where to go to find it. The search time is a constant, independent of the number of records stored. However, this kind of search requires the ability to assign key values so that all keys are within a range of array indices (1 to 1,000 in this case). It also requires that we have enough storage to accommodate all records.
Now suppose we are dealing with records representing information about our employees, and that the keys are social security numbers. Even with only 1,000 employees, there are 109 possible social security numbers. It is not possible to know in advance which of the 109 social security numbers our 1,000 employees will actually have. If we were to allocate storage using social security numbers as addresses, we would run into two problems. First, there would not be enough storage. Second, if we did have sufficient storage, 999,999,000 (109 - 103) storage elements would be wasted! Nonetheless, it is extremely attractive to be able to look at the search key value and to know where to find it. This is the goal of hash tables and hash searching?/FONT>to find a record directly, given its key value.
9.3.4 Other Collision Resolution Policies: Open Addressing and Chaining
9.3.5 Searching in Ordered Hash Tables
9.3.6 Deletion from Hash Tables