在 C# 中,我有一些静态数据可以放在 Dictionary<int, T>
中其中 T
是一些引用类型。 Web 应用程序只需静态初始化一次(它不会更改)。
既然我不必担心插入或删除性能,那么最好使用什么数据结构(或者我应该自己动手)?我可能正在查看大约 100,000 个条目,间隔相当均匀。
我正在寻找一种最佳算法来获取这些数据。 Dictionary<>
不错,但我想一定有一些针对只读数据进行了优化的东西。
我怀疑,但尚未确认这些键的范围可能是 0 - 400,000。如果是这样,建议将如何改变? (我想我会发布一个可能的答案)。
也许我可以:
- 扫描一次数据并获取最高键
- 分配一个大小为最高键 + 1 的数组。
- 进行第二次传递并将数据存储在数组中。
这会比具有合理负载因子的 HashTable/Dictionary 更好还是更差?
最佳答案
字典是正确的方法。这是来自 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% 的内存开销来存储每个键值对。
关于c# - 用于只读字典访问的最有效的内存数据结构,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8570201/