Suppose we want to implement a concurrent hash table that uses open addressing to resolve collisions. Recall the following:

Open addressing checks the array index at the hash function and if it is not available, moves ahead according to some rule until it finds an empty spot in the array.
Recall also that two commonly used rules for finding the empty array slot are:

Linear probing: First check the hashed index i and if it is occupied, then move to index i+1 modulo the size of the array and so on recursively until an open spot is found.
Quadratic probing: First check the hashed index i and if it is occupied, then move to index i^2 modulo the size of the array and so on recursively until an open spot is found.

Linear probing makes it easy to implement a search, but increases clustering, whereas quadratic probing increases the difficulty of implementing a search, but reduces clustering.

With all of this in mind, which of the following approaches to implementing the concurrent hash table do you expect will perform best in terms of turnaround time?

Question

Suppose we want to implement a concurrent hash table that uses open addressing to resolve collisions. Recall the following: 
 
 Open addressing checks the array index at the hash function and if it is not available, moves ahead according to some rule until it finds an empty spot in the array. 
 Recall also that two commonly used rules for finding the empty array slot are:
 
 Linear probing: First check the hashed index i and if it is occupied, then move to index i+1 modulo the size of the array and so on recursively until an open spot is found. 
 Quadratic probing: First check the hashed index i and if it is occupied, then move to index i^2 modulo the size of the array and so on recursively until an open spot is found.

Linear probing makes it easy to implement a search, but increases clustering, whereas quadratic probing increases the difficulty of implementing a search, but reduces clustering. 
 
 With all of this in mind, which of the following approaches to implementing the concurrent hash table do you expect will perform best in terms of turnaround time?

Accepted Answer

Using multiple locks, one for each of a fixed number of array slots (say 10), and quadratic probing.

Answer

Using a single global lock for the array, and linear probing.

Answer

Using a single global lock for the array, and quadratic probing.

Answer

Using multiple locks, one for each of a fixed number of array slots (say 10), and linear probing.

Answer

Using one lock per each slot in the array, and linear probing.

Answer

Using one lock per each slot in the array, and quadratic probing.

Crowdly

Suppose we want to implement a concurrent hash table that uses open addressing t...

Want instant access to all verified answers on moodle31.upei.ca?