只读字典访问最高效存储器内数据结构 [英] Most efficient in-memory data structure for read-only dictionary access

问题描述

在C＃中，我有可能被放在一个词典<一些静态数据，INT，T> ，其中 T 一定的参考类型。 Web应用程序只需要一次初始化，静态（不改变）。

In C#, I have some static data that could be put in a Dictionary<int, T> where T is some reference type. The web app only needs to initialize it once, statically (it doesn't change).

由于我不必担心插入或删除性能，是什么最佳的数据结构来使用（或者我应该推出自己的）？我可能在寻找的东西就好〜10万项，相当均匀分布的。

Since I don't have to worried about insert or delete performance, what is the best data structure to use (or should I roll my own)? I'm probably looking at something like ~100,000 entries, fairly evenly spaced.

我要寻找一个最佳的算法获取这个数据。 词典<> 不坏，但我想一定有什么东西为只读数据在那里进行了优化

I am looking for an optimal algorithm for fetching this data. Dictionary<> isn't bad, but I would imagine there must be something out there optimized for read-only data.

我怀疑，但还没有证实这些键的范围可能是0 - 40.0万。如果是这样的话，怎么会建议改变？ （我有一个思想，我将发布作为一个可能的答案）

I suspect, but haven't confirmed that the range of these keys might be 0 - 400,000. If that was the case, how would the recommendations change? (I have a thought that I will post as a possible answer).

也许我可以：

1. 通过数据扫描一次，并抓住最关键


2. 分配一个数组的最高键+ 1的大小


3. 取第二遍并将数据存储在阵列中。

这会是好还是比一个哈希表/字典糟糕了合理的负载因数？

Would this be better or worse than a HashTable / Dictionary with a reasonable load factor?

推荐答案

Dicrionary是正确的道路要走，这里是报价从 MSDN ：

Dicrionary is the right way to go, here is quote from MSDN:

词典（TKEY的，TValue）泛型类提供了从
A组按键映射到一组值。每次加入到词典
由一个值和其相关联的密钥的。检索利用其关键
的值是非常快的，接近O（1），因为字典（
TKEY的中，TValue）类作为哈希表来实现。

The Dictionary(Of TKey, TValue) generic class provides a mapping from a set of keys to a set of values. Each addition to the dictionary consists of a value and its associated key. Retrieving a value by using its key is very fast, close to O(1), because the Dictionary(Of TKey, TValue) class is implemented as a hash table.

因此将需要大量的时间，同时建立词典（计算哈希和建筑树），但将暴风雪快读你通过关键数据。

So it will take a lot of time while building dictionary (calculating hashes and building tree), but will be blizzard fast to read your data by key.

修改

在情况下，你将有超过50个％目前钥匙从范围0-400k是有意义的去用简单的arrray，其中重点是项目索引。这会给你的 O（1）的复杂性。
但是，根据你的问题只有25％的钥匙将出席。所以，我会去的字典在这种情况下，我不认为它有记忆75％的开销存储每个键值对比较简单的数组。

In case you will have more than 50% keys present from range 0-400k it makes sense to go with simple arrray, where key would be item index. This will give you O(1) complexity. But according to you question only 25% of keys would be present. So I would go with dictionary in this case, I don't think that it has 75% overhead of memory to store each key-value pair comparing to simple array.

这篇关于只读字典访问最高效存储器内数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！