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)).