c# - 跳过列表与字典

Question

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

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

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

哪种算法会更好，Dictionary 还是 SkipList？为什么？

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

Answer 1

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

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

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

Answer 2

Dictionary， 确实。两个原因：

• Dictionary<TKey, TValue>与跳过列表中的O(log n )相比，使用哈希表进行检索 O(1)（即常数时间） 。

• Dictionary<TKey, TValue>已经存在并且经过充分测试和优化，而据我所知不存在跳过列表类，因此您必须实现自己的，这需要努力才能正确并彻底测试。

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

Answer 3

跳过列表给出所有字典操作的平均 Log(n)。如果项目的数量是固定的，那么一个带锁的哈希表会很好。内存中的展开树也很好，因为缓存就是这个词。展开树为最近访问的项目提供更快的速度。因此在诸如查找之类的字典操作中；[跳过列表与 splay 树相比很慢，与哈希表相比又很慢。][1][1]：http ://harisankar-krishnaswamy.blogspot.in/2012/04/skip-list-runtime-on-字典.html

如果需要在数据结构中进行本地化，则跳过列表可能很有用。例如，查找某个日期附近的航班等。但是，缓存在内存中，因此展开是可以的。哈希表和展开树不提供本地化。