SkipList<T> vs Dictionary<TKey，TValue>

Question

我最近一直在读关于跳过列表的文章。

我有一个web应用程序，可以对静态数据集执行相当复杂的Sql查询。

我想实现一个缓存系统，通过该系统生成md5查询的SQL哈希，然后返回该查询的缓存数据集(如果该数据集存在于集合中)。

字典和SkipList，哪种算法更好？为什么？

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

Answer 1

当然是Dictionary。有两个原因：

• Dictionary<TKey, TValue>使用哈希表，使得检索O(1) (即恒定时间)，与跳过列表中的O( list.
• Dictionary<TKey, TValue> n)相比已经存在，并且经过了良好的测试和优化，而据我所知，跳过列表类并不存在，因此您必须实现自己的类，这需要努力使其正确并对其进行彻底测试。

两者的内存消耗大致相同(当然是相同的复杂度，即O(n))。

Answer 2

您使用SkipList<T>与Dictionary<TKey,TValue>的原因是跳过列表保持其项目的顺序。如果您经常需要按顺序枚举项目，则跳过列表是很好的选择，因为它可以按O(n)进行枚举。

如果您希望能够按顺序枚举，但不关心枚举是否为O(n lg n)，那么SortedSet (或者更有可能是SortedDictionary )将是您想要的，因为它们使用红黑树(平衡二叉树)，并且它们已经在标准库中。

由于您不太可能想要按顺序(或根本不)枚举缓存，因此跳过列表(以及同样的二叉树)是不必要的。

Answer 3

跳过列表给出了所有字典操作的平均值Log(n)。如果项目的数量是固定的，那么一个锁剥离的哈希表将会做得很好。内存中的展开树也很好，因为cache就是单词。展开树可以更快地显示最近访问的项目。因此，在查找等字典操作中，跳过列表比展开树慢，而展开树又比哈希表慢。1：http://harisankar-krishnaswamy.blogspot.in/2012/04/skip-list-runtime-on-dictionay.html

如果需要在数据结构中进行本地化，那么跳过列表可能会很有用。例如，查找日期附近的航班等。但是，缓存在内存中，所以splay就可以了。Hashtable和splay树不提供本地化。