Question

Consider a hash function hashing a key K to a table of n buckets (indexed from 0 to n - 1). Which of these would be acceptable hash functions -- meaning that they would work correctly for both insertions and searches? Assume the function Random(n) returns an integer between 0 and n - 1, inclusive. (Select all that apply).

Group of answer choices

1. h(K) = k mod n

2. h(K) = Random(n)

3. h(K) = n

4. h(K) = (k + Random(n)) mod n

Answer 1

Answer:
---------
1. h(K) = k mod n
3. h(K) = n

Explanation:
--------------
1. h(K) = k mod n
    This is a very good hash function used everywhere
2. h(K) = Random(n)
    hash of a key can/should not be random.
3. h(K) = n
    This is a bad hash function.
    but still we can use this as a hash function for insert/search using chaining method for collision resolution.
4. h(K) = (k + Random(n)) mod n
    hash of a key can/should not be random.