answk427   1년 전

해쉬맵이 검색시간이 상수시간이고

이분탐색은 logN 으로 알고있는데 왜 해쉬맵이 느린지 궁금합니다.

39dll   1년 전

아래 내용은 순전히 제 추측입니다.

unordered_map은, 들어온 key를 그대로 사용하지 않고, C++ 내부의 hash 함수를 이용해서 hash값으로 바꿔준 후 저장하고, 탐색도 이와 비슷합니다. 이 hash값을 구하는 비용과 탐색하는 비용이 logN(N이 50만일 때, 약 19)보다 커져서 unordered_map이 이분 탐색보다 더 느리게 작동되지 않았나 추측됩니다.

cgiosy   1년 전

현실 세계에서는 N이 무한히 큰 경우가 거의 없기 때문에 O(lgN)과 O(1) 정도의 차이는 N의 크기에 따라 시간복잡도에 붙은 상수로 자주 뒤집어집니다.

가령, 최소한의 비교로 원하는 수를 찾아야 하는 가상의 문제가 있다고 합시다.

N에 관계없이 항상 50번의 비교로 수를 찾는 어떤 O(1) 알고리즘과 N에 대해 ceil(lgN)번의 비교를 하는 O(lgN) 알고리즘이 있으면,

복잡도만 봤을 때는 O(1)이 나음에도 불구하고, N이 조 단위를 넘어가지 않는 이상 O(lgN)이 O(1)보다도 빠릅니다.

이런 상황은 심지어 O(N)과 O(N^2)같이 시간복잡도가 크게 차이나는 경우에도 자주 일어납니다.

해시맵, 그 중에서도 C++의 unordered_map이 어느 부분에서 큰 상수를 가지는지 궁금하시다면, 다음 동영상과 링크들이 도움이 될 것 같습니다.



GCC의 실제 구현:

bits/hashtable.h

hashtable_policy.h

minjoonist   1년 전

아하.. 그럼 오히려 N이 클수록 O(1)이 유리해지는 건가요?

answk427   11달 전

정말 감사합니다

엄청난 답변이네요.

댓글을 작성하려면 로그인해야 합니다.