글 읽기 - HashMap이 이분탐색보다 느린 이유가 뭔가요?

answk427 3년 전 0

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

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

// https://www.acmicpc.net/problem/10816 숫자카드 2
/*********************이분탐색 사용 풀이 *********************
                  메모리 3936KB  시간  436ms                 */
#include <iostream>
#include <algorithm>
using namespace std;
int arr[500002];
int main(void)
{
	int N;
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
	{
		scanf("%d", &arr[i]); //배열에 넣는다
	}
	int M; //M개의 경우 
	scanf("%d", &M);
	sort(arr, arr + N);//정렬
	for (int i = 0; i < M; i++)
	{
		int num;
		scanf("%d", &num);
		
		int* low = lower_bound(arr, arr + N, num);
		int* upper = upper_bound(arr, arr + N, num);
		int result = upper - low;
		printf("%d ", result);
	}
}
/*********************hashMap 사용 풀이 *********************
                  메모리 51568KB  시간  776ms                 */
#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;
int main(void)
{
	int N;
	unordered_map<int,int> map;
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
	{
		int num;
		scanf("%d", &num);
		
		map[num]++;
	}
	int M; 
	scanf("%d", &M);
	for (int i = 0; i < M; i++)
	{
		int num;
		scanf("%d", &num);
		
		printf("%d ", map[num]);
	}
}

39dll 3년 전 0

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

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