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


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.


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.