A fourth way of handling collisions in hash tables (after chaining, linear probing, and quadratic…
A fourth way of handling collisions in hash tables (after chaining, linear probing, and quadratic probing) is what’s called double hashing: we move forward by the same number of slots at every stage, but that number is randomly chosen, as the output of a different hash function. Specifically, to hash x into an n-slot table, first try to store x in h(x); if that cell is full, try putting x into h(x) + i · g(x), wrapping back around to the beginning of the table as usual, for i = 1, 2, . . .. (Here g is a different hash function, crucially one whose output is never zero.) See Figure 10.13.
(programming required) Modify your program from Exercises 10.46 and 10.47 to use double hashing. Again report the mean and maximum number of cells probed for x5000.
Figure 10.13: Double hashing. We try to store x in slot h(x), then h(x) + g(x), then h(x) + 2g(x), etc. (wrapping around the table as necessary)
Exercises 10.46 and 10.47
(programming required) Write a program to hash 5000 elements into a 10,007-slot hash table using linear probing. Record which cell x5000 ends up occupying—that is, how many hops from h(x5000) is x5000? Run your program 2048 times, and report how far, on average, x5000 moved from h(x5000). Also report the maximum distance that x5000 moved