Assume that you are sorting n keys in a hash table. You are using the dot produc
ID: 3593540 • Letter: A
Question
Assume that you are sorting n keys in a hash table. You are using the dot product for computing the hash values, while, taking into account that functions are picked from a universal family of hash functions. However, the size m of the hash table is not a prime. Will you still be able to retrieve your data? That is, will the issue be only with efficiency, or could it be that some of operations might fail in any reasonable time period Suggest 'reasonable' critiria for choosing the coefficients ai in the dot product hash func- tion, so performences are good. This is a bit an open ended question. There are no keys that always works perfectly However, you could definitely see 'asking for troubles' even before the first data item showed up.Explanation / Answer
In dot product method,Let m be prime,
we decompose k into r+1 digits,each with the value in the set {0,1,...m-1},that is let k={k0 ,k1,....km-1 }where 0<=ki <m
pick a={a0,a1,a2....am-1} where each ai is choosen randomly from {0,1...m-1}
define ha (k)= i=0r ai ki mod m
To reduce the number of collisions, it is important to reduce the number of common factors between m and k,
This can be achieved by making m as a prime number,hence chosing m to have less common factors is important.
If m is noprime,we will still be to retrieve data but because of collisions the effect overall run time.The operations of lookups and delete fail over reasonable time period.