C++ map和unordered_map有什么区别 红黑树与哈希表的性能对比分析

map基于红黑树实现，保证有序性，适用于需要有序遍历的场景；unordered_map基于哈希表实现，追求平均情况下的快速查找，适用于对性能要求高且不关心顺序的场景。1.map的插入、删除、查找时间复杂度为o(log n)，内存占用较小，支持有序遍历；2.unordered_map平均时间复杂度为o(1)，但受哈希冲突影响可能退化至o(n)，内存占用较大，遍历顺序无序；3.选择map需考虑有序性和稳定性能，选择unordered_map需关注哈希函数质量、负载因子及内存限制；4.自定义哈希函数和相等比较函数可优化unordered_map性能，适应特定应用场景。

简单来说，map基于红黑树实现，保证有序性，而unordered_map基于哈希表实现，追求平均情况下的快速查找。选择哪个取决于你的具体需求，比如是否需要有序遍历，以及对性能的极致要求。

C++ map和unordered_map：底层原理与性能差异

map和unordered_map都是C++中常用的关联容器，用于存储键值对。它们的主要区别在于底层实现和性能特点。

map的底层实现是红黑树（Red-Black Tree），一种自平衡的二叉搜索树。红黑树的特性保证了map中的元素是有序的，插入、删除、查找的时间复杂度都是O(log n)，其中n是map中元素的数量。由于红黑树需要维护平衡，因此在插入和删除操作时会有一定的开销。

立即学习“C++免费学习笔记（深入）”；

unordered_map的底层实现是哈希表（Hash Table）。哈希表通过哈希函数将键映射到表中的一个位置，从而实现快速查找。理想情况下，哈希表的查找、插入、删除的时间复杂度都是O(1)。但实际情况下，由于哈希冲突的存在，时间复杂度可能会退化到O(n)。为了减少哈希冲突，unordered_map会动态调整哈希表的大小，但这也会带来一定的开销。

性能对比：红黑树 vs 哈希表

红黑树和哈希表在性能上有各自的优劣。

• 查找性能： 在平均情况下，哈希表的查找性能优于红黑树，时间复杂度为O(1)。但最坏情况下，哈希表的查找性能会退化到O(n)。红黑树的查找性能稳定，时间复杂度为O(log n)。

• 插入性能： 哈希表的插入性能通常优于红黑树，平均时间复杂度为O(1)。但当哈希表需要扩容时，插入性能会受到影响。红黑树的插入性能稳定，时间复杂度为O(log n)。

• 删除性能： 哈希表的删除性能通常优于红黑树，平均时间复杂度为O(1)。但当哈希表需要缩容时，删除性能会受到影响。红黑树的删除性能稳定，时间复杂度为O(log n)。

• 内存占用： 红黑树的内存占用相对较小，因为它只需要存储节点本身的数据和一些必要的指针。哈希表的内存占用通常较大，因为它需要维护哈希表本身以及解决哈希冲突的数据结构（例如链表或开放寻址）。

• 有序性： 红黑树保证了元素的有序性，可以按照键的顺序进行遍历。哈希表不保证元素的有序性，遍历顺序取决于哈希函数和哈希表的结构。

何时使用map，何时使用unordered_map？

选择map还是unordered_map取决于具体的需求。

• 需要有序性： 如果需要按照键的顺序遍历元素，或者需要使用基于顺序的操作（例如查找小于某个键的第一个元素），则应该使用map。

• 追求极致性能： 如果对性能要求非常高，并且不关心元素的顺序，则应该使用unordered_map。但需要注意，unordered_map的性能依赖于哈希函数的质量和哈希表的负载因子。如果哈希函数选择不当或者负载因子过高，可能会导致性能下降。

• 内存限制： 如果内存资源有限，可以考虑使用map，因为它通常比unordered_map占用更少的内存。

  

  Mintlify

  帮助开发者创建和维护文档

  下载

哈希冲突对unordered_map性能的影响及应对策略

哈希冲突是影响unordered_map性能的关键因素。当多个键被哈希到同一个位置时，就会发生哈希冲突。解决哈希冲突的常用方法包括链地址法和开放寻址法。

• 链地址法： 将哈希到同一个位置的元素存储在一个链表中。查找时，需要先找到对应的链表，然后遍历链表查找目标元素。链地址法的优点是实现简单，缺点是当链表过长时，查找效率会下降。

• 开放寻址法： 当发生哈希冲突时，按照某种规则在哈希表中寻找下一个空闲位置。查找时，也按照相同的规则寻找目标元素。开放寻址法的优点是节省内存空间，缺点是实现复杂，并且容易产生聚集现象，导致性能下降。

为了减少哈希冲突，可以采取以下策略：

• 选择合适的哈希函数： 哈希函数应该能够将键均匀地分布到哈希表中，避免出现大量的哈希冲突。

• 调整负载因子： 负载因子是哈希表中元素的数量与哈希表大小的比值。当负载因子过高时，哈希冲突的概率会增加。可以通过调整负载因子来控制哈希表的性能。unordered_map提供了max_load_factor()函数来设置负载因子。

• 使用自定义的哈希函数和相等比较函数： 可以根据键的特点，自定义哈希函数和相等比较函数，以提高哈希表的性能。

如何自定义unordered_map的哈希函数

自定义哈希函数可以提高unordered_map的性能，特别是当键的类型是自定义类型时。

要自定义哈希函数，需要创建一个类或结构体，并重载operator()运算符。operator()运算符应该接受键作为参数，并返回一个size_t类型的哈希值。

例如，假设有一个自定义类型Person：

struct Person {
    std::string name;
    int age;
};

可以创建一个自定义的哈希函数：

struct PersonHash {
    size_t operator()(const Person& person) const {
        // 使用std::hash组合name和age的哈希值
        size_t nameHash = std::hash{}(person.name);
        size_t ageHash = std::hash{}(person.age);
        return nameHash ^ (ageHash << 1); // 简单地组合哈希值
    }
};

然后，在使用unordered_map时，将自定义的哈希函数作为模板参数传递：

std::unordered_map personMap;

还需要自定义相等比较函数，以确保在哈希冲突时能够正确地比较键是否相等。可以创建一个类或结构体，并重载operator()运算符。operator()运算符应该接受两个键作为参数，并返回一个bool类型的值，表示两个键是否相等。

struct PersonEqual {
    bool operator()(const Person& p1, const Person& p2) const {
        return p1.name == p2.name && p1.age == p2.age;
    }
};

然后，在使用unordered_map时，将自定义的相等比较函数作为模板参数传递：

std::unordered_map personMap;

通过自定义哈希函数和相等比较函数，可以更好地控制unordered_map的性能，并使其适应特定的应用场景。