3 ms·
Okay, but which is slower, hashing a string and then looking into an array indexed at that position (possibly traversing a very short (2- or 3-item) list), or p
by BrandonM 18y ago
Okay, but which is slower, hashing a string and then looking into an array indexed at that position (possibly traversing a very short (2- or 3-item) list), or performing an average of 17 string comparisons (for the case of ~130,000 items)?
In particular, the hashing approach gives similar lookup times for any item. The skiplist approach is dependent on the (random) structure of the built-up skiplist. A given item could be found after 2 pointer traversals, or it could take 30. Also disturbing is that as you get closer to the item you're looking for, the string comparisons take longer and longer (because the common prefixes are getting longer and longer).
With a good hashing algorithm, similar strings will hash to different values. This means that even if 2 or 3 string comparisons have to be made (for strings that land in the same bucket), failing comparisons will be fast since they will likely fail on the first character.
- silentbicycle 18y agoThe 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.
- johnm 18y agoJoe Bob says: check out Radix/Crit-Bit/Patricia Trees http://en.wikipedia.org/wiki/Radix_tree http://en.wikipedia.org/wiki/Radix_tree