SkipList< T> VS字典< TKEY的，TValue> [英] SkipList<T> vs Dictionary<TKey,TValue>

问题描述

我最近一直念叨跳表。

我有执行防静电的数据集相当复杂的SQL查询的Web应用程序。

I have a web application that executes quite complex Sql queries against static datasets.

我想实现一个缓存系统，使我产生SQL查询的MD5哈希值，然后返回缓存的数据集查询，如果它存在于集合中。

I want to implement a caching system whereby I generate an md5 hash of the sql query and then return a cached dataset for the query if it exists in the collection.

哪些算法会更好，字典或SkipList？为什么呢？

Which algorithm would be better, Dictionary or a SkipList? Why?

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

推荐答案

词典，绝对。有两个原因：

Dictionary, definitely. Two reasons:

• 词典< TKEY的，TValue> 使用哈希表，使得检索O（1）（即固定时间），相比O（日志的 N 的）在跳跃列表。

• Dictionary<TKey, TValue> uses a hash table, making retrieval O(1) (i.e. constant time), compared to O(log n) in a skip list.

词典< TKEY的，TValue> 已经存在，并且是经过严格测试和优化，而跳跃列表类不存在我的知识，这样你会实现你自己的，它需要努力得到它的权利，并对其进行全面测试。

Dictionary<TKey, TValue> already exists and is well-tested and optimised, whereas a skip list class doesn’t exist to my knowledge, so you would have to implement your own, which takes effort to get it right and test it thoroughly.

内存消耗大约是上是相同的（当然同样的复杂性，即O（ N 的））。

Memory consumption is about the same for both (certainly the same complexity, namely O(n)).

这篇关于SkipList< T> VS字典< TKEY的，TValue>的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！