SkipList 与 Dictionary

我最近一直在阅读有关跳过列表的内容。

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

我想实现一个缓存系统，生成 sql 查询的 md5 哈希值，然后返回查询的缓存数据集（如果集合中存在该数据集）。

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

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

你会使用的原因SkipList<T> vs Dictionary<TKey,TValue>是跳跃列表保持其项目的顺序。如果您经常需要按顺序枚举项目，那么跳跃列表会很好，因为它可以在 O(n) 内进行枚举。

如果您希望能够按顺序枚举但不关心枚举是否为 O(n lg n)，则SortedSet<T> https://msdn.microsoft.com/en-us/library/dd412070(v=vs.110).aspx（或者更有可能的是SortedDictionary<TKey, TValue> https://msdn.microsoft.com/en-us/library/f7fta44c(v=vs.110).aspx）将是您想要的，因为它们使用红黑树（平衡二叉树）并且它们已经在标准库中。

由于您不太可能希望按顺序（或根本）枚举缓存，因此不需要跳过列表（以及同样的二叉树）。