1. Suppose you are given the following keys: 115, 2545, 995, 505 and the following hash...

 

Transcribed Image Text:

1. Suppose you are given the following keys: 115, 2545, 995, 505 and the following hash function h(x) = x mod 10. Hash the keys using the hash function. How many keys collide? Choose a random hash function, hR from H10007,10. Include your random choice of hR 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, h, 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? 1. Suppose you are given the following keys: 115, 2545, 995, 505 and the following hash function h(x) = x mod 10. Hash the keys using the hash function. How many keys collide? Choose a random hash function, hR from H10007,10. Include your random choice of hR 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, h, 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?