c# - C# 中字符串字典的最佳性能

Question

我正在设计一个包含字符串层次结构的 C# 类，其中每个字符串都有 0 或 1 个父级。

我的倾向是用Dictionary<string,string>key 是 child 而 value 是 parent 来实现这一点。字典可能有大量的值，但我不能说确切的大小。这似乎应该比使用对父级的引用创建复合包装器更快，但我可能是错的。

有没有我可以采取的替代方法来确保更好的性能速度？

Answer 1

从 a 中检索值Dictionary<K,V>非常快（接近 O(1)，即几乎恒定的时间查找，而不管集合的大小），因为底层实现使用哈希表。当然，如果该key类型使用糟糕的散列算法，则性能可能会降低，但您可以放心，框架的string类型可能并非如此。

但是，正如我在评论中所问的，您需要回答几个问题：

1. 定义最重要的性能指标，即时间（CPU）或空间（内存）。
2. 你有什么要求？这将如何使用？你最坏的情况是什么？这是否会保存大量查找相对不频繁的数据，是否需要在短时间内执行许多查找，或者两者都成立？

该类Dictionary<K,V>还在内部使用一个数组，该数组会随着您添加项目而增长。这对你好吗？同样，在任何人都可以给您完整的答案之前，您需要更具体地了解您的要求。

Answer 2

使用字典比使用直接引用要慢，因为字典必须计算哈希等。如果你真的只需要父而不是子的操作（我怀疑），那么你可以将字符串一起存储在一个数组中与父字符串的索引。