Assume that you are sorting n keys in a hash table. You are using the dot produc
ID: 3593683 • 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. Wil 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
Every key in K that shares a common factor with the number of buckets m will be hashed to a bucket that is a multiple of this factor. Therefore, to minimize collisions, it is important to reduce the number of common factors between m and the elements of K. Hence, we choose prime numbered m's. If this isn't the case then we get collusions, reducing efficiency, but hashing is still valid.
The ai's can be selected in such a way that the dot product of them is a prime. This will reduce the number of collisions.
----------------
Thank you.