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

Q1:
Table sizes must be a power of two and the keys must have a binary representation in order for the bit-reversal to work out.

Q2:
In order to grow a split-ordered list, dummy nodes are inserted, splitting the older bucket's chains of elements. These dummy nodes are never deleted and without doing so we could not shrink the list.

Bonus:
No...

Q1: 1. log(n) operations performed on a machine with finite memory can be considered constant.
2. The number of retries (loops) in the underlying lock-free linked list will be bounded by some constant.

Q2:

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.

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.

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.

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 constant extendibility rate, meaning that the table is never extended (doubled in size) a non-constant number of times while a thread is delayed by the scheduler.

Q2. As this is an extensible hash table, "resizing" means extending the table. It is interesting to note, as argued elsewhere [Hsu and Yang 1986; Lea (e-mail communication 2005)], that many of the standard concurrent applications using hash tables require tables to only increase in size.
According to constant extendibility rate assumption, if shrinking is allowed there would be no constant number of steps or constant time for any single operation.

Q1:
The hash function has a uniform distribution.

Q2:
short: It's not implemented.
long: It is not really necessary. The only thing the user of the datastructure would get is:
+ some memory (dummy nodes)
+ lower runtime (shrinking)
+ slightly larger code size

Q1:
The hash function should distribute the keys uniformly over the buckets, and there should not be arbitrarily many splits of buckets due to insertions.

Q2:
It can be done, but not really necessary. To have any practical impact, shrinking should delete the dummy nodes. The only benefit of such an action would be the reclaimed memory.

Q1:
The hash function should have a uniform distribution, otherwise all elements will end up in too few (or the same) bucket/s.

Q2:
Split-ordered lists are grown by splitting buckets. Elements start in the same bucket, and as the list grows, they gradually move to different buckets. Shrinking a list would require merging buckets, which is not supported by the current algorithm.