2.13、set的底层实现为什么不用哈希表而是用红黑树

1. std::set的设计目标：有序且唯一的元素集合

std::set是一个有序关联容器，它不仅保证元素唯一，还保证元素按照严格弱序（默认是升序）排列，用户可以通过迭代器顺序访问元素，这一点是哈希表无法直接满足的。
红黑树是一种自平衡的二叉搜索树，天然支持元素的排序和范围查询，能够在对数时间内完成插入、删除和查找操作，同时保持元素有序。

2. 哈希表的无序性与std::set需求不符

哈希表通过哈希函数将元素映射到桶中，元素存储顺序依赖于哈希值，不保证元素的顺序，因此不适合需要有序访问的场景。
如果只关心快速查找且不需要排序，C++提供了std::unordered_set，它基于哈希表实现，平均查找时间复杂度为O(1)，但最坏情况下可能退化为O(n)。

3. 类型要求和泛型编程的考虑

• • 红黑树只要求元素类型支持比较操作符（<），这使得std::set能支持广泛的类型。
• • 哈希表则要求元素类型必须有合适的哈希函数和相等比较函数，这增加了泛型编程的复杂度和限制。
  STL设计者倾向于使用红黑树，因为它“开箱即用”，不依赖用户提供哈希函数，减少了使用门槛和出错概率。

4. 性能权衡与应用场景

• • 红黑树：查找、插入、删除时间复杂度均为O(log n)，虽然比哈希表的平均O(1)慢，但提供了有序性和稳定的性能表现，支持频繁范围查询、排序访问的场景。
• • 哈希表：查找快，但存在哈希冲突、扩容代价大、最坏情况性能退化等问题，且不支持有序遍历，适合只需快速查找且不关心顺序的场景（如std::unordered_set）。

5. 设计哲学与历史背景

• • C++ STL设计者Alexander Stepanov等人选择红黑树作为std::set和std::map的底层实现，是基于其自平衡特性和稳定的性能表现。
• • STL设计时，哈希表的实现和性能调优较为复杂，且哈希函数的设计依赖具体应用，红黑树提供了更通用且易于维护的解决方案。
• • 近年来，随着硬件缓存和内存访问模式的变化，有研究建议使用B*树等缓存友好型数据结构替代红黑树，但红黑树依然是标准库默认的选择。

总结

std::set采用红黑树而非哈希表的核心原因是：

1. 1. 有序性需求：set需要保持元素有序，红黑树天然支持，而哈希表无序。
2. 2. 接口和泛型约束：红黑树只需元素支持比较，哈希表需额外哈希函数，降低泛用性。
3. 3. 稳定性能和功能：红黑树提供对数时间复杂度的稳定性能，支持范围查询和有序遍历。
4. 4. 设计简洁和通用：红黑树“开箱即用”，不依赖复杂的哈希策略，符合STL设计哲学。
   本文首发于【讳疾忌医-note】公众号，未经授权，不得转载。
   （加入我的知识星球，免费获取账号，解锁所有文章。）