Hash Table VS Red-Black Tree gaunthan Posted on Jan 16 2017 ? Data Structures ? > 你有了解过C++、Java和C#中的map和set的实现吗？据我所知，流行的实现都是默认采用红黑树作为底层数据结构，而不是散列表。那么问题来了，为什么？ ## 散列表的特点 我们知道，散列表对关键字进行散列，算出一个值以决定它在表中的存储位置。在发生冲突时，散列表有分离链接和开放定址两种方法来解决。冲突解决方法的不同，导致算法操作的最坏时间复杂度也有所不同。但是从平均时间复杂度的角度来看，散列表的操作都是**常数平均时间**的，即$\theta (1)$。 ## 红黑树的特点 红黑树是平衡二叉查找树的一种，因此它的操作都是**对数平均时间**的，即$\theta (logN)$。 红黑树与AVL树有些许差异，AVL树是高度严格平衡的，这导致相比于红黑树，它的查找效率较高。但是，相比其他操作，如插入、更新和删除，红黑树的表现更佳。因此对于标准库来说，如果要使用平衡树来实现某些东西，则往往会选用红黑树，因为它**更具一般性**。 ## map和set的选择 那么，回到最初的问题，map的底层实现该选择哪种数据结构？由于我们无法确定容器大小，因此我们的选择只有： - 红黑树 - 基于分离链接散列法的散列表 首先，我们还需要明确一些东西： - 能够排序的关键字，不一定能散列。 - 为了通用性，散列的代价往往比较大。 - 先序、后序遍历平衡二叉树，能够得到两种排序结果。 为了一般性，标准库只好默认使用红黑树实现。 对于C++而言，有序容器std::map和std::set都使用红黑树，同时提供使用散列表的实现：无序容器std::unordered_map。也许你会奇怪为什么不像Java一样，直接提供TreeMap和HashMap？根据[Stack Overflow上的一篇文章的一个回答](http://stackoverflow.com/questions/22665902/why-stdmap-is-red-black-tree-and-not-hash-table?rq=1)：  原因是**来不及**。在意识到之前，已经冻结版本特性了。 ## 参考资料 - [Hash tables v self-balancing search trees](http://stackoverflow.com/questions/3265266/hash-tables-v-self-balancing-search-trees) - [Why std::map is red black tree and not hash table ?](http://stackoverflow.com/questions/22665902/why-stdmap-is-red-black-tree-and-not-hash-table?rq=1) - [Why is std::map implemented as a red-black tree?](http://stackoverflow.com/questions/5288320/why-is-stdmap-implemented-as-a-red-black-tree) 赏 Wechat Pay Alipay 装饰者模式 设计原则
