Q$2.$ Hashing $[20$ marks$]$

Consider a relation $s$ with one attribute $A.$ Suppose you have to insert the following

$L=\{100,123123,12345678900,1231234,11011,0,1001\}$ into the relation $s.$ Construct a

dynamic hash index on the attribute $A$ of $s$ based on extendable hashing.

$($a$)[3$ marks$]$ A simple hash function $h(x)=$ length $(str(x))\%7,$ which converts the real

number $x$ as a string, counts its length and computes the value by modulus $7.$ It maps

the real numbers in $L$ into $\{0,1,2,3,4,5,6\}.$ Show the hash values of each number in

$L.$ Please complete the form below.

$($b$)[3$ marks$]$ Since the value of $h(x)$ is less than $7,$ we can use a $3-$bit binary integer to

denote it $($i$.$e$.,$ from ${000}_2$ to ${110}_2).$ Show the binary representation of each hash value

of $L.$ Please complete the form below.

$($c$)[14$ marks$]$ In the hash index, a bucket keeps $2$ entries, where an entry is a pair of

search$-$key and pointer to the record in $s$ that has the key. Assume that the dynamic

hash index has a bucket address table and an empty bucket of $0-$bit initially as shown

in Figure $2.$ During insertions, the maximum length of the hash prefix is limited to

$3$ bits. Overflow buckets are used when necessary. Insert $L$ into the relation $s$ in

the given order, and show the dynamic hash index $($the bucket address table and the

buckets$)$ after each insertion.

Figure $2$: Initial state of the hash index.