1. Suppose you are given the following keys: 115, 2545, 995, 505 and the followi
ID: 3756744 • Letter: 1
Question
1. Suppose you are given the following keys: 115, 2545, 995, 505 and the following hash function h(x)- mod 10. Hash the keys using the hash function. How many keys collide? Choose a random hash function, h from H10007,10. Include your random choice of h with your answer to this problem. Before you rehash the numbers with the new hash function, determine the probability that the keys 115 and 2545 collide when hashed with hR? Hash each of the keys 115,2545,995,5025 with hR. How many keys collided? If you had 1000 keys (all keys were positive integers less than 10000) inserted into a hash table of size 2000 using a hash function, hR, randomly choosen from H10007,2000 (the family of universal hash functions we defined in class). What is the expected number of collisions you would have if you inserted a new key, x, into the hash table?Explanation / Answer
for h(x) = x mod 10
the keys will be hashed as:
115 -> 5
2545 -> 5
995 -> 5
505 -> 5
all the keys will collide.
As the reference to the family of hash function H10007,10and H10007,2000 is not given in the question, the complete answer can not be given. Though it is suggested that to get a probability of same collision, one has to look for the numbers in the list that will land on the same remainder for the given key values. The number that will leave same remained out of the total count will form the collision probability. (A simple program can be written in any basic language say C/C++ or MATLAB to find it out, if you wish to)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.