unordered_map原理

unordered_map 是 C++ 标准库中的一种关联容器，它提供了一种基于键值对的快速查找和插入操作。其原理是通过哈希表来实现的。

哈希表是一种通过将关键字映射到哈希值来进行快速查找的数据结构。unordered_map 内部维护了一个数组，数组的每个位置称为一个桶(bucket)，每个桶存储了一个链表或者红黑树，用于处理哈希冲突。

当插入一个键值对时，unordered_map 首先使用哈希函数将键转换为哈希值，然后通过取模运算将哈希值映射到对应的桶中。如果该桶为空，则直接插入键值对；如果桶中已经存在一个或多个元素，则需要通过比较键的值来确定是否已经存在相同的键，如果存在则更新值，否则将新的键值对插入到链表或红黑树中。

当查找一个键时，unordered_map 同样使用哈希函数计算键的哈希值，并映射到对应的桶。然后在该桶中搜索键，如果找到了对应的键，则返回其值；如果没有找到，则返回一个特殊值来表示不存在。

由于哈希函数的设计以及桶的数量等因素的不同，unordered_map 的性能可能会受到影响。但平均情况下，unordered_map 提供了常数时间复杂度的插入、查找和删除操作，具有较高的效率。

相关问题

unordered_set、unordered_multiset、unordered_map、unordered_multimap底层原理

unordered_set、unordered_multiset、unordered_map和unordered_multimap的底层原理是基于哈希表实现的。哈希表是一种数据结构，通过将关键字映射到哈希表中的一个位置来快速查找和插入元素。在哈希表中，每个元素被存储在一个桶中，桶的数量和大小根据哈希表的大小和负载因子动态调整。

当插入一个元素时，哈希表首先使用哈希函数计算关键字的哈希值，然后根据哈希值找到对应的桶。如果桶是空的，则直接插入元素；如果桶不为空，则通过开放定址法或链地址法解决冲突，将元素插入到合适的位置。插入操作的平均时间复杂度是常数级别的。

当查找一个元素时，哈希表通过哈希函数计算关键字的哈希值，然后根据哈希值找到对应的桶。如果桶中有元素，则通过比较关键字找到目标元素；如果桶中没有元素，则表示目标元素不存在。查找操作的平均时间复杂度是常数级别的。

删除一个元素的操作也类似于查找操作，先找到元素所在的桶，然后删除元素。删除操作的平均时间复杂度也是常数级别的。

在 C++ 中，如何判断两个 unordered_map 是否相等？unordered_mapA== unordered_mapB 的比较原理

在 C++ 中，判断两个 unordered_map 是否相等，需要比较它们的大小和每个键值对是否相等。具体实现可以使用以下代码：

bool isEqual(unordered_map<int, int>& mapA, unordered_map<int, int>& mapB) {
    if (mapA.size() != mapB.size()) {
        return false;
    }
    for (auto& kv : mapA) {
        auto it = mapB.find(kv.first);
        if (it == mapB.end() || it->second != kv.second) {
            return false;
        }
    }
    return true;
}

其中，`mapA.size() != mapB.size()` 判断两个 unordered_map 的大小是否相等，如果不相等，则直接返回 false。然后遍历 mapA 中的每个键值对，查找 mapB 中是否存在相同的键值对，如果不存在或者值不相等，则返回 false。如果遍历完所有键值对都没有返回 false，则说明两个 unordered_map 相等。

unordered_mapA== unordered_mapB 的比较原理是先比较两个 unordered_map 的大小，如果不相等则直接返回 false。然后遍历 unordered_mapA 中的每个键值对，查找 unordered_mapB 中是否存在相同的键值对，如果不存在或者值不相等，则返回 false。如果遍历完所有键值对都没有返回 false，则说明两个 unordered_map 相等。