As for a fix, the hopscotch algorithm is modified to use 31 as H (instead of 32). So there will
be 31 neighbor buckets instead of 32 buckets. The highbit (bit 31) is set whenever we end up with
a situation where all neighbor buckets are full when we try to add a key to the mlk_shrhash table.
If we find the highbit set, we do a linear search of the entire hash buckets array instead
of just the 31 neighbor buckets to check if a key exists or not. A similar logic is used for
deletion of an entry from the mlk_shrhash table too.
This modified hopscotch algorithm handles the bucket-full situation (a very rare scenario) with a
slower linear search. It still continues to use the much faster hash algorithm for all hash buckets where
there is less than 31 collisions (the most common case). But this removes the hangs and
lock-ownership-seizes that can happen in rare cases with the previous implementation.
See description at https://github.com/YottaDB/YottaDB/issues/297 for background on issue.
As for a fix, the hopscotch algorithm is modified to use 31 as H (instead of 32). So there will be 31 neighbor buckets instead of 32 buckets. The highbit (bit 31) is set whenever we end up with a situation where all neighbor buckets are full when we try to add a key to the mlk_shrhash table.
If we find the highbit set, we do a linear search of the entire hash buckets array instead of just the 31 neighbor buckets to check if a key exists or not. A similar logic is used for deletion of an entry from the mlk_shrhash table too.
This modified hopscotch algorithm handles the bucket-full situation (a very rare scenario) with a slower linear search. It still continues to use the much faster hash algorithm for all hash buckets where there is less than 31 collisions (the most common case). But this removes the hangs and lock-ownership-seizes that can happen in rare cases with the previous implementation.