SkipList<T> vs Dictionary<TKey,TValue>

Question

I've been reading about Skip Lists lately.

I have a web application that executes quite complex Sql queries against static datasets.

I want to implement a caching system whereby I generate an md5 hash of the sql query and then return a cached dataset for the query if it exists in the collection.

Which algorithm would be better, Dictionary or a SkipList? Why?

http://msdn.microsoft.com/en-us/library/ms379573%28VS.80%29.aspx#datastructures20_4_topic4

Answer 1

Dictionary, definitely. Two reasons:

• Dictionary<TKey, TValue> uses a hash table, making retrieval O(1) (i.e. constant time), compared to O(log n) in a skip list.

• Dictionary<TKey, TValue> already exists and is well-tested and optimised, whereas a skip list class doesn’t exist to my knowledge, so you would have to implement your own, which takes effort to get it right and test it thoroughly.

Memory consumption is about the same for both (certainly the same complexity, namely O(n)).

Answer 2

+1 to Timwi, but I'll also add that it won't make any practical difference in speed for your particular scenario for two reasons. Firstly because the cost of cache misses (which involve DB access) will dwarf any time for cache hits. Secondly because you won't have enough keys in the cache for any difference in performance to be felt, even if you almost never get a cache miss.

Answer 3

The reason you would use a SkipList<T> vs Dictionary<TKey,TValue> is that a skip list keeps its items in order. If you regularly need to enumerate the items in order, a skip list is good because it can enumerate in O(n).

If you wanted to be able to enumerate in order but didn't care if enumeration is O(n lg n), a SortedSet<T> (or more likely a SortedDictionary<TKey, TValue>) would be what you'd want because they use red-black trees (balanced binary trees) and they are already in the standard library.

Since it's extremely unlikely that you will want to enumerate your cache in order (or at all), a skip list (and likewise a binary tree) is unnecessary.

Answer 4

Dictionary will give you fast access rather than Skip list.

A skip list can be thought of a Binary Search Tree which is having O(log n) searching for a node if your tree is balanced otherwise it will be O(n) searching time.

But in case of Disctionary if no Collision occures i.e. the ideal scenarion you can search in constant time. If Collison occurs than your key will be chained like a LinkList.

And Collision avoidence can be minimized (not removed) by choosing a valid hash function so if your hash function is smart enough that it can avoid collision in 90% of cases than your dictionary will be very fast.

while in case of skip list , you need to maintain list like a Balanced Binary Search Tree.