点击上方【蓝字】关注博主
“ 文章探讨了C++STL中的map使用红黑树而非散列表的原因，分析了红黑树和散列表在查找、插入、删除操作的时间复杂度、空间利用率等方面的差异，并介绍了unordered_map作为散列表实现的特点和应用场景。红黑树在保持良好平衡性的同时提供稳定的查找效率，适合有序存储，而unordered_map利用散列表实现快速插入和查找，但不保证元素顺序。”
简介
红黑树和散列表的基本介绍
2.1、定义和特性
红黑树和散列表是两种常见的数据结构，用于实现map（映射）这样的键值对存储结构。
2.1.1、红黑树
红黑树是一种自平衡的二叉搜索树，它的定义和特性如下：
每个节点要么是红色，要么是黑色。
根节点是黑色的。
每个叶子节点（nil节点，空节点）是黑色的。
如果一个节点是红色的，则它的子节点必须是黑色的。
从根节点到叶子节点的每条路径上，黑色节点的数量相同。
红黑树具有以下优势：
插入、删除和查找操作的平均时间复杂度为O(logN)。
在动态插入和删除元素时能够自动保持树的平衡，避免出现极端情况下的不平衡现象。
2.1.2、散列表（Hash Table）
散列表（Hash Table）是根据键（Key）直接访问存储位置的数据结构，它的定义和特性如下：
使用散列函数将键映射到存储位置。
存储位置通常是一个数组，称为散列表。
存储位置的选择是根据键的哈希值计算得出的。
不同的键可能会有相同的哈希值，称为哈希冲突。
散列表具有以下限制：
散列表的查找操作平均时间复杂度为O(1)，但最坏情况下可能达到O(n)（所有键映射到同一个位置）。
需要额外的空间来存储散列表本身。
哈希冲突的处理需要使用冲突解决方法，例如链表法或开放寻址法。
2.1.3、如何选择？
在具体应用中选择红黑树还是散列表：
如果对查找操作的性能要求较高，且数据量较大，可以选择红黑树。
如果对内存使用和空间复杂度要求较高，或者数据量较小，可以选择散列表。
unordered_map是C++ STL中的一种基于散列表实现的map容器，它具有散列表的特性，例如
2.2、应用场景和优缺点
红黑树：
应用场景：适用于需要频繁插入、删除、查找操作且数据量较大，要求有序性的情况。
优点：① 具有平衡性，插入、删除、查找的时间复杂度为
O ( l o g n ) 缺点：①相对于散列表来说，需要更多的内存空间；②对于基于散列的操作，如随机访问，并不擅长。
散列表：
应用场景：适用于需要频繁插入、删除、查找操作且数据量较大，不需要有序性的情况。
优点：①查找、插入、删除的平均时间复杂度为O(1)，最坏时间复杂度是O(n)；②支持随机访问，性能通常比树要好。
缺点：①可能会出现哈希冲突，需要使用冲突解决方法，如链表法、开放寻址法等；②散列表的元素是无序的，不支持有序遍历。
对比红黑树和散列表
3.1、查找操作的时间复杂度
基于红黑树的性质，可以推导出红黑树的高度不会超过
2 l o g ( N + 1 ) O ( l o g N ) 散列表的查找操作平均时间复杂度为O(1)，最坏时间复杂度为O(n)。散列表（哈希表）的查找操作时间复杂度通常是O(1)，即常数时间是在一定条件下成立的：
在散列表中，通过将关键字映射到数组的特定位置来存储和检索元素。当执行查找操作时，使用关键字计算其哈希值，并根据哈希值找到对应的桶或槽，然后在该桶中进行查找。如果哈希函数和散列冲突处理方法选择得当，平均情况下可以达到O(1)的时间复杂度。
然而，在某些情况下，散列冲突可能会发生，即不同的关键字经过哈希函数计算得到的哈希值相同，导致它们被映射到同一个桶中。为了解决冲突，散列表采用了各种冲突解决方法，如链地址法、开放地址法等。
当采用链地址法时，每个桶都是一个链表，发生冲突后，将元素插入到对应桶的链表中。此时，在最坏情况下，如果所有元素都映射到同一个桶中，那么查找操作的时间复杂度可能会退化到O(n)，其中n是散列表中元素的数量。
而采用开放地址法时，发生冲突后，会根据特定的探测序列依次查找下一个可用的桶。常见的探测序列包括线性探测、二次探测和双重哈希等。在开放地址法中，如果散列表的负载因子保持较低，并且有足够的空间，平均情况下仍可以达到O(1)的时间复杂度。
3.2、空间利用率
在空间利用率方面，散列表会占用更多的空间，因为它需要额外的空间来存储哈希表的桶和哈希冲突解决方法所需的链表或探测序列等。而红黑树只需要存储节点数据和指向左右子树的指针。因此，红黑树在空间利用率方面相对于散列表更为优秀。
3.3、其他方面
除了在空间利用率方面比较之外，红黑树和散列表在内存消耗方面也有所不同。由于散列表需要额外的空间来存储哈希表的桶和哈希冲突解决方法所需的链表或探测序列等，因此其内存消耗相对于红黑树更大。
红黑树是一种有序树结构，可以用于实现各种有序算法和数据结构。而散列表是一种无序结构，不适合用于需要维护元素顺序的场合。
散列表的空间复杂度会随着元素数量的增加而增加，而红黑树的空间复杂度与元素数量无关，只与树的高度有关。因此，在元素数量较大时，红黑树的空间复杂度相对于散列表更优秀。
为什么map选择红黑树？
4.1、红黑树的优势
红黑树的查询效率比散列表更为稳定，不会因为哈希冲突等因素而导致查询性能下降。在查询方面，红黑树的时间复杂度为O(log n)（n为树中元素个数），而散列表的查询时间复杂度为O(1)。但是，在涉及到大量数据的情况下，红黑树的常数因子更小，查询效率更高。
红黑树的插入和删除操作的时间复杂度也为O(log n)，相对于散列表来说更为稳定，不会因为哈希冲突等因素导致性能下降。
红黑树是一种平衡二叉搜索树，具有良好的稳定性。在任何情况下，红黑树的平衡性都能得到保持。而散列表的性能会因为哈希冲突等因素而不稳定。
红黑树相对于散列表来说，内存消耗更为稳定，不会因为哈希冲突等因素而引起内存的浪费。
红黑树是一种有序树结构，可以维护元素的顺序，而散列表是一种无序结构，不适用于需要维护元素顺序的场合。
红黑树支持动态扩容和缩容，而散列表需要重新计算哈希函数，重新分配内存等过程，相对来说比较复杂。
4.2、散列表的限制
冲突：散列冲突指不同的关键字经过哈希函数计算得到相同的哈希值，导致它们映射到相同的桶中。冲突会影响查找效率，需要采用适当的冲突解决方法，如链地址法、开放地址法等。
类型限制：散列表的键（关键字）通常需要具备可哈希性和可比较性。因此，对于自定义类型的对象，需要实现哈希函数和比较运算符来支持散列表的操作。
空间消耗：散列表需要额外的空间来存储桶和相关数据结构，对于大规模数据集或内存受限的环境，可能会占用较多的内存空间。
散列函数选择：选择一个良好的散列函数对散列表的性能至关重要。一个低质量的散列函数可能导致冲突增加，进而降低查找效率。
负载因子：负载因子是指散列表中已存储元素数量与总桶数的比例。负载因子过高会增加冲突的概率，进而影响查找效率。为了避免负载因子过高，可能需要进行动态调整和重新散列。
不支持有序性：散列表是基于哈希值进行存储和检索的，不保证元素的有序性。如果需要按照顺序访问或排序元素，通常需要使用其他数据结构。
unordered_map和散列表的关系
5.1、unordered_map的特性与应用
5.2、为什么unordered_map使用散列表?
散列表通过将键映射到存储桶（bucket）中，可以实现接近常数时间的查找和插入操作。通过正确选择哈希函数和调整散列表的大小，可以使大多数操作在平均情况下具有非常高效的时间复杂度。
散列表使用哈希函数将键映射到不同的存储桶中，可以将元素均匀地分布在整个散列表中。在理想情况下，每个存储桶中有相等数量的元素，从而最大程度地减少了冲突（多个键映射到同一个存储桶）的可能性。
当多个键通过哈希函数映射到同一个存储桶时，会发生冲突。散列表使用冲突解决技术来处理冲突，最常见的方法是链地址法（chaining），即在同一个存储桶中使用链表或其他数据结构将冲突的元素链接起来。这样，即使有冲突发生，也可以通过链表的遍历等方式快速地找到目标键。
散列表大小可以根据需要进行调整，以适应不同的数据集和操作。在实际使用中，可以根据负载因子（load factor）来判断是否需要重新调整散列表的大小，以保持较低的冲突和高效的性能。
散列表中的元素没有固定的顺序，与插入的顺序无关。这种无序性使得unordered_map容器适用于不需要保持元素顺序的需求，例如字典、索引等。
基于以上原因，散列表作为unordered_map的底层数据结构，提供了快速的查找和插入操作，并且适用于不需要保持元素顺序的场景。通过合理选择哈希函数和调整散列表的大小，可以最大限度地发挥散列表的优势，并提供高性能和灵活性。
map和unordered_map的选择
总结
在选择容器时，根据具体需求权衡使用场景并选择最适合的容器。例如，需要有序性时可选择map，需要快速插入/删除操作时可选择unordered_map。
注意不同容器之间的特点和性能差异，了解它们的底层实现机制和时间复杂度，以便作出合理的选择。
使用迭代器进行遍历和访问容器元素，可以灵活地操作数据。
注意容器使用过程中的内存管理，避免内存泄漏和多余的复制操作。
熟悉容器提供的成员函数和算法，利用它们来简化代码，提高开发效率。
公众号: Lion 莱恩呀
微信号: 关注获取
扫码关注 了解更多内容
点个 在看 你最好看
