Fundamental of CS/: : C++

[Set, Map / Hash] std::unordered_set

Jay.P Morgan 2024. 7. 31. 20:33

 

 

1. std::unordered_set이란?

이번에는 std::unordered_set에 대해 알아보겠습니다.

이전에 알아본 std::set은 내부적으로 트리(Red-Black Tree) 구조를 사용하기 때문에,

  • insert()
  • erase()
  • find()

모두 O(log N)의 시간 복잡도를 가집니다.

 

반면 std::unordered_set은 해시(Hash)를 사용하기 때문에 평균적으로

  • insert()
  • erase()
  • find()

모두 O(1)의 시간 복잡도를 가집니다.

 

 

2. std::unordered_set의 특징

std::unordered_set은 <unordered_set> 헤더에 정의되어 있으며, 주요 특징은 다음과 같습니다.

  • 중복되지 않는(Unique) 데이터를 저장합니다.
  • 내부적으로 Hash Function을 사용합니다.
  • KeyEqual을 이용해 동일한 키인지 비교합니다.
  • 데이터는 정렬되지 않습니다.
  • find(), insert(), erase()는 평균 O(1)의 시간 복잡도를 가집니다.

즉, set처럼 정렬된 트리를 유지하는 것이 아니라 해시 버킷(Bucket) 에 데이터를 저장합니다.

 

 

3. 데이터는 어떻게 저장될까?

예를 들어 다음과 같이 문자열을 저장한다고 가정해 보겠습니다.

unordered_set<string> s;

s.insert("ABC");
s.insert("DEF");
s.insert("GHI");
s.insert("JKL");

출력해 보면 입력한 순서와도 다르고, 사전순도 아닌 순서로 출력됩니다.

이는 unordered_set이 정렬을 하지 않기 때문입니다.

각 문자열은 Hash Function을 통해 하나의 해시값(Hash Value)으로 변환되고,

그 해시값을 이용하여 어느 버킷(Bucket)에 저장할지 결정합니다.

 

 

4. 해시(Hash)와 버킷(Bucket)

해시 함수는 다음과 같은 성질을 가집니다.

  • 같은 입력은 항상 같은 해시값을 생성합니다.
  • 다른 입력은 가능한 한 다른 해시값을 생성합니다.
  • 서로 다른 입력이 같은 해시값을 갖는 충돌(Collision) 은 매우 드물어야 합니다.

예를 들어

"ABC" → Hash Value
"DEF" → Hash Value
"GHI" → Hash Value

와 같이 문자열마다 고유한 해시값이 계산됩니다.

하지만 해시값 자체는 매우 큰 숫자이므로 그대로 사용할 수 없습니다.

그래서 Bucket Count를 이용하여

Bucket = Hash Value % Bucket Count

와 같은 방식으로 저장할 버킷을 결정합니다.

예를 들어 버킷이 13개라면

ABC → Bucket 4
DEF → Bucket 7
GHI → Bucket 4

처럼 서로 같은 버킷에 저장될 수도 있습니다.

 

 

 

5. 충돌(Collision)과 시간 복잡도

만약 서로 다른 데이터가 같은 버킷으로 들어오면 Collision이 발생합니다.

이 경우 하나의 버킷 내부에서는 일반적으로 연결 리스트(또는 구현체에 따라 다른 구조)를 이용하여 데이터를 저장합니다.

예를 들어

Bucket 4
 ├── ABC
 └── GHI

처럼 연결됩니다.

find("ABC")를 수행하면

  1. "ABC"의 해시값을 계산합니다.
  2. 버킷 번호를 계산합니다.
  3. 해당 버킷만 탐색합니다.

전체 데이터를 모두 탐색하지 않기 때문에 평균적으로 O(1)에 검색할 수 있습니다.

insert()와 erase()도 동일한 방식으로 평균 O(1)의 시간 복잡도를 가집니다.

 

 

6. 리해싱(Rehashing)과 reserve()

데이터가 계속 증가하면 하나의 버킷에 저장되는 원소 수도 많아집니다.

예를 들어

Bucket Count = 13
Element = 100

처럼 원소가 많아지면 충돌이 증가하여 성능이 떨어집니다.

이를 방지하기 위해 unordered_set은 버킷 개수를 자동으로 증가시키는데, 이를 리해싱(Rehashing) 이라고 합니다.

리해싱이 발생하면

  • 버킷 개수를 늘리고
  • 모든 데이터를 다시 해싱하여 재배치합니다.

이 과정은 O(N)의 시간 복잡도를 가집니다.

리해싱을 줄이려면 미리 충분한 공간을 확보하는 것이 좋습니다.

unordered_set<int> s;
s.reserve(10000);

처럼 reserve()를 사용하면 예상되는 원소 개수에 맞게 버킷을 미리 확보할 수 있어 불필요한 리해싱을 줄일 수 있습니다.

또한 Load Factor(원소 수 ÷ 버킷 수)가 일정 값을 넘으면 리해싱이 발생하며, max_load_factor()를 통해 이 기준을 조정할 수도 있습니다.

 

 

최종 정리

  • std::unordered_set은 해시 테이블 기반의 컨테이너이며 데이터를 정렬하지 않습니다.
  • 내부적으로 Hash Function과 Bucket을 이용하여 데이터를 저장합니다.
  • find(), insert(), erase()는 평균 O(1)의 시간 복잡도를 가집니다.
  • 서로 다른 데이터가 같은 버킷으로 들어가면 Collision이 발생하며, 버킷 내부에서 관리됩니다.
  • 데이터가 많아지면 Rehashing이 발생하며 O(N)의 비용이 듭니다.
  • reserve()를 사용해 충분한 버킷을 미리 확보하면 리해싱 횟수를 줄여 성능을 향상시킬 수 있습니다.

 



 

 

std::unordered_set(해시 셋) 정리

1. unordered_set이란?

  • std::unordered_set은 해시(Hash) 기반으로 구현된 컨테이너이다.
  • 헤더: #include <unordered_set>
  • 중복을 허용하지 않는(Set) 컨테이너이며, 내부적으로 정렬되지 않는다.
  • 평균 시간 복잡도
    • insert() : O(1)
    • find() : O(1)
    • erase() : O(1)

set은 트리 기반이라 O(log N), unordered_set은 해시 기반이라 평균 O(1)이다.

2. set과 unordered_set의 차이

setunordered_set

균형 이진 탐색 트리(Red-Black Tree) 기반 해시 테이블(Hash Table) 기반
자동 정렬 정렬되지 않음
중복 불가 중복 불가
탐색/삽입/삭제 : O(log N) 평균 O(1)

3. 해시(Hash)란?

해시는 입력값(Key)을 일정한 크기의 숫자(Hash Value)로 변환하는 함수이다.

좋은 해시 함수의 특징

  • 같은 입력 → 항상 같은 해시값
  • 다른 입력 → 가능한 다른 해시값
  • 서로 다른 입력이 같은 해시값을 가질 확률(충돌)이 매우 낮음

C++에서는 std::hash를 기본 제공하며, 반환형은 size_t이다.

4. unordered_set의 저장 방식

unordered_set은 원소를 해시값을 이용해 버킷(Bucket)에 저장한다.

예를 들어 다음과 같이 문자열을 저장한다고 가정하면,

ABC
DEF
GHI
JKL

각 문자열은

ABC → hash() → 큰 숫자
DEF → hash() → 큰 숫자
GHI → hash() → 큰 숫자
JKL → hash() → 큰 숫자

와 같이 해시값을 가진다.

하지만 해시값은 매우 크므로 그대로 배열 인덱스로 사용할 수 없다.

따라서

버킷 번호 = hash(key) % bucket_count

와 같은 방식으로 버킷 번호를 계산하여 저장한다.

5. 버킷(Bucket)과 충돌(Collision)

예를 들어 버킷이 13개라면

ABC → Bucket 4
DEF → Bucket 7
GHI → Bucket 4

처럼 서로 다른 데이터가 같은 버킷으로 들어갈 수 있다.

이를 해시 충돌(Hash Collision)이라고 한다.

충돌이 발생하면 해당 버킷 내부에서 연결 리스트(또는 구현체에 따라 다른 구조)로 데이터를 관리한다.

Bucket 4
 ├── ABC
 └── GHI

6. 왜 평균 O(1)인가?

예를 들어 "ABC"를 찾는 과정은 다음과 같다.

  1. "ABC"의 해시값 계산
  2. 버킷 번호 계산
  3. 해당 버킷만 확인
  4. 버킷 내부에서 원소 검색

전체 과정이 매우 짧기 때문에

  • find()
  • insert()
  • erase()

모두 평균 O(1)의 시간 복잡도를 가진다.

7. 리해싱(Rehashing)

원소가 계속 증가하면 버킷 하나에 너무 많은 데이터가 몰리게 된다.

Bucket 4
 ├── ABC
 ├── GHI
 ├── XYZ
 ├── ...

이렇게 되면 버킷 내부 탐색 시간이 증가하여 성능이 저하된다.

이를 방지하기 위해 버킷 개수를 늘리고 데이터를 다시 배치하는 작업을 수행하는데, 이를 리해싱(Rehashing)이라고 한다.

  • 리해싱 시간 복잡도 : O(N)

8. reserve()와 Load Factor

리해싱은 비용이 크므로 가능한 줄이는 것이 좋다.

reserve()

예상되는 데이터 개수를 미리 알려주면 충분한 버킷을 확보하여 리해싱 횟수를 줄일 수 있다.

unordered_set<int> s;
s.reserve(10000);

Load Factor

로드 팩터는

Load Factor = 원소 개수 / 버킷 개수

예를 들어

  • 버킷 100개, 원소 100개 → Load Factor = 1.0
  • 버킷 100개, 원소 50개 → Load Factor = 0.5

로드 팩터가 최대값(max_load_factor)을 넘으면 자동으로 리해싱이 발생한다.

핵심 정리

  • unordered_set은 해시 테이블 기반의 컨테이너이다.
  • 중복을 허용하지 않으며, 자동 정렬되지 않는다.
  • find(), insert(), erase()는 평균 O(1)이다.
  • 원소는 해시값 → 버킷 번호를 계산하여 저장된다.
  • 같은 버킷에 여러 원소가 들어가면 충돌(Collision)이 발생하며 버킷 내부에서 관리된다.
  • 원소가 많아지면 리해싱(O(N))이 발생하여 버킷 수를 늘리고 데이터를 재배치한다.
  • reserve()를 사용하면 미리 버킷을 확보하여 리해싱을 줄여 성능을 향상시킬 수 있다.

 

 

 

 

unordered_set 

1. unordered_set이란?

  • set은 균형 이진 탐색 트리(Red-Black Tree) 기반으로 구현된다.
  • 따라서 삽입(Insert), 삭제(Erase), 탐색(Find) 의 시간 복잡도는 모두 O(log N) 이다.
  • 반면 unordered_set 은 해시(Hash) 를 사용하므로 평균적으로
    • 삽입 : O(1)
    • 삭제 : O(1)
    • 탐색 : O(1)
      의 시간 복잡도를 가진다.

 

 

2. unordered_set의 특징

헤더

#include <unordered_set>

주요 특징

  • 중복을 허용하지 않는(Set) 컨테이너
  • 원소는 정렬되지 않는다.
  • 원소는 해시값(Hash Value) 에 따라 버킷(Bucket) 에 저장된다.
  • 평균적으로 Search / Insert / Erase가 Constant Time(O(1)) 이다.

예를 들어

unordered_set<string> s;

s.insert("ABC");
s.insert("DEF");
s.insert("GHI");
s.insert("JKL");

출력하면

GHI
ABC
JKL
DEF

처럼 입력 순서나 정렬 순서가 아닌 임의의 순서로 출력될 수 있다.

3. 해시(Hash)와 버킷(Bucket)

해시 함수(Hash Function)

해시 함수는 입력값을 하나의 정수(Hash Value)로 변환한다.

좋은 해시 함수의 조건

  • 같은 입력 → 항상 같은 해시값
  • 다른 입력 → 가능한 서로 다른 해시값
  • 해시 충돌(Hash Collision)은 매우 적어야 한다.

예를 들어

ABC → 356734...
DEF → 129347...
GHI → 872349...

처럼 각각의 문자열은 서로 다른 해시값을 갖는다.

C++에서는

std::hash<T>

를 통해 해시값을 생성한다.

4. 버킷(Bucket)과 충돌(Collision)

해시값은 매우 큰 숫자이므로 그대로 인덱스로 사용할 수 없다.

그래서 내부적으로

Bucket Count = 13

이라면

Hash Value
        ↓
Bucket Number (0 ~ 12)

로 변환하여 저장한다.

예시

ABC → Bucket 4
DEF → Bucket 7
GHI → Bucket 4

처럼 서로 다른 데이터가 같은 버킷으로 들어갈 수도 있다.

이를 해시 충돌(Hash Collision) 이라고 한다.

이 경우 같은 버킷 안에서 연결 리스트(또는 유사한 연결 구조) 로 데이터를 관리한다.

5. 왜 평균 O(1)인가?

예를 들어

find("ABC")

를 수행하면

  1. "ABC"의 해시값 계산
  2. 버킷 번호 계산
  3. 해당 버킷만 확인

하면 되므로 전체 데이터를 탐색할 필요가 없다.

따라서 평균적으로

  • Insert : O(1)
  • Erase : O(1)
  • Find : O(1)

이 된다.

단, 충돌이 많아지면 같은 버킷의 연결 리스트가 길어져 성능이 저하될 수 있다.

6. 리해싱(Rehashing)

원소가 계속 증가하면 버킷 하나에 너무 많은 원소가 저장된다.

예를 들어

Bucket Count
13
→
29

처럼 버킷 개수가 증가하면서

기존 모든 원소를 새로운 버킷으로 다시 배치한다.

이를 리해싱(Rehashing) 이라고 한다.

리해싱의 시간 복잡도는

O(N)

이다.

7. reserve()와 Load Factor

리해싱이 자주 발생하면 성능이 떨어진다.

미리 충분한 공간을 확보하려면

unordered_set<int> s;
s.reserve(10000);

처럼 reserve()를 사용한다.

그러면 처음부터 충분한 버킷을 확보하여 리해싱 횟수를 줄일 수 있다.

Load Factor

로드 팩터는

Load Factor =
원소 개수 / 버킷 개수

예를 들어

  • 버킷 100개, 원소 100개 → 1.0
  • 버킷 100개, 원소 50개 → 0.5

max_load_factor()를 초과하면 자동으로 리해싱이 발생한다.

기본값은 일반적으로 1.0이다.

8. set과 unordered_set 비교

항목setunordered_set

내부 구조 Red-Black Tree Hash Table
정렬 O X
중복 허용 X X
탐색 O(log N) 평균 O(1)
삽입 O(log N) 평균 O(1)
삭제 O(log N) 평균 O(1)
최악의 경우 O(log N) O(N) (충돌이 많을 경우)

9. 핵심 정리

  • unordered_set은 해시 테이블 기반의 컨테이너이다.
  • 원소는 정렬되지 않고, 해시값을 이용해 버킷에 저장된다.
  • 평균적으로 삽입, 삭제, 탐색이 모두 O(1) 이다.
  • 동일한 버킷에 여러 원소가 저장되는 현상을 해시 충돌(Hash Collision) 이라고 한다.
  • 원소가 많아지면 리해싱(O(N)) 이 발생한다.
  • reserve()를 사용하면 미리 버킷을 확보하여 리해싱을 줄일 수 있다.
  • max_load_factor()는 리해싱이 발생하는 기준(로드 팩터)을 결정한다.



 

 

 

'Fundamental of CS > : : C++' 카테고리의 다른 글

[Set, Map / Hash] std::unordered_map  (0) 2024.07.31
[Set, Map / Hash] Hash Set과 Custom Class  (0) 2024.07.31
[Set, Map / Hash] std::map  (0) 2024.07.31
[Set, Map / Hash] std::multi_set  (0) 2024.07.31
[Set, Map / Hash] std::set  (0) 2024.07.31

'Fundamental of CS/: : C++'의 다른글

  • 현재글[Set, Map / Hash] std::unordered_set

관련글

티스토리툴바