BST，Hashing，Tries和地圖之間的區別

Question

我閱讀了一些關於Tries，hashing，Map（stl）和BST的博客和教程。我很困惑哪一個更好用，哪個更好。我知道，讓它們之間的這種區別是無稽之談，因爲它們都依賴於實現。請您告訴我更具體的內容，請不要忘記提及複雜性（最差，平均和最好的情況）。

在此先感謝...

Answer 1

BST是二叉搜索樹。它用於字典。 BST對結構沒有限制，因此搜索/插入/刪除是O（n）最差的情況。

地圖 [on stl]也是一本字典，實際上是一個紅黑樹[on stl]。它是一種特殊的BST，它對結構有限制，因爲它最糟糕的情況是搜索/插入/刪除是O（logn）。

hashing散列表是一種不同類型的字典，散列表[具有良好散列函數]的優點是O（1）搜索/刪除/插入的平均時間。然而，最糟糕的情況是O（n），如果過多的元素相互碰撞和/或需要重新散佈，就會發生這種情況[Load Balance過高時，我們分配一個更大的數組，然後重新哈希所有元素]。

嘗試是特殊的字符串。所有的操作符都是O（S），其中S是字符串的長度。這對其他人來說是有利的[在處理字符串時]是否需要讀取字符串，所以例如在處理字符串時的複雜性實際上是O（S * n * logn）。

何時使用？
a Map [或任何其他平衡樹]應該幾乎總是一個更好的選擇，然後定期BST。
hash table當你想要平均短時間時，是一個不錯的選擇，但不要在意有時候你會因重新散佈而導致性能損失，並且在某些情況下可能會發生衝突。
Trie通常是一個很好的字典字典。