Question

Assume that you are hashing key K to a hash table of n slots (indexed from 0 to n - 1). For each of the following functions h(K), answer the following question(s):

1) Is the function acceptable as a hash function (i.e., would the has program work correctly for both insertions and searches),

2) and if so, is it a good hash function?

Function rand(n) returns a random integer between 0 and n - 1. Also assume k is a an integer values that is >> (potentially much larger than) n.

(a) h(k) = k / n where k and n are integers, k >> n

(b) h(k) = 1

(c) h(k) = (k + rand(n)) mod n

(d) h(k) = k mod n where n is a prime number and k is an integer k >> n

Answer 1

So First we will talk about first function:

1) H(k)=k/n This function can be used as a Hash function But there will be some collisions as for a group of n numbers key will be same. So we have to use Linear Searching in that case if collision occurs. Eg. if n=10 then 0-9,will be in key 0, 10-19 will be in key1 and so on. So for the given case as k>>n it is a good hashing function because for searching O(n) complexity will be required and as n is small less time will be taken.

2) H(k)=1 It is also acceptable but is a very bad hashing function as all the elements will be present under the same key and searching requires K searches which is O(K) time complexity which is very high and It is equivalent to Linear Searching. Collisions occurs at a high rate.

3)H(k) = (k + rand(n)) % n : It is not acceptable as a hashing function as Key cant be calculated Or more clearly if we calculate the key using this function many times different key will be generated and hence searching becomes impossible in this case.

4)H(k) = k mod n where n is a prime number and k is an integer k >> n : It is acceptable as a hashing function and is a best one among all the above functions as It reduces the number of collisions in the hashing table and is very fast in searching the element in the hashing table.

If it was any help to you then Please UPVOTE my answer

And Feel free to ask any doubts in the comment section..