引言
在C++标准库中，map和unordered_map是两个常用的关联容器，它们都提供了键值对的存储和查找功能，但在底层实现和使用特性上却有着本质的区别。map基于红黑树实现，保证了元素的有序性，而unordered_map基于哈希表实现，追求更快的查找速度。要深入理解这两种容器的差异，我们需要从它们底层的数据结构说起。
《C++标准库》里把容器分为了三类：序列式容器，关联式容器，以及无序容器。虽然都叫map，但map和unordered_map的map经常被拿来比较可能也就是名字非常像的原因。map属于关联式容器，unordered_map是无序容器。我觉得不能说他们都是用key来查找value所以很像，那这些容器的基本功能不都是通过一个索引来查找访问数据吗？无非是这个key是简单的数字值还是我们自己想用的类型罢了。
红黑树：map的底层实现
红黑树是一种自平衡的二叉搜索树，它通过为每个节点添加颜色属性（红色或黑色）来维持树的平衡。红黑树的设计思想在于通过相对宽松的平衡条件来减少旋转操作的频率，从而在查找、插入和删除操作之间取得一个较好的平衡。
红黑树的核心特点体现在它的五个约束条件上。首先，每个节点要么是红色，要么是黑色。其次，根节点必须是黑色。第三，所有叶子节点（空节点）都被视为黑色。第四，如果一个节点是红色的，那么它的两个子节点都必须是黑色的，这意味着红色节点不能连续出现。最后，从任意节点到其每个叶子节点的所有路径上，黑色节点的数量必须相同，这个特性保证了红黑树的高度不会过度增长。
这些约束条件虽然不如AVL树那样严格，但足以保证红黑树的高度在最坏情况下也不会超过2倍的最小高度，从而保证了查找操作的时间复杂度为O(log n)。更重要的是，由于平衡条件相对宽松，红黑树在插入和删除操作时需要的旋转次数通常比AVL树少，这使得它在需要频繁修改的场景下表现更好。
AVL树：严格平衡的代表
AVL树是另一种自平衡二叉搜索树，它以发明者Adelson-Velsky和Landis的名字命名。AVL树的设计哲学是追求严格的平衡，它要求任何节点的左右子树高度差不能超过1。这种严格的平衡条件使得AVL树在任何时候都保持接近完全平衡的状态。
AVL树通过旋转操作来维持平衡，当插入或删除操作导致某个节点的平衡因子（左右子树高度差）超过1时，就会触发相应的旋转操作。单旋转包括左旋和右旋，双旋转包括左右旋和右左旋。这些旋转操作能够有效地恢复树的平衡，但同时也带来了一定的性能开销。
由于AVL树始终保持严格的平衡，它的查找性能在所有自平衡树中是最优的，查找操作的时间复杂度稳定在O(log n)，且常数因子较小。然而，这种严格的平衡也意味着在插入和删除操作时，AVL树可能需要执行更多的旋转操作来维持平衡，这使得它在需要频繁修改的场景下性能可能不如红黑树。
红黑树与AVL树的权衡
红黑树和AVL树在平衡策略上的差异，反映了在查找性能和修改性能之间的不同权衡。红黑树通过允许一定程度的不平衡来减少旋转操作的频率，这使得它在插入和删除操作时效率更高，但查找时可能需要更多的比较次数。而AVL树通过严格的平衡条件来优化查找性能，但代价是在修改操作时需要更多的平衡调整。
从高度角度来看，AVL树的高度通常比红黑树更小，因为它的平衡条件更严格。红黑树虽然整体高度可能较大，但它有一个重要的特性：从根节点到任意叶子节点的路径上，黑色节点的数量是相同的。这个特性保证了红黑树的高度不会过度增长，同时减少了维护平衡的开销。
在实际应用中，红黑树被广泛采用，特别是在C++标准库的map和set容器中。这是因为在实际场景中，容器往往需要同时支持查找和修改操作，而红黑树在两者之间取得了更好的平衡。AVL树则更适合那些查找操作远多于修改操作的场景。
哈希散列的实现方法
哈希表是unordered_map的底层实现，它通过哈希函数将键映射到数组的特定位置，从而实现快速查找。哈希函数的设计直接影响哈希表的性能，不同的实现方法各有特点。
开放定址法是最直观的哈希冲突解决方法之一。当发生冲突时，它会按照某种探测序列在哈希表中寻找下一个可用的位置。线性探测是最简单的形式，它按顺序检查下一个位置，直到找到空位。二次探测使用二次函数来生成探测序列，能够减少聚集现象。双重散列则使用第二个哈希函数来生成探测序列，进一步减少了冲突的可能性。开放定址法的优点是不需要额外的存储空间来存储链表，但缺点是删除操作比较复杂，且容易产生聚集现象。
链地址法，也称为拉链法，是另一种常见的冲突解决方法。它将哈希表的每个位置都作为一个链表的头节点，当发生冲突时，将新元素插入到对应位置的链表中。这种方法实现简单，删除操作也很直接，但需要额外的空间来存储链表指针。当链表过长时，查找性能会下降，因此需要合理设计哈希函数和负载因子。
再哈希法使用多个哈希函数，当第一个哈希函数发生冲突时，尝试使用第二个、第三个哈希函数，直到找到空位。这种方法能够有效减少冲突，但需要设计多个良好的哈希函数，实现复杂度较高。
建立公共溢出区是另一种思路，它维护一个额外的区域来存储所有发生冲突的元素。这种方法实现简单，但当冲突较多时，溢出区会变得很大，查找性能会下降。
C++ unordered_map的哈希实现
C++标准库的unordered_map主要采用链地址法来解决哈希冲突。这种选择有其合理性，因为链地址法实现相对简单，且能够很好地处理动态扩容和缩容的情况。当哈希表中的元素数量增加时，标准库会自动进行扩容操作，重新分配更大的桶数组，并将所有元素重新哈希到新的位置。
在哈希函数的选择上，C++标准库为基本类型提供了默认的哈希函数，对于自定义类型，则需要用户提供哈希函数或者特化std::hash模板。对于字符串类型，一些实现可能会使用SipHash算法，这是一种密码学安全的哈希函数，能够有效防止哈希碰撞攻击，同时对于相近的字符串能够表现出良好的随机分布特性，从而减少哈希冲突的发生。
unordered_map的扩容与缩容机制
unordered_map的扩容机制是自动的，当负载因子（元素数量与桶数量的比值）超过设定的最大值时，容器会自动进行扩容操作。默认情况下，最大负载因子为1.0，但可以通过max_load_factor成员函数进行调整。扩容时，容器会创建一个更大的桶数组，通常是当前大小的两倍左右，然后对所有元素进行重新哈希，这个过程称为rehash。
然而，unordered_map默认情况下不会自动缩容。即使元素数量大幅减少，桶数组的大小也不会自动缩小，这可能导致内存浪费。不过，标准库提供了rehash和reserve等接口，允许用户手动控制桶的数量。如果我们在使用erase等操作大量删除元素后，希望减少内存占用，可以调用rehash函数来手动触发重新哈希，从而减少桶的数量。
unordered_map的性能优化
要充分发挥unordered_map的性能优势，有几个关键的优化点需要注意。首先，如果我们能够预估元素的数量，应该在创建容器时就通过reserve函数设置合适的桶数量，这样可以避免多次自动扩容带来的性能开销。其次，选择合适的哈希函数至关重要，一个好的哈希函数应该能够将键均匀分布到各个桶中，减少冲突的发生。对于自定义类型，我们需要仔细设计哈希函数，确保它既快速又具有良好的分布特性。
负载因子的设置也是一个重要的优化点。默认的负载因子为0.75，这是一个在内存占用和性能之间的折中选择。如果我们更注重查找性能，可以适当降低负载因子，这样每个桶中的元素会更少，查找速度会更快，但内存占用会增加。相反，如果内存紧张，可以适当提高负载因子，但要注意过高的负载因子会导致冲突增多，性能下降。
map与unordered_map的全面对比
map和unordered_map在多个方面都存在显著差异，这些差异决定了它们各自适用的场景。从数据结构的角度来看，map基于红黑树实现，是一种有序的数据结构，而unordered_map基于哈希表实现，元素之间没有特定的顺序关系。
在查找性能方面，map的查找时间复杂度为O(log n)，这是一个稳定的性能保证。而unordered_map的平均查找时间复杂度为O(1)，但在最坏情况下可能退化到O(n)，这通常发生在哈希函数设计不当或发生大量冲突的情况下。因此，如果我们需要稳定的性能保证，map可能更合适；如果追求平均情况下的高性能，unordered_map是更好的选择。
有序性是一个重要的区别。map中的元素按照键的大小自动排序，这使得范围查询变得非常高效，我们可以轻松地找到某个范围内的所有元素。而unordered_map中的元素是无序的，它不支持范围查询，但单点查询的性能通常更好。
在内存占用方面，红黑树作为平衡二叉树，基本没有空间浪费，每个节点都存储实际的数据。而哈希表需要维护一个桶数组，即使某些桶为空也会占用内存，此外还需要额外的空间来存储链表指针等元数据。因此，map在内存使用上通常更加紧凑。
从内存占用的另一个角度来看，红黑树节点需要存储颜色信息，这通常只需要一个比特位，但为了内存对齐，可能会占用更多空间。相比之下，AVL树节点需要存储平衡因子，通常也需要额外的空间。不过，这个差异相对较小，在实际应用中影响不大。
键类型的要求
map和unordered_map对键类型有不同的要求，这反映了它们底层实现的差异。map需要键类型支持比较操作，因为红黑树需要通过比较键的大小来维持有序性。具体来说，键类型需要实现小于运算符（<），或者提供一个自定义的比较函数。这使得map可以处理任何定义了比较关系的类型。
unordered_map的要求则不同，它需要键类型支持两个操作：哈希和相等比较。键类型需要能够被哈希函数处理，生成一个哈希值，同时需要能够判断两个键是否相等。对于基本类型，标准库已经提供了默认的哈希函数和相等比较；对于自定义类型，我们需要提供自定义的哈希函数和相等比较函数，或者特化相应的模板。
一些面试题
在实际应用中，经常会遇到一些特殊的需求，比如需要不区分大小写的字符串作为键，或者使用自定义的结构体作为键。
对于不区分大小写的字符串键，map可以通过提供自定义的比较函数来实现，这个比较函数会将字符串转换为统一的大小写后再进行比较。unordered_map则需要同时提供自定义的哈希函数和相等比较函数，哈希函数也需要基于统一大小写的字符串来计算，这样才能确保不区分大小写的特性。
当键是结构体或类对象时，map需要为这个类型实现小于运算符，或者提供一个比较函数对象。这个比较函数需要定义一种全序关系，确保能够正确排序。unordered_map则需要同时实现哈希函数和相等比较函数。哈希函数的设计需要特别小心，它应该能够充分利用结构体的各个成员，生成良好的哈希值分布。相等比较函数则需要比较所有相关的成员，确保两个相等的对象能够被正确识别。