C++ Study. stl unordered_set

1. 소개

• **std::unordered_set**은 C++ STL의 일부로 해시 테이블을 기반으로 하는 무순서 집합을 구현한 컨테이너입니다.
• 해시 함수를 사용하여 빠르게 요소에 접근할 수 있어서 검색, 삽입, 삭제 작업이 상수 시간에 이루어집니다.
• C++11부터 도입되었으며, 해시맵(std::unordered_map)과 비슷한 방식으로 동작합니다.

2. 특징

2.1 무순서성

• 순서가 없는 집합이기 때문에 요소의 순서가 유지되지 않습니다.
• 따라서 범위 기반 루프 등에서 예상한 순서대로 순회되지 않습니다.

2.2 중복 허용되지 않음

• 각 요소는 유일해야 합니다. 중복된 요소는 하나로 취급됩니다.

2.3 해시 함수 사용

• 해시 함수를 통해 각 요소를 버킷으로 매핑하므로 상수 시간 내에 요소에 접근할 수 있습니다.

3. 사용법

#include <unordered_set>

int main() {
	std::unordered_set<int> mySet = {1, 2, 3, 4, 5};
	
	mySet.insert(6);  // 요소 추가
	mySet.erase(3);   // 요소 삭제

	auto it = mySet.find(4);
	if (it != mySet.end()) {
	    // 요소가 찾아졌을 때의 처리
	}

	// 중복 제거
	std::vector<int> vec = {1, 2, 2, 3, 4, 4, 5};
	std::unordered_set<int> uniqueSet(vec.begin(), vec.end());

 

버킷

해시테이블은 내부적으로 배열로 구현되어 있다. 이 배열의 각각의 원소는 버킷이라는 링크드리스트의 헤드를 가리키는 포인터이다.

해시테이블은 모듈러 연산을 하는 해시함수를 이용해서 나머지값을 인덱스로 삼는다 → 원소를 마구 넣을 시 이미 채워진 인덱스에 접근해서 충돌날 가능성이 높아진다.

충돌 해결 방법

1. 개방 주소법:
   • 선형 조사 (Linear Probing): 충돌이 발생하면 선형적으로 다음 버킷을 확인하며 빈 공간을 찾아 삽입합니다.
   • 이차 조사 (Quadratic Probing): 충돌이 발생하면 제곱수만큼 건너뛰어 새로운 위치를 찾아 삽입합니다.
   • 이중 해싱 (Double Hashing): 충돌이 발생하면 또 다른 해시 함수를 이용하여 다른 위치를 찾아 삽입합니다.
2. 체이닝 (Chaining) → c++ unordered_set에 적용된 방법
   • 각 버킷에 연결 리스트를 구성하여 충돌이 발생하면 해당 버킷의 연결 리스트에 노드를 추가합니다.
   • C++ 표준 라이브러리에서는 체이닝 방식을 주로 사용합니다.

체이닝해서 버킷에 원소 연결시켜가다가 어느 임계점 이후로는 더 큰 해시테이블로 이동해야 한다 → rehash

• 이 임계점을 나타내는 지표 = 로드팩터

로드 팩터 = 전체 원소 개수 / 버킷 개수

• 예) max로드팩터 = 0.75이고 원소 개수=4개, 버킷개수=4개일 때 → 현재 로드팩터 = 4/4 = 1 > 0.75이므로 리해시 필요
• c++에서 unordered_set의 default max load_factor는 1.0이다(원소개수 == 버킷개수 되면 리해싱 자동으로 일어남)

unordered_set에 원소 추가할수록 로드펙터 증가하고, 이 값이 max_load_factor값을 초과할 경우 자동으로 rehash됨(메모리에서 더 큰 해시테이블 공간을 할당해서 여기에 기존 원소들을 새 해시함수 이용해서 버킷에 넣기)

 

자동 리해싱 일어나는 코드

#include <iostream>
#include <unordered_set>

int main() {
    // Create an unordered_set with a custom load factor of 0.75
    std::unordered_set<int> mySet(10);  // Initial number of buckets is 10
    mySet.max_load_factor(0.75);

    // Insert elements and trigger rehashing when load factor exceeds 0.75
    for (int i = 0; i < 100; ++i) {
        mySet.insert(i);
    }

    return 0;
}

• 버킷은 링크드리스트로 구현되는데도 rehash 필요하나?(충돌나도 어차피 연결해서 삽입 가능하지않나?)
• -> 충돌발생시 링크드리스트에 연결되는 방식이라서 리스트가 길어지면 검색 및 삽입시 성능 떨어뜨릴 수 있어서 적절한 시점에서 rehashing을 통해 버킷의 수를 늘리고 링크드리스트의 길이를 줄이면 좋다.

다양한 함수를 지원함