[C++] unordered_set

특징

1. 자동적으로 정렬되지 않는다.

2. hash 사용으로 bucket 으로 인해 메모리 사용량 증가

3. insertion, deletion, find O(1)에 수행, 다만 충돌이 너무 많이 일어나면 O(N)

(그러면 기존 set 보다 더 느리게 수행될 수 있다는 말이다.)

4. hash 자료구조를 사용한다.

 

원소의 개수가 많을수록 해시 충돌이 일어날 확률도 많아지게 되므로

경우에 따라 사용하자.

 

원소의 개수가 적고 빠른 성능 : unordered_set

원소의 개수가 많고 안정성 : set

Hash function

정의는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수.

unordered_set 에 특정 value 를 찾거나 넣을 때 해당 value 를 hash function 에 넣고 나온 리턴 값인

hash value 를 얻는다.

 

기본적으로  hash value 는 bucket 에 들어가는 index 보다 크기 때문에 bucket 의 size 로 나머지 연산을 하여서 최종 index 를 얻고 그 bucket[index] 에 해당 value 를 저장하게 된다.

 

1. value -> hash function -> hash value(해시 값)

2. hash value % bucket count = index

3. bucket[index] 에 linked list 로 value 를 넣어준다.

 

이때 서로 다른 value 라도 우연히 hash value 가 같을 수 있는데

이를 hash collision(해시 충돌)이라고 한다.

 

O(1) ??

insertion, deletion, find 가 어떻게 O(1)이 나올까?

문자열 "abc" 를 unordered_set 에 삽입한다고 하면.

1. "abc" 는 hash function 으로 리턴 값인 hash value : 23103023124 를 얻는다. O(1)

2. hash value % bucket count = 4 (index) O(1)

3. bucket[4] -> "abc" (Linked List에 삽입은 O(1))

따라서 insertion 은 O(1) 에 가능하다.

 

문자열 "abc" 를 unordered_set 에서 찾거나 삭제한다면?

1. "abc" 는 hash function 으로 리턴 값인 hash value : 23103023124 를 얻는다. O(1)

2. hash value % bucket count = 4 (index) O(1)

3. bucket[4] 에서 "abc" 찾는다.  O(1)

따라서 find, deletion 도 O(1) 에 가능하다.

 

그런데, element 가 너무 많아지게 되면 hash collision 이 빈번하게 발생하여

서로 다른 값임에도 불구하고 같은 bucket 에 연결된다면 O(N) 이 아닐까?

element 가 많아지게 되면 hash 자체 내부에서 rehashing 이 일어나 bucket count 를 늘려 O(1) 에 수행할 수 있게 변경된다. 다만 rehashing 의 경우 O(N) 이 소요되기 때문에 이를 막기 위해 선언할 때

reserve 를 활용하여 rehashing 의 빈도수를 줄일 수 있다.

#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;

int main()
{
	unordered_set<string> s;

	s.insert("abc");
	s.insert("def");
	s.insert("ghi");
	s.insert("jkl");

	// string(input) -> hash function -> hash value
	cout << "abc: " << hash<string>{}("abc") << endl;
	cout << "def: " << hash<string>{}("def") << endl;
	cout << "ghi: " << hash<string>{}("ghi") << endl;
	cout << "jkl: " << hash<string>{}("jkl") << endl << endl;

	// hash value % bucket_count -> index(hash table mapping)
	cout << "bucket count : " << s.bucket_count() << endl;
	cout << "abc bucket : " << s.bucket("abc") << endl;
	cout << "def bucket : " << s.bucket("def") << endl;
	cout << "ghi bucket : " << s.bucket("ghi") << endl;
	cout << "jkl bucket : " << s.bucket("jkl") << endl << endl;

	// 더 많은 input이 들어오면, rehashing이 발생한다.
	// rehashing 은 O(N)이 소모되므로,
	// 이를 방지하고자 할 때 미리 할당해주는 reserve 를 사용한다.
	s.insert("dasq");
	s.insert("dasdawq");
	s.insert("rdewq");
	s.insert("vkbas");
	s.insert("treq");
	s.insert("gfoas");
	s.insert("bdea");
	s.insert("dela");
	s.insert("jgela");
	cout << "bucket count : " << s.bucket_count() << endl;
	return 0;
}

 

abc: 440920331
def: 3310976652
ghi: 992499321
jkl: 3286144074

bucket count : 8
abc bucket : 3
def bucket : 4
ghi bucket : 1
jkl bucket : 2

bucket count : 64

참고:)

youtu.be/MsDz50o3jHY