合理的樹大小和字典

Question

我目前正在實現一個非常複雜的樹結構，以允許近乎即時的數據訪問，而不是對每個請求進行重新處理。

我只是想知道是否存在一個理論上或實際的限制，即樹的大小變得過大，或者字典變得過於碰撞以使其正確/快速運行的一個點？

一般的答案將不勝感激，但C＃特有的信息會好得多！

Answer 1

在.NET中，樹或字典中的最大值爲2^31 - 1（可能少於開銷）。

實際上，您可能會在很久之前耗盡內存！

如果樹保持平衡，則搜索將保持約。 O（log N）。

字典對所使用的底層算法更敏感，例如有許多具有不同特徵的散列方案。

Answer 2

取決於你認爲的大量。數百或數千人應該沒問題，但數百萬人可能值得尋找專門的東西。

根據您的存儲技術和重新平衡，樹會隨着增長而變慢。

字典應該是相當一致的，但要確保它的大小適合您可能存儲的數據量（可能x2是安全的）。

Answer 3

見this question - 這是我第一次回答了一個這樣:)

問題是性能下降建設字典，約90萬項。我把時間從10分鐘縮短到了0.34秒。

教訓是，字典只有你的散列函數一樣好，如果你能快速生成一個獨特的散列，它會像閃電一樣運行。

希望這有助於

編輯：

比較類並不重要，.NET字符串有很強的散列函數和 - 因此 - 在字典優異的性能。如果他使用單個字符串而不是字符串對，那麼這些傢伙的問題就會「消失」。