Question

If every item of the list maps to a unique index in the hash table, the hash function is called a ______ hash function.

• A. perfect
• B. remainder
• C. collision
• D. aggregate

Hint:

A "Perfect Hash Function" guarantees $O(1)$ constant time lookup in the worst case because there are no collisions to resolve!

Answer 1

The Correct Option is A

Step 1: Understanding the Question:
The question asks for the specific name of a hash function that maps every distinct input key to a unique slot or index in a hash table without any overlapping.

Step 2: Key Hashing Concepts:
- Hash Function: A function that maps keys of arbitrary size to fixed-size array indices.
- Collision: An event that occurs when two different keys map to the exact same hash table index.
- Perfect Hash Function: A hash function that maps each key in a static set of keys to a distinct integer, ensuring that no collisions occur.

Step 3: Detailed Explanation:
- In general hashing, we often experience collisions because the key space is much larger than the slot space of the hash table. We then use collision resolution techniques (like chaining or open addressing) to handle them.
- However, if we know the set of keys beforehand, we can design a specialized hash function such that:
\[ H(key_1) \neq H(key_2) \quad \text{for all } key_1 \neq key_2 \]
- Such a hash function guarantees that each item maps to its own unique index, resulting in zero collisions. This is called a Perfect Hash Function.
- Let us evaluate the other options:
- Remainder: This refers to the modulo division method (e.g., $key \pmod m$), which is a common way to implement a hash function but does not guarantee unique mappings.
- Collision: This is the event of key conflict, not a type of function.
- Aggregate: This is unrelated and refers to summarizing multiple values in database queries.

Step 4: Final Answer:
A hash function that maps each input item to a unique index is called a perfect hash function.
Hence, option (A) is the correct choice.