32bit GCCのunordered_mapに下位32ビットが同じキーを送り続けると死ぬ

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

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

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

実験環境

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

ソースコードはこちら。

#include 
#include 
#include 

unsigned long getT()
{
    return std::chrono::system_clock::now().time_since_epoch() / std::chrono::milliseconds(1);
}

int main()
{
    {
        std::unordered_map 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(getT() - t));
		fflush(stdout);
    }
    {
        std::unordered_map 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(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

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