1. Given the following key values, show what the data structures would look like after insertions 25 44 126 91 53 150 544 525 481 123 621 735 566 223 66 (no preprocessing necessary: pk = key)
a. Linear array of 19 elements using division hashing and the linear-quotient collision path algorithm N = 19, 4k+3 prime = 23
LQHashing:
1. ip = pk % N
2. q=pk/N
if (q%N != 0)
offset = q
else
offset = 4k+3 prime
3. While collisions:
ip’ = (ip + offset) % N
4. Set Array[ip]=key
b. Bucket hashing of 10 elements (N=10) ip = (pk) % N
2. Fill in the table based on exercise 1
Number of comparisons to retrieve this element
Key, Lineary array - (Length of Collision Path + 1), Buckets - (# of elements in linked list compared)
25
44
481
735
566
66