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

Question

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

既然我不必担心插入或删除性能，那么最好使用什么数据结构(或者我应该自己动手)？我可能正在查看大约 100,000 个条目，间隔相当均匀。

我正在寻找一种最佳算法来获取这些数据。 Dictionary<>不错，但我想一定有一些针对只读数据进行了优化的东西。

我怀疑，但尚未确认这些键的范围可能是 0 - 400,000。如果是这样，建议将如何改变？ (我想我会发布一个可能的答案)。

---

也许我可以:

1. 扫描一次数据并获取最高键
2. 分配一个大小为最高键 + 1 的数组。
3. 进行第二次传递并将数据存储在数组中。

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

Answer 1

字典是正确的方法。这是来自 MSDN 的引述:

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.

因此在构建字典(计算哈希和构建树)时会花费大量时间，但通过键读取数据会非常快。

编辑

如果在 0-400k 范围内存在超过 50% 的键，那么使用一个简单的数组是有意义的，其中键是项目的索引。在最佳情况下，这会给您O(1) 复杂性。根据您的问题，只有 25% 的 key 会出现。因此，在这种情况下，我会选择 Dictionary<,>，我认为与简单数组相比，它没有 75% 的内存开销来存储每个键值对。