c# - 树和字典的合理大小

Question

我目前正在实现一个非常复杂的树结构，以允许近乎即时的数据访问，而不是对每个请求进行重新处理。

我只是想知道是否存在理论或实际限制树的大小变得太大，或者字典变得过于冲突而无法正确/快速运行的点？

一个一般的答案将不胜感激，但特定于 C# 的信息会更好！

Answer 1

在 .NET 中，树或字典中的最大值为 2^31 - 1（并且可能会减少一些开销）。

实际上，您可能早就用完了内存！

如果树保持平衡，则搜索将保持大约。O(log N)。

字典对使用的底层算法更敏感，例如有许多具有不同特征的散列方案。

Answer 2

取决于你认为的量很大。数百或数千应该没问题，但数百万可能值得寻找专门的东西。

树会随着你的成长而变慢，这取决于你的存储技术和重新平衡。

字典应该是相当一致的，但请确保您构建它的大小与您可能存储的数据量相适应（也许 x2 是安全的）。

Answer 3

看到这个问题- 这是我在 So 上回答的第一个问题：）

问题是构建包含大约 900,000 个项目的字典的性能缓慢。我将时间从 10 多分钟缩短到 0.34 秒。

教训是，字典只和你的散列函数一样好，如果你能快速生成一个唯一的散列，它会像闪电一样运行。

希望这可以帮助，

编辑：

比较类并不重要，.net 字符串具有非常强大的哈希函数，因此 - 在字典中具有出色的性能。如果他一直使用单弦而不是双弦，那家伙的问题就会“消失”。