为什么我的机器上 hash_map 和 unordered_map 的速度非常慢？

Question

我用以下代码对它们进行了测试（在Visual Studio 2010 sp1上）：

#include <ctime>
#include <iostream>
#include <map>
#include <unordered_map>
#include <hash_map>

int main()
{ 
    clock_t time;
    int LOOP = (1 << 16);
    std::map<int, int> my_map;
    std::unordered_map<int, int> map_unordered_map;
    std::hash_map<int, int> my_hash_map;

    time = clock();
    for (int i = 0; i != LOOP; ++i)
    {
        my_map[i] = i;
    }
    std::cout << "map: " << ((double)(clock() - time) / CLOCKS_PER_SEC) << std::endl;

    time = clock();
    for (int i = 0; i != LOOP; ++i)
    {
        map_unordered_map[i] = i;
    }
    std::cout << "unordered_map: " << ((double)(clock() - time) / CLOCKS_PER_SEC) << std::endl;

    time = clock();
    for (int i = 0; i != LOOP; ++i)
    {
        my_hash_map[i] = i;
    }
    std::cout << "hash_map: " << ((double)(clock() - time) / CLOCKS_PER_SEC) << std::endl;

    system("PAUSE");
    return EXIT_SUCCESS;
}

结果非常奇怪：

在DEBUG模式下： map: 0.289 unordered_map: 10.738 hash_map: 10.58 按任意键继续 . . .

在RELEASE模式下： map: 0.101 unordered_map: 0.463 hash_map: 0.429 按任意键继续 . . .

- hythloday

---

可能是std::map的实现特别针对增加键插入，您应该使用随机数进行测试。也可能是2^16太小，无法显示哈希容器的理论优势。 - Mark Ransom

std::map使用红黑树作为其内部数据结构，而std::hash_map使用哈希表。你所看到的可能是随着哈希表增长而重新哈希的成本。如果你清除它们并再次运行相同的插入操作，会发生什么？ - Jens Agby

因为如果我将LOOP设置得更大，它会变得非常慢，所以最终我将其设置为1 << 16，这样我就可以一遍又一遍地运行它来检查问题......只需查看DEBUG模式下的10秒结果即可。 - hythloday

Jens Agby是正确的......如果我在所有元素插入后再循环一次，那么hash_map比map快得多..... - hythloday

添加了一个回答，描述了我们的发现。 - Jens Agby

Answer 1

1. 你每个map只插入了65536个项目--这对于O(log N)和O(1)之间的差异并没有太大意义。
2. 你仅插入项目，之后不进行任何搜索。
3. 你的键都是连续递增的整数--这与通常使用的任何map都不符合。

总之：这不太可能告诉你关于所讨论的数据结构的太多信息。

- Jerry Coffin

---

我稍微修改了代码，首先插入所有元素，然后计算搜索每个元素所需的时间。这次结果符合预期...无论如何还是谢谢您... - hythloday

Answer 2

这是算法摊销成本与最坏情况成本的示例。

std::map使用红黑树，其插入复杂度为O(logN)。
std::hash_map使用哈希表，其插入复杂度为O(1)的摊销复杂度。

然而，当哈希表需要调整大小并重新哈希表时，其最坏情况复杂度为O(N)。

在您的情况下，由于需要进行大量的重新哈希操作，因此哈希表插入操作达到了最坏情况，而树的插入操作变得更快 - O(N) > O(logN)。

如果您使用足够大的表来初始化hash_map，则哈希表永远不会达到最坏情况，它将比树更快 - O(1) < O(logN)。

- Jens Agby

---

所以，在需要经常进行插入和删除的情况下，请使用 map；在一次性加载大量数据，并稍后使用键读取它们时，请使用任何类型的 hash_map，我是对的吗？ - hythloday

并不完全如此。hash_map 的性能取决于提供的哈希函数。如果哈希函数与输入数据不匹配，那么性能可能会非常糟糕。 - timrau

如果你只需要进行插入、查找和删除操作，那么hash_map应该成为你的默认选择。只要确保对你的数据初始化到一个合适的大小，就可以了。 当然，在使用hash_map时需要考虑散列函数和最坏情况等方面。所以请确保你有基本的了解，以免遇到问题。 相比之下，map的优点在于可以按排序顺序非常便宜地迭代数据。如果你不关心排序，那么hash_map应该是你的首选。 - Jens Agby