SkipList<T>和Dictionary<TKey, TValue>的比较

Question

最近我一直在阅读关于跳表的内容。

我有一个 Web 应用程序，它针对静态数据集执行非常复杂的 SQL 查询。

我想实现一个缓存系统，通过生成 SQL 查询的 MD5 哈希值，并在集合中存在该查询的情况下返回查询的缓存数据集。

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

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

- WOPR

---

顺便提一下，我感觉有必要提到memcached。 - Jim Brissom

建议使用memcached并没有什么帮助，如果没有一种在.NET中使用它的方法。http://sourceforge.net/projects/memcacheddotnet/ - Ben Voigt

每次我看到 <T> vs <S, T>，我都觉得这个比较是有缺陷的。就像苹果和橙子一样不可比较。 - nawfal

Answer 1

使用 SkipList<T> 相比于 Dictionary<TKey,TValue> 的原因在于跳表会保持其项的顺序。如果您需要定期按顺序枚举项，则使用跳表很好，因为它可以在 O(n) 时间内枚举。

如果您想按顺序枚举但不关心枚举的时间复杂度是否为 O(n lg n)，则应使用 SortedSet<T>（或更可能是SortedDictionary<TKey, TValue>），因为它们使用红黑树（平衡二叉树）并且已经在标准库中。

由于极不可能需要按顺序（或根本不需要）枚举缓存，因此不需要使用跳表（或同样地使用二叉树）。

- Gabe

---

根据研究来源，一个正确实现的SkipList通常可以比RBTree表现更好，更不用说SkipList所需的资源远远少于RBTree。我想看一下SkipList和SortedDictionary之间的比较... - IAbstract

dboarman：你有这方面的研究吗？如果有，或许你可以在http://stackoverflow.com/questions/4118109/hashtable-and-list-side-by-side上发表一下评论。 - Gabe

Answer 2

Dictionary，毫无疑问。原因如下：

• Dictionary<TKey, TValue>使用哈希表，使得检索时间为O(1)（即常数时间），而跳表的检索时间为O(log n)。

• Dictionary<TKey, TValue>已经存在并且经过了充分的测试和优化，而我所知道的跳表类并不存在，因此您需要自己实现它，这需要花费精力来确保正确性并彻底测试它。

两者的内存消耗大致相同（确切地说是相同的复杂度，即O(n)）。

- Timwi

Answer 3

Skip List在所有字典操作中平均需要Log（n）的时间。如果项目数量固定，则锁定散列表将表现良好。由于缓存是关键，内存中的Splay Tree也很好。 Splay Trees可以更快地访问最近访问的项。因此，在词典操作中，[跳过列表相对于Splay Tree而言速度较慢，后者相对于hash table而言速度又较慢。][1][1]: http://harisankar-krishnaswamy.blogspot.in/2012/04/skip-list-runtime-on-dictionay.html

如果需要数据结构本地化，则跳过列表可能有用。例如，查找某个日期周围的航班等。但是，缓存位于内存中，因此splay也可以。Hashtable和splay tree不提供本地化。

- Harisankar Krishna Swamy