C++ unordered_map rehash详解|极客笔记

C++ unordered_map rehash详解

在C++标准库中，unordered_map是一种关联容器，它提供了快速的查找和插入操作。在使用unordered_map时，一个关键的考虑因素是其哈希表的大小和性能。在本文中，我们将详细讨论unordered_map中的rehash操作，探讨如何手动触发rehash以及如何优化rehash的性能。

1. unordered_map简介

首先，让我们简要回顾一下unordered_map的基本概念。unordered_map是一个键值对的集合，其中每个键都是唯一的。它基于哈希表实现，可以实现平均O(1)的插入、查找和删除操作。

以下是一个简单的示例代码，演示如何使用unordered_map：

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> myMap;

    myMap["apple"] = 5;
    myMap["banana"] = 3;
    myMap["cherry"] = 8;

    std::cout << "The value of banana is: " << myMap["banana"] << std::endl;

    return 0;
}

上述代码中，我们创建了一个unordered_map对象myMap，并插入了三组键值对。然后，我们通过键”banana”查找其对应的值，并输出。

2. rehash操作

在unordered_map中，当哈希表中的元素数量达到一定阈值时，会触发rehash操作。rehash操作指的是将哈希表中的元素重新散列到一个更大的桶数组中，从而减少冲突的概率。

默认情况下，unordered_map在rehash时会选择一个大于当前元素数量的最小质数作为新的桶数组大小。这种选择保证了rehash后哈希表的性能会得到提升。

虽然unordered_map会自动触发rehash操作，但我们也可以手动调用unordered_map的rehash方法，强制进行rehash操作。rehash方法会将哈希表的大小调整为参数指定的大小，并重新散列所有元素。

以下是一个示例代码，展示如何手动调用rehash方法：

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> myMap;

    myMap.reserve(20); // 预留20个桶

    // 插入若干元素...

    myMap.rehash(50); // 手动进行rehash，将桶数组大小调整为50

    return 0;
}

在上述示例中，我们通过reserve方法预留了20个桶，然后通过rehash方法手动将桶数组大小调整为50。这样做可以提前为unordered_map分配足够的内存，避免频繁的rehash操作。

3. rehash性能优化

虽然unordered_map的rehash操作可以提升插入、查找和删除的性能，但频繁的rehash操作也会带来一定的开销。因此，在实际应用中，我们应该尽量避免不必要的rehash操作，或者优化rehash的性能。

一种优化rehash性能的方法是在rehash前禁用自动rehash。我们可以通过unordered_map的reserve方法设置一个较大的容量，使其不会在插入新元素时触发rehash操作。待所有元素插入完毕后，再手动调用rehash方法进行rehash。

以下是一个示例代码，展示禁用自动rehash的方法：

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> myMap;

    myMap.reserve(100); // 预留100个桶，禁用自动rehash

    // 插入若干元素...

    myMap.rehash(150); // 手动进行rehash

    return 0;
}

在上述示例中，我们通过reserve方法预留了100个桶，以禁用自动rehash。当所有元素插入完毕后，再手动调用rehash方法将桶数组大小调整为150。

另外，我们还可以通过调整unordered_map的负载因子来优化rehash性能。负载因子是哈希表中元素数量与桶数组大小的比值，当负载因子超过一定阈值时，会触发rehash操作。通过设置合适的负载因子，可以避免过早或过晚触发rehash操作，从而提高性能。