SkipList vs Dictionary
我最近一直在阅读Skip Lists。
我有一个Web应用程序，它对静态数据集执行非常复杂的Sql查询。
我想实现一个缓存系统，我生成sql查询的md5哈希值，然后返回查询的缓存数据集（如果它存在于集合中）。
哪种算法会更好，Dictionary还是SkipList？ 为什么？
http://msdn.microsoft.com/en-us/library/ms379573%28VS.80%29.aspx#datastructures20_4_topic4
Dictionary ，绝对。 两个原因：
-
Dictionary使用哈希表，使检索O（1）（即恒定时间）与跳过列表中的O（log n ）进行比较。 -
Dictionary已经存在且经过充分测试和优化，而我不知道跳过列表类，因此您必须实现自己的，这需要努力使其正确并彻底测试。
两者的内存消耗大致相同（当然复杂性相同，即O（ n ））。
你使用SkipList vs Dictionary是跳过列表保持其项目的顺序。 如果您经常需要按顺序枚举项目，则跳过列表很好，因为它可以在O（n）中枚举。
如果你想能够按顺序枚举但不关心枚举是否为O（n lg n），那么SortedSet （或者更可能是SortedDictionary ）将是你想要的，因为他们使用红黑树（平衡二叉树），它们已经在标准库中。
由于您不太可能希望按顺序（或根本）枚举缓存，因此不需要跳过列表（以及同样的二叉树）。
跳过列表给出了所有字典操作的平均Log（n）。 如果项目的数量是固定的，那么锁定剥离的哈希表将会很好。 内存展开树也很好，因为缓存是单词。 Splay树为最近访问的项目提供更快的速度。 因此在诸如find的字典操作中; [跳过列表与splay树相比较慢，与哈希表相比，它们再次缓慢。] [1] [1]： http ： //harisankar-krishnaswamy.blogspot.in/2012/04/skip-list-runtime-on- dictionay.html
如果需要在数据结构中进行本地化，则跳过列表可能很有用。 例如，查找日期等周围的航class。但是，缓存在内存中，因此展开是正常的。 Hashtable和splay树不提供本地化。