前回の記事の最後で「unsigned long long intのハッシュは（size_t = 32ビットの環境で）下位32ビットしか見てない」みたいな事を書きました。

これが本当にそうだとすると、この挙動に依存しているunordered_mapに、下位32ビットが同じ値のキーを送り続けるとアルゴリズムの教科書通りの最悪ケースになって悲惨なことになるのでは…！という事が容易に予想されます。

ということで、やってみました。

実験環境

• Windows 7 64bit
• MinGW 32 g++ 4.8.1

ソースコードはこちら。

#include <unordered_map>
#include <cstdio>
#include <chrono>
unsigned long getT()
{
    return std::chrono::system_clock::now().time_since_epoch() / std::chrono::milliseconds(1);
}
int main()
{
    {
        std::unordered_map<unsigned long long int, int> map;
        unsigned long t = getT();
        for(int j=0;j<100;++j)
        for(unsigned long long int i=0;i<0x1000;++i){
            map.insert(std::make_pair(i << 17, 10));
        }
        printf("Case 1 Time: %d\n", static_cast<int>(getT() - t));
    fflush(stdout);
    }
    {
        std::unordered_map<unsigned long long int, int> map;
        unsigned long t = getT();
        for(int j=0;j<100;++j)
        for(unsigned long long int i=0;i<0x1000;++i){
            map.insert(std::make_pair(i << 33, 10));
        }
        printf("Case 2 Time: %d\n", static_cast<int>(getT() - t));
    fflush(stdout);
    }
}

シフトする値だけ少し変更することで、他の要素の影響を出来る限り減らしました。

結果

g++ -o test -std=gnu++11 test.cpp
./test
Case 1 Time: 120
Case 2 Time: 67825

というわけで500倍くらい遅かったので、本当に線形探索してるっぽいです。本当にありがとうごいました。

64bit環境なら問題ありません

64bit環境のwandboxで実行すると、64bit環境ではsize_tも64ビットになってくれるので、

Start

Case 1 Time: 287
Case 2 Time: 279

0

Finish

というわけでほぼ同じ時間で終わります。