哈希表支持在Θ(1)时间内完成下列操作：
1) 查找 2) 插入 3) 删除
对于自平衡的二叉搜索树，比如红黑树（Red-Black Tree），平衡二叉树（AVL Tree），伸展树（Splay Tree）等，上述操作的时间复杂度是O(Logn)。
因此对于常用操作哈希表似乎完胜BST。那么我们在什么时候应该选择BST而不是哈希表，BST的优势何在。下面是BST的几项比较重要的优势。
我们只需通过中序遍历BST即可获得排好序的key列表。而这并非哈希表的自然操作，需要额外的工作才可以实现。
使用BST可以很容易地执行顺序统计，找出最接近的最小和最大元素，执行范围查询。像排序一样，这些操作也不是哈希表的自然操作。
BST相较于哈希表更容易实现，我们可以很容易地实现自定义的BST。而要实现哈希表，我们一般需要依赖编程语言提供的库函数。
使用BST，所有的操作都可以确保在O(Logn)时间内完成，而对于哈希表， Θ(1) 是平均时间，对于某些特定的操作代价可能会比较高，尤其是当表的大小需要调整时。
英文原文：
Hash Table supports following operations in Θ(1) time.
1) Search
2) Insert
3) Delete
The time complexity of above operations in a self-balancing Binary Search Tree (BST) (like Red-Black Tree,AVL Tree, Splay Tree, etc) is O(Logn).
So Hash Table seems to beating BST in all common operations. When should we prefer BST over Hash Tables, what are advantages. Following are some important points in favor of BSTs.
We can get all keys in sorted order by just doing Inorder Traversal of BST. This is not a natural operation in Hash Tables and requires extra efforts.
Doing order statistics, finding closest lower and greater elements, doing range queries are easy to do with BSTs. Like sorting, these operations are not a natural operation with Hash Tables.
BSTs are easy to implement compared to hashing, we can easily implement our own customized BST. To implement Hashing, we generally rely on libraries provided by programming languages.
With BSTs, all operations are guaranteed to work in O(Logn) time. But with Hashing, Θ(1) is average time and some particular operations may be costly, especially when table resizing happens.
原文链接：Advantages of BST over Hash Table
本文链接：http://bookshadow.com/weblog/2015/04/02/advantages-of-bst-over-hash-table/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。
捐赠书影博客
