In: Computer Science
Suppose that we are using extendable hashing on a file that contains records with the following search-key values: (2, 3, 5, 7, 11, 17, 19, 23, 29, 31). Show the final extendable hash structure for this file if the hash function is h(x) = x mod 8 and buckets can hold three records. Recall that:
1. the bucket address table is indexed by the prefix of the binary representation of h(x).
2. Initially i = 0, i.e. the prefix consists of zero bits. There is only one bucket. There is one entry in the address table whose key = null (since prefix size = 0) with a pointer that points to the only bucket we have.