合理的树大小和字典

Question

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

我只是想知道是否存在一个理论上或实际的限制，即树的大小变得过大，或者字典变得过于碰撞以使其正确/快速运行的一个点？

一般的答案将不胜感激，但C＃特有的信息会好得多！

Answer 1

在.NET中，树或字典中的最大值为2^31 - 1（可能少于开销）。

实际上，您可能会在很久之前耗尽内存！

如果树保持平衡，则搜索将保持约。 O（log N）。

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

Answer 2

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

根据您的存储技术和重新平衡，树会随着增长而变慢。

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

Answer 3

见this question - 这是我第一次回答了一个这样:)

问题是性能下降建设字典，约90万项。我把时间从10分钟缩短到了0.34秒。

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

希望这有助于

编辑：

比较类并不重要，.NET字符串有很强的散列函数和 - 因此 - 在字典优异的性能。如果他使用单个字符串而不是字符串对，那么这些家伙的问题就会“消失”。