해시테이블이란? C++에서 표준 라이브러리로 해시테이블을 지원한다. 해시 테이블은 key-value 형태의 데이터를 빠른 시간복잡도를 보장하는 삽입, 삭제 및 검색 작업을 위한 자료 구조이다. 해시 함수를 사용하여 배열의 인덱스에 키를 매핑하여 작동한다. 배열의 각 인덱스는 동일한 키가 한 인덱스에 매핑되는 충돌을 해결하기 위한 메커니즘을 보유한다. 해시테이블의 자세한 개념이 궁금하다면? 해시테이블을 C++로 직접 구현해보고 싶다면? unordered_map 선언과 주요 메서드 C++에서는 unordered_map으로 이를 지원하는데, 평균적으로 상수 시간에 원소를 삽입/삭제/검색이 가능하다. 보통 키를 기반으로 원소에 대한 빠른 탐색이 필요한 경우 사용한다. key(string) : value(int)..

일반적으로 효율적인 데이터의 저장 방법(직접 주소 테이블) 일반적으로 (key : value) 데이터를 기본 자료구조에 배치하면 탐색에 O(N)이 걸리거나 삽입/삭제에 O(N)이 걸린다. 가장 빠른 방법이 배열의 index로 key를 사용했을 때 탐색에 O(1) 시간이 걸린다. 그러나 key값의 종류가 대략 10^16 정도로 매우 많아지면 똑같이 배열로 구현할 수 있을까? 현실적으로 불가능하다. 혹은 key값이 최대 2000인데 실제 존재하는 key값은 0, 2000 뿐이라면 배열의 1~1999까지의 공간은 낭비된다. 이러한 문제들을 해시 테이블을 통해 해결할 수 있다. 해시 테이블이란? 해시 테이블은 임의의 길이를 가진 key값에 해시함수를 적용해 고정된 크기의 index를 생성하여 그 index에 값..