# Split-Ordered Lists: Lock-Free Extensible Hash Tables (J. ACM 53, 3 (May 2006), 379-405)

Ori Shalev (Tel Aviv University) and Nir Shavit (Tel Aviv University and Sun Microsystems Laboratories)

Description
If you want another description of this algorithm see "The Art of Multiprocessor Programming" by Maurice Herlihy and Nir Shavit, pages 309 to 316. |

## Questions

**Question 1:**

What assumption(s) has/have to be made so that operations on split-ordered lists work in constant time?

**Question 2:**

Why is it possible to extend split-ordered lists, but not possible to shrink them back to their original size after use?

**Bonus Question:**

Did you read the correctness proof section?

Magnus
Q1: Q2: Bonus: |
Jonatan
Q1: 1. log(n) operations performed on a machine with finite memory can be considered constant. Q2: |

Martin
Q1: The hash table is actually hierarchical, but assuming a 64-bit machine it is enough with a 4-level "hirarchy" to exhaust the memory, so the depth of this hierarchy is seen as bounded, and the access time as constant. Q2: They do not provide any way to shrink them, but I can't find any proof that it would be impossible. |
Pan
Q1: The hash function provides a uniform distribution. Q2: When the table extends, the elements originally in the same bucket may be separated to different buckets. In order to shrink the hashtable, we'll need to merge some of the buckets, which is not trivial. |

Kjell
Q1: 1. The hash values of the keys need to be uniformly distributed. The worst case is that all elements are placed in the same bucket and all the other buckets are empty. The complexity of the operations will then be proportional to the size of the set instead of constant. 2. The operations are never starved by operations performed by other threads (the number of retries is constant). Q2: It might be possible to extend the described algorithm to support decreasing the size of the bucket array and removing sentinel nodes. The price that one would need to pay for such an extension is that the algorithm becomes more complicated and less performant for cases when decreasing the size of the bucket array is not needed. |
Afshin
Q1. Making the standard assumption of a hash function with a uniform distribution, then under any scheduling adversary the new algorithm provides a lock-free extensible hash table with O(1) average cost per operation. The complexity improves to expected constant time if we assume a Q2. |

Andreas
Q1: Q2: |
Stavros
Q1: Q2: |

Sofia
Q1: Q2: |