Ami*_*Pal 4 hash trie time-complexity binary-search-tree data-structures
我在Tries,hashing,Map(stl)和BST上阅读了一些博客和教程.我很困惑哪一个更好用,哪里.我知道在它们之间做出这样的区别是无稽之谈,因为它们都是依赖于实现的.请您告诉我更具体的内容,请不要忘记提及复杂性(最差,平均和最佳情况).
提前致谢...
BST是二进制搜索树.它用于字典.BST对结构没有限制,因此搜索/插入/删除是O(n)最坏情况.
Map [on stl]也是一个字典,实际上是一个红黑树[在stl].它是一种特殊的BST,它对结构有限制,因此,最坏的情况是搜索/插入/删除是O(logn).
哈希哈希表是一种不同类型的字典,哈希表[具有良好的哈希函数]的优点是搜索/删除/插入的平均时间为O(1).然而,最坏的情况是O(n),如果太多元素碰撞和/或需要重新散列时发生[当负载平衡太高时,我们分配一个更大的数组,并将所有元素重新组合为].
尝试是特殊的字符串.所有操作都是O(S),其中S是字符串的长度.它对其他人[在处理字符串时]的优点是你需要读取字符串,所以Map例如,当处理字符串时,复杂性实际上是O(S*n*logn).
什么时候用？
一个Map[或任何其他平衡的树]几乎总是比常规树更好的选择BST.
hash table当你想要平均短时间时,这是一个不错的选择,但是有时你不会因重新散列而导致性能下降,并且在某些情况下可能会发生冲突.
Trie通常是字符串的好词典.