Question

Which of the following is true about a good hash function?

• A. It always produces the same hash value for different keys.
• B. It distributes keys uniformly across the hash table.
• C. It always results in hash collisions.
• D. It requires storing all keys in contiguous memory locations.

Hint:

A perfect hash function (one with zero collisions) is rarely possible in practice. Thus, a "good" function focuses on "Simple Uniform Hashing," where any given key is equally likely to hash into any of the $m$ slots.

Answer 1

The Correct Option is B

Concept: Hashing is a technique used to map data of arbitrary size to fixed-size values. A "Good" hash function is critical for the performance of Hash Tables.
• Efficiency: Should be fast to compute ($O(1)$).
• Determinism: Same input must always produce the same output.
• Uniformity: Inputs should be spread evenly across the table to minimize clusters.

Step 1: Analyzing "Uniform Distribution".
The primary goal is to utilize the available table slots effectively. If many keys map to the same slot, performance degrades from $O(1)$ to $O(n)$.

Step 2: Addressing the concept of collisions.
Option (A) describes a "Constant" hash function, which is terrible. Option (C) says it "always" results in collisions; a good function aims to minimize them.

Step 3: Distinguishing from storage requirements.
Hashing is about the "mapping" logic, not the physical memory layout. The table itself might be an array, but the hash function does not "require" contiguous keys.