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 装饰者模式 设计原则