Test on Hash Tables: Concepts, Operations, and Performance

Question 1: In a perfect hashing scheme, searching takes constant time in the worst case.

A. Yes

B. No

Explanation: Perfect hashing is defined as a technique where O(1) memory accesses are required to perform a search in the worst case. This means searching takes constant time in the worst case because no collisions occur in any of the secondary hash tables.

Question 2: In a hash table with 'n' slots, where 'n' keys are inserted and collisions are resolved by chaining, what is the expected upper bound for 'M', the maximum number of keys in any single slot, assuming each key is equally likely to be hashed to any slot?

A. O(n)

B. O(log n)

C. O(lg n / lg lg n)

D. O(1)

Explanation: Problem 11-2, "Slot-size bound for chaining," specifically asks to prove an O(lg n / lg lg n) upper bound on E[M], where M is the maximum number of keys in any slot under the described conditions.

Question 3: In the multiplication method for hashing, the value of 'm' is typically chosen as a power of 2 to facilitate easy implementation on most computers.

A. Yes

B. No

Explanation: The study materials state: "An advantage of the multiplication method is that the value of m is not critical. We typically choose it to be a power of 2 ( m D 2 p for some integer p ), since we can then easily implement the function on most computers as follows."

Question 4: Which of the following statements accurately describe properties or implications of a universal collection of hash functions, as defined in the study materials?

A. For any pair of distinct keys, the probability of a collision is at most 1/m when a hash function is chosen randomly from the collection.

B. It guarantees that no single input will always evoke worst-case behavior, even against a malicious adversary choosing keys.

C. The expected length of the list containing a key k (if k is in the table, using chaining) is at most 1 + the load factor α.

D. The expectations for list lengths (E[n_h(k)]) depend on assumptions about the distribution of the keys.

Explanation: Option 0 is correct: The study materials state that for a universal collection, 'with a hash function randomly chosen from H, the chance of a collision between distinct keys k and l is no more than the chance 1/m'. Option 1 is correct: The text explains that 'randomization guarantees that no single input will always evoke worst-case behavior' and that universal hashing 'can yield provably good performance on average, no matter which keys the adversary chooses'. Option 2 is correct: Theorem 11.3 explicitly states, 'If key k is in the table, then the expected length E[n_h(k)] of the list containing key k is at most 1 + α'. Option 3 is incorrect: The proof of Theorem 11.3 explicitly notes that 'The expectations here are over the choice of the hash function and do not depend on any assumptions about the distribution of the keys'.

Question 5: The expected number of probes in an unsuccessful search in an open-address hash table is at most 1/(1 - α) for any load factor α, even when deletions are performed using the DELETED special value.

A. Yes

B. No

Explanation: The study materials state that 'When we use the special value DELETED, however, search times no longer depend on the load factor α'. Therefore, the theorem regarding the expected number of probes being at most 1/(1 - α) (which depends on the load factor) does not hold true under those conditions.