C++ 의 해쉬맵 자료구조의 허점(?)

unordered_map, unordered_set 과 같은 해쉬맵 자료구조에서 해쉬값을 만드는데에 사용하는 해쉬 함수의 디폴트가 컴파일러 마다 다른데

MSVC++ 에서는 어떤상황에서든 잘 돌아가는데

G++ 에서는 디폴트 함수가 하위 16비트만 보고 해쉬값을 만들기때문에 해쉬값은같지만 실제 값은 다른 값들이 많이 존재하는 상황이 발생할 수가 있다고 한다. 이런 최악의경우에 시간 복잡도가 O(N) 이 걸리게 된다는 문제가있다..... 

그러므로 입력 데이터가 골고루 나오는경우가 아니거나 hack 이 가능한 탑코더나, 코드포스와 같은 CP 환경에서는 직접 해쉬함수를 정의하여 unordered 의 세번째 인자로 넣어주거나, 굳이 O(1) 에 계산할 필요가없고 편하게 하려면 그냥 set, map 을 쓰자..

세번째 인자로 넣어주는 해쉬맵으로는 이걸 넣으면 된다고한다.

struct hashLL {
    size_t operator()(LL x) const {
        x = (x ^ (x >> 30)) * UINT64_C(0xbf58476d1ce4e5b9);
        x = (x ^ (x >> 27)) * UINT64_C(0x94d049bb133111eb);
        x = x ^ (x >> 31);
        return x;
    }
};

만약 그냥 g++의 디폴트 해쉬 함수를 사용할 경우 이런 코드에서는 원래 해쉬 함수에서는 삽입과 검색이 O(1) 가 걸리므로 O(N) 이 걸릴 거라고 생각하기 쉬운데 위에서 말한 g++의 해쉬 함수의 특성에 따라 O(N^2) 이 걸리게된다.

#include <iostream>
#include <unordered_set>
 
using namespace std;
 
int main() {
    unordered_set<long long> d;
    int n = 1e5;
    long long t = 1LL << 32;
    for (int i = 0; i < n; i++) {
        d.insert(i * t);
    }
    cout << d.size() << endl;
}