어떤 상황에서 std :: unordered_map이 매우 느리게 동작합니까?

Question

몇 가지 임의의 테스트를 수행했지만 결론에 도달하지 못했습니다.

지도와 unordered_map에 1000000 개의 정수를 삽입하면지도에 사용되는 시간은 3 배가됩니다.

1000000 개의 문자열을 삽입하면지도에서 사용한 시간이 2 배 크게됩니다.

어떤 상황에서 std :: unordered_map이 매우 느리게 동작합니까?

미리 감사드립니다.

UPD :: gcc 버전 4.8.4 (Ubuntu 4.8.4-2ubuntu1 ~ 14.04.3). 모든 테스트는 -O2없이 수행되었습니다.

코드 :

a.cpp : std::map<int, int> M; b.cpp : 내 테스트 std::unordered_map<int, int> M;

g(i, 1, 1000000) { 
    M[i] = rand() % i; 
} 

결과 :

yyhs@yyhs-Pro:~/Documents$ g++ a.cpp -o a -g --std=c++11 && time ./a 

real 0m0.659s 
user 0m0.653s 
sys 0m0.004s 
yyhs@yyhs-Pro:~/Documents$ g++ b.cpp -o b -g --std=c++11 && time ./b 

real 0m0.260s 
user 0m0.251s 
sys 0m0.008s 

yyhs@yyhs-Pro:~/Documents$ g++ a.cpp -o a -g --std=c++11 -O2 && time ./a 

real 0m0.290s 
user 0m0.282s 
sys 0m0.008s 
yyhs@yyhs-Pro:~/Documents$ g++ b.cpp -o b -g --std=c++11 -O2 && time ./b 

real 0m0.081s 
user 0m0.081s 
sys 0m0.000s 

여기 내 질문의 경우는 표준 발생할 수 있습니다 것입니다 :: unordered_map이 느려집니다.

Answer 1

평상시와 같이 이것은 특정 구현에 따라 다르지만 이는 사실이 아니며 표준은 std::unordered_map이 점진적으로 std::map보다 우수한 성능을 보임을 보장합니다. 구현에 따라 달라질 수있는 요소는 일정합니다. std::map의 삽입 시간은 O (log N)이고 std::unordered_map의 평균 삽입 시간은 O (1)입니다. 자세한 내용은 n3690의 §23.4.4.1 및 §23.5.4를 참조하십시오.

일반적으로 std::unordered_map은 많은 충돌이 발생하지 않는 한 큰 마진 (관찰 한대로)으로 std::map을 능가합니다. 동일한 버킷에있는 키를 선택하여 충돌을 만들 수 있습니다. 이를 위해서는 해시 함수에 대한 지식과 해쉬 값에서 버킷으로의 매핑이 필요하지만이 지식은 해시 테이블의 키를 제어 할 수 있다면 공격자가 프로그램을 느리게 만들 수 있습니다. 이러한 이유로 노출 된 응용 프로그램에서 무작위 해시 함수를 사용하는 것이 일반적입니다.

병리학 적 경우에 해시 함수가 잘못 선택되거나 (많은 충돌이 발생하는 경우) 또는 std::unordered_map의 경우 병력이있는 경우 std::map의 성능이 우수 할 수 있습니다. 이것은 극히 예외적입니다.

표준 라이브러리 std::unordered_map은 반복자 동작과 관련하여 C++ 표준의 요구 사항을 충족시키기 위해 개방형 해시 테이블이되는 경향이 있습니다. 이것은 많은 응용 프로그램에서 최적의 것으로부터 멀리 떨어져있는 것으로 알려져 있으며 더 나은 성능을 발휘하는 여러 가지 해시 테이블 라이브러리가 있습니다.