0 0 1 Hạshing Lab 1. Given the following key values, show what the data structures would look like after insertions 27 53 13 10 138 109 49 174 26 24 (no preprocessing necessary: pk=key) a. Linear array of 10 elements using division hashing b. Bucket hashing of 10 elements (N=10) and the linear-quotient collision path algorithm ip = (px) %N N= 13, 4k+3 prime = 19 Array: Array: LOHashing: 1. ip = pk %N 1 2 2. q=pk/N 3 3 if (q%N !=0) offset = 9 5 5 else offset = 4k+3 prime 7 7 3. While collisions: 8 ip’ = (ip + offset) %N 9 4. Set Array[ip]=key 10 11 12 2 4 4 6 6

2. Fill in the table based on exercise 1 Number of comparisons to retrieve this element Key Linear array – (Length of Collision Path +1) Buckets – (# of elements in linked list compared) 53 138 109 49 174 26