0
$\begingroup$

I am reading the research paper "Split-Ordered Lists: Lock-Free Extensible Hash Tables" by Nir Shavit and Ori Shalev.

https://dl.acm.org/doi/10.1145/1147954.1147958

I was just wandering if anyone is familiar with the algorithm. I have two questions that I can't get my head around.

  1. In the code presented on the paper, I did not see a place where buckets array (T[]) is doubled. Am I missing something? We could create a new array, copy over the items and replace it with a compare and swap, but would it make the add method not constant time?

  2. What if we get a duplicate hash value? And what if we get two hash values only different by their most significant bit?

Appreciate any help. Thanks.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.