4

我用这段代码测试了它们（在 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 按任意键继续。. .

4

2 回答 2

6
  1. 您只在每个地图中插入 65536 个项目 - 不足以让 O(log N) 和 O(1) 之间的差异意味着很多。
  2. 您只是插入项目，之后不进行任何搜索。
  3. 您的键都是按递增顺序排列的连续整数 - 不适合任何地图的通常使用方式。

底线：这不太可能告诉您有关数据结构的很多信息。

于 2012-08-30T16:46:17.197 回答
1

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

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

但是，当必须调整表大小并重新散列表时，散列表的最坏情况复杂度为 O(N)。

在您的情况下，您最终会进行大量重新散列，因此哈希表插入达到了最坏的情况，以至于树插入变得更快 - O(N) > O(logN)。

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

于 2012-08-30T17:15:34.010 回答