data-structures - BST , Hashing , Tries 和 map 的区别

Question

我阅读了一些关于 Tries、散列、Map(stl) 和 BST 的博客和教程。我很困惑哪个更好用以及在哪里使用。我知道在它们之间做出这样的区别是无稽之谈，因为它们都依赖于实现。请您更具体地告诉我，请不要忘记提及复杂性（最坏、平均和最佳情况）。

提前致谢...

Answer 1

BST是二叉搜索树。它用于字典。BST 对结构没有限制，因此搜索/插入/删除是 O(n) 最坏的情况。

Map [on stl] 也是一个字典，实际上是一个红黑树 [on stl]。它是一种特殊的 BST，对结构有限制，因此，最坏情况的搜索/插入/删除是 O(logn)。

哈希哈希表是一种不同类型的字典，哈希表 [具有良好哈希函数] 的优点是搜索/删除/插入的平均时间为 O(1)。然而，最坏的情况是 O(n)，如果太多的元素发生冲突和/或需要重新散列时[当负载平衡太高，我们分配一个更大的数组，并将所有元素重新散列到 is] 时，就会发生这种情况。

尝试对于字符串是特殊的。所有操作都是 O(S)，其中 S 是字符串的长度。其他[处理字符串时]的优势是无论如何您都需要读取字符串，因此Map例如，在处理字符串时，复杂性实际上是O（S * n * logn）。

什么时候使用？
a Map[或任何其他平衡树] 几乎总是比常规树更好的选择BST。
hash table当您想要平均较短的时间时，这是一个不错的选择，但不要关心有时您会由于重新哈希而导致性能损失，并且在某些情况下可能会发生冲突。
Trie通常是一个很好的字符串字典。