哈希表何时比搜索树更好用？

Question

哈希表何时比搜索树更好用？

Answer 1

取决于您想要对数据结构做什么.

Operation         Hash table  Search Tree
Search            O(1)        O(log(N))
Insert            O(1)        O(log(N))
Delete            O(1)        O(log(N))
Traversal         O(N)        O(N)
Min/Max-Key       -hard-      O(log(N))
Find-Next-Key     -hard-      O(1)

• Insert,Search on Hashtable取决于哈希表的加载因子及其设计.设计糟糕的hastables可以进行O(N)搜索和插入.您的搜索树也是如此.

• 根据您的冲突解决方案状态,在哈希表中删除可能很麻烦.

• 遍历容器,查找最小值/最大值,查找下一个/上一行操作在搜索树上更好,因为它的排序.

• 上面搜索树的所有估计都是针对"平衡"搜索树的.