A hash file uses the division function to calculate the bucket number from the given key value. The file was set with 11 buckets numbered 0 to 10, where each bucket can contain at most 3 records. Analyse what happens when records with the following keys are inserted into the hash file. Explain what went wrong and suggest a solution.
15 27 44 79 30 26 38
5 35 9 16 45 57 18
Check the attachment for the table correctly displayed.
As written, the hashing algorithm described above is limiting and simplistic. It is not surprising that it took only 14 records to fill up one of the buckets in the hash table. The primary limiting factor is that only 3 records can be contained in each bucket.
The division function for hash tables divides the data value by the number of buckets, and the *remainder* is used for the bucket number. In mathematical terms, this is called "modulo arithmetic," commonly used in programming languages with the word "mod" or the percent symbol (%). 25 mod 10 would equal 5, since 25/10 = 2 with a remainder of 5. For the hash algorithm described above, the bucket number from 0 to 10 would be determined by the remainder after the data element is divided by 11.
For example, the first data element is 15. 15 mod 11 = 4, since 15 / 11 = 1 with a remainder of 4.
With that in mind, here is the hash buckets chosen as the data is entered. It is assumed that the data is entered in the order specified above.
15 mod 11 = 4 thus 15 goes in bucket 4, which now contains 1 record (15).
27 mod 11 = 5 thus 27 goes in bucket 5, which now contains 1 record (27).
44 mod 11 = 0 thus 44 goes in ...
The expert examines hash division function numbers.