So I read a bit about skip lists and am currently implementing one. But there is one thing I didn't really got so far. Why are skip lists randomized? In all sources I found skip list used a random number to decide at what level the item will be inserted. Couldn't the optimum be calculated? Or couldn't you just say "every fourth item" should be inserted at the level above?
1 Answer
Skip lists can be constructed deterministically, for instance to minimize the amortized access cost. However, for any deterministic construction method the set of higher-level list entries is always known, so it's easy to construct a "hostile" set of delete operations that will degenerate performance back to O(n). With randomized construction there's still a set of worst-case deletes, but for any sizable list the likelihood of finding that worst-case delete sequence by sheer chance is vanishingly small.
4 Comments
Nick
I know this is old question, but what about instead of random to have a counter. Then use first bits of the counter as if these were random. and in the beginning, we can initialize this counter with some random value, in order counter values to be "unpredictable".
pjs
@Nick I don't see that this changes the substance of my answer. Using a counter is a completely predictable approach, and it only takes one observation to probe the counter's starting value. Perhaps I'm misunderstanding what you're proposing? If so, why not write it up as a separate question?
Lem
Sooo we using randomization ONLY to prevent Denial-of-service?
pjs
@Lem I wouldn’t say that. We use randomization because it works well AND shuts down an otherwise easy attack vector.