해쉬 테이블을 기반한 자료 구조 Hash Set

데이터를 빠르게 검색하고 관리해야 하는 경우 해시 테이블을 기반으로 한 해시 세트는 매우 유용하게 사용된다. 해시 세트는 주로 데이터의 존재 여부를 빠르게 확인할 수 있도록 설계되었으며, 각 데이터 항목은 해시 함수를 통해 계산된 고유한 해시 코드를 이용해 저장 위치가 결정된다. 이 키는 고유해야 하기 때문에 중복된 항목을 허용하지 않는다.

작동원리

1. 해시 함수: 해시 세트는 해시 함수를 사용해 입렫횐 키의 해시 값을 계산한다. 이 해시 값은 요소가 저장될 버킷(위치)를 결정하는 데 사용됨.
2. 버킷 할당: 계산된 해시 값에 따라 각 키는 특정 버킷에 저장되는데, 버킷 수는 고정되어 있지 않고 데이터의 양에 따라 동적으로 조정될 수 있음.
3. 충돌 해결: 두 개 이상의 키가 동일한 버킷에 할당될 경우를 충돌이라 하는데, 이러한 충돌을 체이닝 방식 등으로 해결함.

해시 세트의 장점

• 빠른 접근 속도: 평균적으로 O(1)의 시간 복잡도로 데이터의 존재 여부를 확인할 수 있음.
• 데이터 관리 효율성: 중복 데이터를 자동으로 제거하므로 데이터 관리가 용이함.
• 동적 크기 조정: 데이터의 양에 따라 내부 버킷의 크기가 조정되므로 메모리 사용이 효율적임.

C++ 표준 라이브러리에서 제공하는 해시 테이블 기반의 자료구조

• unordered_set : 값을 저장하는 해시 테이블 기반의 자료구조
• unordered_map : 키-값 쌍을 저장하는 해시 테이블 기반의 자료구조
• unordered_multiset : unordered_set과 유사하지만, 중복된 요소를 저장할 수 있음
• unordered_multimap : unordered_map과 유사하지만, 중복된 요소를 저장할 수 있음