SkipList <T> vs Dictionary <TKey,TValue>

Question

我最近一直在阅读关于Skip Lists的文章.

我有一个Web应用程序,它对静态数据集执行非常复杂的Sql查询.

我想实现一个缓存系统,我生成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， 确实。两个原因：

\n\n

\n

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

\n

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

\n

\n\n

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

\n