목록해쉬맵 (1)
블로그 옮겼습니다
C++ 의 해쉬맵 자료구조의 허점(?)
unordered_map, unordered_set 과 같은 해쉬맵 자료구조에서 해쉬값을 만드는데에 사용하는 해쉬 함수의 디폴트가 컴파일러 마다 다른데MSVC++ 에서는 어떤상황에서든 잘 돌아가는데G++ 에서는 디폴트 함수가 하위 16비트만 보고 해쉬값을 만들기때문에 해쉬값은같지만 실제 값은 다른 값들이 많이 존재하는 상황이 발생할 수가 있다고 한다. 이런 최악의경우에 시간 복잡도가 O(N) 이 걸리게 된다는 문제가있다..... 그러므로 입력 데이터가 골고루 나오는경우가 아니거나 hack 이 가능한 탑코더나, 코드포스와 같은 CP 환경에서는 직접 해쉬함수를 정의하여 unordered 의 세번째 인자로 넣어주거나, 굳이 O(1) 에 계산할 필요가없고 편하게 하려면 그냥 set, map 을 쓰자.. 세번째 ..
Algorithm/Memo &Tips
2017. 2. 24. 21:40