Question: 8. This question tries to clarify why every hash function could be beaten by bad data. (a) Let U be a set of 100 keys,

8. This question tries to clarify why every hash function could be beaten by bad data. (a) Let U be a set of 100 keys, and h be a hash function that maps each key to an integer between 0 and 9. Show that you can find a subset K CU of 10 keys in U such that h(x) = h(y) for every pair T, YE K. That is, h maps all keys of K to the same index. (b) Generalize the previous question, but now U is a set of m keys and h maps each key to an integer between 0 and m - 1
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
