用于只读字典访问的最有效的内存数据结构

Question

在C#中,我有可能被放入一些静态的数据Dictionary<int, T>,其中T一些引用类型.Web应用程序只需要静态初始化一次(它不会更改).

由于我不必担心插入或删除性能,使用什么是最好的数据结构(或者我应该自己动手)？我可能会看到大约100,000个条目,间隔相当均匀.

我正在寻找一种获取这些数据的最佳算法.Dictionary<>虽然不错,但我认为必须有针对只读数据优化的东西.

我怀疑,但尚未确认这些密钥的范围可能是0 - 400,000.如果是这样的话,建议会如何变化？(我想我会发布一个可能的答案).

也许我可以:

这会比具有合理负载系数的HashTable/Dictionary更好还是更差？

Answer 1

Dicrionary是正确的方法,这里引用MSDN:

Dictionary(Of TKey,TValue)泛型类提供从一组键到一组值的映射.字典的每个添加都包含一个值及其关联的键.通过使用其键来检索值非常快,接近于O(1),因为Dictionary(Of TKey,TValue)类被实现为哈希表.

因此,在构建字典(计算哈希值和构建树)时需要花费大量时间,但是通过密钥读取数据会很快暴风雪.

编辑

如果您在0-400k范围内有超过50%的密钥,那么使用简单的arrray是有意义的,其中key是项目索引.这将给你O(1)复杂性.但根据你的问题,只有25%的钥匙会出现.所以在这种情况下我会使用字典,我认为与简单数组相比,它存储75%的内存开销来存储每个键值对.