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

Question

在 C# 中，我有一些静态数据可以放入

Dictionary<int, T>

中，其中

T

是某种引用类型。 Web 应用程序只需静态初始化一次（不会改变）。

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

我正在寻找一种获取这些数据的最佳算法。

Dictionary<>

还不错，但我想一定有针对只读数据进行优化的东西。

我怀疑，但尚未证实这些键的范围可能是 0 - 400,000。 如果是这样的话，建议会如何改变？ （我想我会发布作为可能的答案）。

---

也许我可以：

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

这比具有合理负载因子的哈希表/字典更好还是更差？

Answer 1

字典是正确的选择。这是来自MSDN的引用：

Dictionary(Of TKey, TValue)泛型类提供了从 一组键对应一组值。每次添加到字典中的内容 由一个值及其关联的键组成。通过以下方式检索值 使用它的 key 非常快，接近 O(1)，因为 Dictionary(Of TKey, TValue) 类被实现为哈希表。

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

编辑

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

Answer 2

如果它确实是字典，那么 trie 效果相当好。

Dictionary

（哈希表）是另一种可能性，只要你对其进行微调即可。哪个会更快......我不知道，我想你需要对其进行分析。从空间角度来看，trie 轻而易举地获胜。我认为 .NET 的标准库中没有 trie，但应该有一些实现。

Answer 3

您可能想使用 .Net8.0 中提供的 Frozen Dictionaries 进行结帐

参考：https://learn.microsoft.com/en-us/dotnet/api/system.collections.frozen.frozendictionary-2

州：

FrozenDictionary 是不可变的，并且针对不经常创建字典但在运行时频繁使用的情况进行了优化。它的创建成本相对较高，但提供了出色的查找性能。因此，对于字典创建一次（可能在应用程序启动时）并在应用程序的剩余生命周期中使用的情况来说，它是理想的选择。

然后可以从扩展方法中实例化它，例如

new KeyValuePair<string, string>[]{ new ("Hello", "World" )}.ToFrozenDictionary();

还提醒一下，using命名空间是

System.Collections.Frozen

。

这里有一个基准：https://code-corner.dev/2023/11/08/NET-8-%E2%80%94-FrozenDictionary-performance/