Question

Select the correct option for the following multiple choice questions or provide short answers accordingly: 1. Consider a hash table with chaining, of size N. Assume in each of the following scenarios the table starts empty. Further assume K pairs of <key, element> are added and K N Then, in which of the following situations will a find operation for a particular key have a potential worst-case runtime of O(N) a) The keys of all elements are powers of two and the hash function returns a unique index for each key mod N b) The hash function returns a fixed number mod N, but the keys of all elements inserted are uniquee c) Although the hashing function computes a good distribution of key values into the hash table indices, the hash function returns only even numbers. d) The find operation in this problem is never near O(N) 2. You have a hash table of size N = 65. You have total 10,000 elements to insert into the table (e.g., N << 10,000). The keys are all unique and are all 64 bit positive integers. You have to find a suitable hash function h(k) for key k'. Which of the following hash functions will NOT work with the given parameters? a) h(k)-k mod N b) h(k)- (number of bits of k which are '1') mod N c) h(k)=11082 (k) d) h(k) - [ loga (k') J

Explain each answer.

Answer 1

1. b. The hash function returns a fixed number mod N, but the keys of all elements inserted are unique.

Explanation:

a). If hash function returns a unique index then all elements will be stored in unique blocks corresponding to that index value.

• for example: if N=5  elements have keys 2, 4, 8, 16.(keys value in powers of 2 as given in question).
• 2 will be stored at block no.2 mod 5=2
• 4 will be stored at block no. 4 mod 5=4
• 2 will be stored at block no. 8 mod 5=3
• 2 will be stored at block no. 16 mod 5=1
• so if you want to find key element 16 ,just compute 16 mod 5=1 and go to block no 1 and get key element 16.
• so searching here will be done in O(1) time. it is actually the best case. so this option is wrong.

b). consider N=4 and elements have key values as 2,6,10,14.

• 2 will be stored at 2 mod 4=2
• 6 will be stored at 6 mod 4=2
• 10 will be stored at 10 mod 4=2
• 14 will be stored at 14 mod 4=2 .so all have to be stored at block no.0. so they would be stored as shown in following image.
• 
  1 y 0 hauyh table
  
• so if you have to search for key element 14 you have to do 14 mod 4 which is 2 then at block no 2 ,you have to traverse entire linked list. this is worst case scenario. here time complexity is O(n). so this option is correct.

c). hash function can return odd numbers too. for example if N=4 and key element have key value 3 then 3 mod 4=3 which is odd and this means this element will be stored at block no. 3 in hash table. so option is not correct.

d). In worst case find operation will take o(n) time when all key mapped to same block number. so wrong option.

Question 2. d).
(log )
would not work for all values. for example if k=2⁶⁴ then
( log | ( 264 )2 | ) = (log | 2128 | ) 128
and hash table size is 65 that is block index would be from 0-64 .so there is no block which have index number 128.so it can't be mapped to any of block. so (d) option is correct.

a) k mod N will work for all element because whenever you divide a number with 65 remainder will be in range of 0-64.

b). In 64 bit integers number of bits which is 1 will be in range of 0-64.

c).in worst case k=2⁶⁴ which will mapped to block no.=. so here index also range between 0-64. so this hash function will also work.

(log |(264)) 64