Question

Problem 7 Given the following keys 16, 27, 52, 38, 10. 67. 56, 32, 4, 71.33, 15. Assume address is calculated by K% 17 l. (6%) Calculate the home addresses of the given keys: (4%)Show the contents of the hash table, using progressive overflow"?lysM) collisions where M 17 2. to resolve 0 10 12 13 6 14 16 (2%) Assuming that every key has the same probability number of accesses to look for a key in the table you built in 2. 3. to be searched for, calculate the average (4%) Show the contents of the hash table, using double hashing (G+c)%M) to resolve collisions where c7 and M-17: 4. 0 10 13 14 15 16 (2%) Assuming that every key has the same probability to be searched for, calculate the aver number of accesses to look for a key in the table you built in 4. 5,

Answer 1

"Home address of given keys (k%17) keys are: 16, 27, 52, 38, 10, 67, 56, 32, 4, 71, 33, 15 home keys are: rightarrow 16% 17 = 16 rightarrow 4% 17 = 4 rightarrow 27% 17 = 10 rightarrow 71% 17 = 3 rightarrow 52 % 17 = 1 rightarrow 33% 17 = 16 rightarrow 38% 17 = 4 rightarrow 10% 17 = 10 rightarrow 15% 17 = 15 rightarrow 67 % 17 = 16 rightarrow 56% 17 = 5 rightarrow 32% 17 = 15 in progressive overflow method, if its home address is free, then we place the key in that address if it is not free then we try the nex position untill finds a free one, the next position of last one is the first position it is called ""wrap around"" 0 67 1 52 2 33 3 71 4 38 5 56 6 4 7 15 8 9 10 27 11 10 12 13 14 15 32 16 16"