맵과 해시맵의 시간 복잡도와 해시맵이 더 빠른 이유

 

 

1. 맵과 해시맵의 시간 복잡도

맵의 시간 복잡도는 O(logN)의 탐색 속도를 가지며, 해시 맵의 시간 복잡도는 O(1)의 탐색 속도를 가집니다. 대부분의 경우 맵과 해시맵은 기본 데이터 구조를 해시 테이블을 사용하므로, 특정 값을 찾는 데 걸리는 시간 복잡도는 평균 O(1)입니다. 그렇지만, 시간 복잡도는 컨테이너 및 기본 데이터 구조의 구현에 따라 다릅니다.

그러나 만약 해시 테이블이 충돌하는 경우와 같은 특수 경우 특정 값을 찾는 시간 복잡도는 O(n)일 수 있습니다. 여기서 n은 컨테이너의 요소 수입니다. 이 경우 값을 찾는 데에 시간이 보다 더 걸릴 수 있으며, 이는 컨테이너의 크기가 커질수록 더 오래 걸립니다.

요약하면 맵 혹은 해시 맵 컨테이너 내에서 특정 값을 찾는 시간 복잡도는 스토리지에 사용되는 컨테이너 및 기본 데이터 구조의 구현에 따라 다릅니다. 대부분의 경우 값을 찾는 시간 복잡도는 평균적으로 O(1)이지만 경우에 따라 O(n)이 될 수도 있습니다.

 

2. 해시맵이 더 빠른 이유

해시 맵과 맵은 유사한 데이터 구조이며 성능은 위에서 얘기한 것과 같이 컨테이너의 구현 및 크기를 비롯한 여러 요인에 따라 달라집니다.

일반적으로 해시 맵은 특정 값을 찾기 위한 평균 시간 복잡도가 O(1)이므로 맵보다 빠를 수 있습니다. 반면에 맵은 조회에 대해 O(log n)의 시간 복잡도를 갖는 경우가 많습니다.  그러나 만약, 해시 테이블이 충돌을 겪고 특정 값을 찾는 시간 복잡도가 O(n)이 되는 경우와 같은 특정 상황의 경우에는 해시 맵이 맵보다 느릴 수 있습니다.

조회 이외에도 맵과 해시 맵은 삽입, 삭제 및 반복과 같은 다른 작업에 대해 다른 성능 특성을 가질 수 있습니다. 데이터 구조의 특정 요구 사항 및 성능 특성에 따라 당면한 작업에 적합한 데이터 구조를 선택하는 것이 중요합니다.

 

3. 결론
요약하면 해시 맵은 조회용 맵보다 빠를 수 있지만 성능은 구현 및 컨테이너 크기를 비롯한 여러 요인에 따라 달라지며 경우에 따라 맵보다 느릴 수 있습니다. 특정 작업에 가장 적합한 데이터 구조는 데이터 구조의 특정 요구 사항 및 성능 특성에 따라 다릅니다.

 

 

---

 

 

참고자료

https://gracefulprograming.tistory.com/3

[C++] map vs hash_map(unordered_map)