GW LABS

세 번째 C++ 세 번째 포스팅은 해시맵이다. 해시맵은 실무에서도 다양하게 응용되는 친숙한 자료구조이다. 어떤 내부구조를 갖고 있는지 함께 알아보자! 1. Hashmap (해시 맵, 해시 테이블) 해시맵은 키를 통해 어떤 값을 찾기 위한 자료구조이다. 다양한 형태로 응용할 수 있고, 알고리즘 문제 뿐만 아니라 실무에서도 유용하게 사용한다. 해시맵은 읽기, 쓰기, 삭제 모두 평균적으로 O(1)에 수행할 수 있다. 어떻게 이런 시간복잡도가 가능할까? 2. Hasing 해시맵을 이해하기 위해선 먼저 해싱을 알아야한다. 해싱은 해쉬함수를 이용해서 키를 숫자로 변환하는 과정이다. 이렇게 생성된 키는 해쉬맵 내부에 있는 자료구조 방 번호가 된다. 얻어진 방 번호를 통해 값을 저장하고, 찾고, 삭제하면 되는 것이다...