Hashing — Practice MCQs for CCAT

Correct Answer: A — O(1)

Hash table provides O(1) average case for insert, delete, search.

Correct Answer: B — Two keys map to same index

Collision occurs when different keys produce the same hash index.

Correct Answer: B — Checking next slot sequentially

Linear probing checks next consecutive slots until empty slot found.

Correct Answer: B — Linked lists at each index

Chaining stores multiple elements at same index using linked list.

Correct Answer: A — n/m

Load factor = n/m where n is elements and m is table size.

Correct Answer: B — Distribute keys uniformly

Good hash function distributes keys uniformly to minimize collisions.

Correct Answer: B — O(n)

Worst case (all keys collide) is O(n).

Correct Answer: B — Two hash functions

Double hashing uses two hash functions to calculate probe sequence.

Correct Answer: D — Sorting

Sorting is not a collision resolution technique.

Correct Answer: B — Linear probing

Linear probing suffers from primary clustering where consecutive slots fill up.

Correct Answer: C — Quadratic probing

Quadratic probing suffers from secondary clustering where keys with same hash follow same probe sequence.

Correct Answer: B — Load factor exceeds threshold

Rehashing creates a larger table when load factor becomes too high to maintain efficiency.

Correct Answer: B — Prime number

Prime number table sizes help distribute keys more uniformly and reduce collisions.

Correct Answer: B — Adversarial attacks

Universal hashing randomly selects hash function to prevent adversarial worst-case inputs.

Correct Answer: B — Two hash functions and tables

Cuckoo hashing uses two hash functions and moves elements between positions on collision.

Correct Answer: B — O(1) worst case lookup

Perfect hashing provides O(1) worst-case lookup with no collisions for static sets.

Correct Answer: B — Tombstone/Deleted

Tombstone markers allow probe sequences to continue past deleted elements.

Correct Answer: B — 7

47 mod 10 = 7, so the key 47 maps to index 7.

Correct Answer: B — Load factor can exceed 1

With chaining, load factor can exceed 1 as multiple elements can be at same index.

Correct Answer: B — Probabilistic membership testing

Bloom filter is a space-efficient probabilistic structure for membership testing with possible false positives.