HashMap
-
hash map컴퓨터 과학/자료구조와 알고리즘 2021. 8. 7. 21:51
언어 차원에서 제공하는 알고리즘은 성능, 안정성 등에서 검증이 된 것입니다. 그렇지 않으면 해당 언어의 신뢰도에 치명적인 손상을 입힐 수 있기 때문입니다. 때문에 검증된 이론, 수학적으로 증명된 공식 등을 통해서 구현됩니다. 자료구조는 직접 개발하기 위해 공부한다기 보다는 간단한 기능을 직접 구현해보면서 개념과 기본적인 흐름을 파악하는 데 의의가 있는 것 같습니다. 해시맵은 데이터를 배열에 넣습니다. 그러므로 O(1)의 시간복잡도를 가지지만 데이터가 많아질수록 중복된 해시 코드를 얻게 될 확률이 올라갑니다. 그래서 C++ 표준 라이브러리인 std::unordered_map은 일정 수준 이상에서 std::map보다 성능이 안 나올 수 있습니다. 해시맵은 최악의 경우에는 O(n)까지 성능이 저하될 수 있습니..