The lookup would remain O(1) fast, which will overtake O(log N) skiplist lookup, true. The insertion and other costs differ between the two as well, though. A h

The lookup would remain O(1) fast, which will overtake O(log N) skiplist lookup, true. The insertion and other costs differ between the two as well, though. A hash table would be clearly best in a case where the approx. final table size needed is known ahead of time, most data is inserted upfront, and characteristics of the data are known (for tuning the hashing function). Also, good point about string comparisons getting longer among close nodes. Personally, I think skiplists are most interesting because they rely on randomness to make the underlying structure efficient. I wonder what over data structures that could apply to.