📒 C++ - unordered associate container(비 정렬 연관 컨테이너)

📌 unordered associate container란?

- 데이터가 입력 및 삭제되어도 정렬되지 않는다.

- 순서가 보장되지 않는다.

- 저장되는 데이터는 해시 함수를 거쳐서 hash table에 저장된다.

- 해시 함수 -> 해시 키 생성 -> 해시 키에 맞는 버킷에 저장

- 데이터가 한 버킷에 몰릴 경우(해시 키 중복) 성능이 저하되고 상수시간을 보장할 수 없다.

- 삽입, 삭제, 탐색에서 빠른 속도를 보이며, 충돌이 없다면 상수시간을 보장한다.

// C++

#include <iostream>
#include <unordered_map>

using std::cout;
using std::endl;

int main()
{
	// <key type, value type, 해시 함수, 충돌 시 동일성을 체크하는 함수>
	std::unordered_map<int, std::string> um;

	for (int i = 0; i < 10000; ++i)
	{
		um[i] = i;
	}

	cout << um.bucket_count() << endl; // bucket의 수
	cout << um.bucket_size(0) << endl; // bucket0번의 사이즈
	cout << um.bucket_size(1) << endl; // bucket1번의 사이즈
}

Output:
16384
0
0

- 위 예제와 같이, 한 버킷에만 데이터가 많아지게 되면 해시 테이블을 사용하는 의미가 없기 때문에 해시 함수를 잘 구현해야 한다.

- 해시 함수를 잘 구현하는 것은 매우 까다로운 작업이기 때문에 기본 제공되는 것을 사용하는 것을 권장한다.