관리 메뉴
목록2025/11/26 (1)
개발자공부일기
C++ Map vs Unordered_map: 해시 테이블과 트리의 차이
1. 서론 - Hash와 Map의 개요맵(Map)은 키(Key)와 값(Value) 쌍을 저장하는 연관 컨테이너를 말합니다. 한편 해시 테이블(Hash Table)은 키를 해시 함수로 변환하여 나온 해시값을 이용해 데이터를 배열의 특정 위치(버킷)에 저장하는 자료구조입니다. 사실 Map은 인터페이스 혹은 추상 자료구조이고, Hash Table은 그 구현 방식 중 하나입니다. Map vs Unordered_map이라고 쓰여있긴 하지만, 더 정확하게는 이진 탐색 트리 vs 해시 테이블의 차이라고 볼 수 있습니다.C++ 표준 라이브러리에서는 이러한 구조를 각각 `std::map`과 `std::unordered_map` 클래스로 제공합니다. `std::map`은 이진 탐색 트리(레드-블랙 트리) 기반으..
CS지식/자료구조
2025. 11. 26. 20:48