Hashing - Practice MCQs for CCAT

Correct Answer: B - O(1)

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

Correct Answer: D - Two keys map to same index

Collision occurs when different keys produce the same hash index.

Correct Answer: C - Checking next slot sequentially

Linear probing checks next consecutive slots until empty slot found.

Correct Answer: A - Linked lists at each index

Chaining stores multiple elements at same index using linked list.

Correct Answer: B - n/m

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

Correct Answer: D - Distribute keys uniformly

Good hash function distributes keys uniformly to minimize collisions.

Correct Answer: C - O(n)

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

Correct Answer: D - 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: A - 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: A - Load factor exceeds threshold

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

Correct Answer: D - Prime number

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

Correct Answer: A - 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: D - O(1) worst case lookup

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

Correct Answer: A - Tombstone/Deleted

Tombstone markers allow probe sequences to continue past deleted elements.

Correct Answer: C - 7

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

Correct Answer: C - 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.

Correct Answer: B - To map keys to indices in a hash table

A hash function maps keys to indices (hash values) in a hash table, enabling fast data retrieval in approximately O(1) time.

Correct Answer: B - When two different keys map to the same hash value

A collision occurs when two different keys produce the same hash value, mapping to the same index in the hash table.

Correct Answer: D - Chaining

Chaining (separate chaining) resolves collisions by maintaining a linked list at each hash table index to store all keys that hash to that index.

Correct Answer: C - Searching the next available slot sequentially

Linear probing resolves collisions by checking the next slot (index + 1, index + 2, ...) sequentially until an empty slot is found.

Correct Answer: B - Primary clustering

Linear probing suffers from primary clustering, where consecutive occupied slots form clusters, degrading performance as search time increases.

Correct Answer: C - Checking slots at intervals of 1², 2², 3², ...

Quadratic probing checks slots at positions h(k)+1², h(k)+2², h(k)+3², etc., reducing primary clustering compared to linear probing.

Correct Answer: D - Two hash functions

Double hashing uses a second hash function to determine the step size for probing, providing a more uniform distribution and reducing clustering.

Correct Answer: A - Number of elements / table size

The load factor α = n/m where n is the number of elements stored and m is the size of the hash table. It measures how full the table is.

Correct Answer: A - O(1)

With a good hash function and low load factor, hash table operations (search, insert, delete) achieve O(1) average-case time complexity.

Correct Answer: B - Division method

The division method computes hash as h(k) = k mod m, where m is the table size. It's simple and commonly used.

Correct Answer: B - A pointer to a linked list

In separate chaining, each slot contains a pointer to a linked list (or chain) that stores all elements hashing to that index.

Correct Answer: D - When the load factor exceeds a threshold

Rehashing is typically done when the load factor exceeds a threshold (e.g., 0.75), to maintain O(1) average-case performance.

Correct Answer: A - Creating a larger table and reinserting all elements

Rehashing involves creating a new, larger hash table and reinserting all existing elements using the hash function with the new table size.

Correct Answer: D - Distribute keys uniformly across the table

A good hash function should distribute keys uniformly across the hash table to minimize collisions and achieve O(1) average performance.

Correct Answer: A - h(k) = ⌊m(kA mod 1)⌋ where 0 < A < 1

The multiplication method computes h(k) = ⌊m(kA mod 1)⌋ where A is a constant between 0 and 1. Knuth suggests A ≈ (√5 - 1)/2.

Correct Answer: A - Double hashing

Double hashing virtually eliminates clustering because the probe sequence depends on two independent hash functions, producing a more uniform distribution.

Correct Answer: B - O(n)

In the worst case, all n elements hash to the same index, creating a single linked list of length n, making search O(n).

Correct Answer: C - A prime number

A prime number is preferred for m in the division method as it distributes keys more uniformly and avoids patterns caused by powers of 2.

Correct Answer: C - A function with no collisions for a given set of keys

A perfect hash function maps each key in a specific set to a distinct hash value with no collisions. It's achievable when the key set is known in advance.

Correct Answer: A - No more elements can be inserted

In open addressing, when the table is full, no more elements can be inserted since all slots are occupied. Rehashing is needed to accommodate more elements.

Correct Answer: B - Separate chaining

Separate chaining is NOT an open addressing technique. It uses linked lists at each slot, while open addressing stores all elements within the table itself.

Correct Answer: C - Squaring the key and extracting middle digits

The mid-square method squares the key and then extracts the middle digits of the result to use as the hash value.

Correct Answer: C - (1/α) × ln(1/(1-α))

For uniform hashing with open addressing, the expected number of probes for a successful search is approximately (1/α) × ln(1/(1-α)).

Correct Answer: A - Two hash functions and two tables

Cuckoo hashing uses two hash functions and two tables. Each key has two possible positions, and collisions are resolved by displacing existing keys.

Correct Answer: D - All of the above

Hashing is widely used in database indexing, compiler symbol tables, caching mechanisms, and many other applications requiring fast lookups.

Correct Answer: C - n/m

The average chain length in separate chaining equals the load factor n/m, which represents the average number of keys per slot.

Correct Answer: D - Dividing the key into parts and combining them

The folding method divides the key into equal-sized parts (except possibly the last) and combines them (usually by addition) to get the hash value.

Correct Answer: A - When keys with the same initial hash follow the same probe sequence

Secondary clustering occurs when keys that hash to the same initial position follow the same probe sequence. Quadratic probing suffers from this.

Correct Answer: B - Mark the slot as deleted (lazy deletion)

In open addressing, we use lazy deletion (marking as deleted) rather than simply removing, because removing would break the probe sequence for other elements.

Correct Answer: B - The probability of collision for any two keys is at most 1/m

A universal hash function family guarantees that for any two distinct keys, the probability of collision is at most 1/m, where m is the table size.