'Probabilistic' doesn't have to mean 'nondeterministic'. Hash tables are deterministic and probabilistic. You could probably do the same with a skip list: hash the key to see what level of the skip list it gets promoted to.