해시 테이블(Hash Table)

해시 테이블

해싱(hashing) - 각각의 데이터를 가급적 고유한 숫자 값으로 표현하고, 나중에 같은 숫자 값을 사용하여 데이터의 유무를 확인하거나 해당 숫자에 대응하는 원본 데이터를 추출하는 작업.

해시 함수(hash function) - 주어진 데이터로부터 고유한 숫자 값을 계산하는 함수.

모듈로 함수(modulo funcion) - 가장 간단한 해시 함수로 큰 범위의 정수를 인자로 받아 정해진 정수(n)로 나눈 나머지를 반환. 보통 % 기호로 표시.

ex) 숫자 x를 입력하면 (x % n)가 연산의 결과로 반환. x를 배열에서 (x % n)의 위치에 삽입.

해시 값(hash value) - 위의 예시처럼 해시 함수에 의해 반환되는 값.

충돌(collision) - 서로 다른 데이터의 대해 같은 해시 값을 반환하는 문제.

ex) 모듈러 함수에서 (9 % 7)과 (16 % 7)은 모두 2를 반환함. 이때 해시 값 2에 해당하는 위치가 true인 경우 그곳에 들어있는 데이터가 9인지 16인지 알수 없으며 해시 값 2를 만족하는 다른 수가 저장되어 있을 수도 있음.

부하율(load factor) - 해시 테이블에서 각각의 리스트에 저장되는 키의 편균 갯수. 부하율 = 전체 키 갯수/해시 테이블 크기

해시 테이블에서의 충돌을 해결하는 방법

1. 체이닝(chaining) - 해시 테이블의 특정 위치에서 하나의 키를 저장하는 것이 아니라 하나의 연결 리스트를 저장. 충돌이 일어났을 때 새로 삽입된 키를 리스트에 추가.

2. 열린 주소 지정(open addressing) - 해시 값에 해당하는 위치가 이미 사용되고 잇다면 테이블의 다른 비어 있는 주소를 탐색, 저장.

열린 주소 지정에서의 탐색 방법들

• 선형 탐색(leaner probing) - 충돌이 발생하면 해당 위치에서 하나씩 다음 셀(cell)로 이동하며, 비어 있는 셀을 찾으면 원소를 삽입.
• 이차함수 탐색(quadratic probing) - 선형 탐색을 하는 경우 새 원소들이 특정 위치에 모이는 군집화가 발생할 수 있기 때문에 선형 방정식이 아닌 이차 방정식을 사용하여 탐색을 수행.

3. 뻐꾸기 해싱(cuckoo hashing) - 완벽한 해싱 기법 중에 하나. 두개의 해시 테이블을 사용하며 각각의 해시 테이블은 서로 다른 해시 함수를 가짐. 또한 원소가 나중에 다른 위치로 이동할 수 있음. 단, 원소를 옮기는 과정에서 순환이 발생할 수 있으며 이 경우엔 새로운 해시 함수로 재해싱을 해야할 수 있음.

c++에서 기본으로 제공하는 해시 테이블

#include <iostream>
#include <unordered_map>
#include <unordered_set>


void print(const std::unordered_set<int>& container) {
	for (const auto& element : container)
		std::cout << element << " ";
	std::cout << std::endl;
}

void print(const std::unordered_map<int, int>& container) {
	for (const auto& element : container)
		std::cout << element.first << ": " << element.second << ". ";
	std::cout << std::endl;
}

void find(const std::unordered_set<int>& container, const int& value) {
	if (container.find(value) == container.end())
		std::cout << value << " 검색: 실패" << std::endl;
	else
		std::cout << value << " 검색: 성공" << std::endl;
}

void find(const std::unordered_map<int, int>& container, const int value) {
	auto it = container.find(value);
	if (it == container.end())
		std::cout << value << " 검색: 실패" << std::endl;
	else
		std::cout << value << " 검색: 성공, 값 =" << it->second << std::endl;
}

int main()
{
	std::cout << "std::unordered_set 예제" << std::endl;
	std::unordered_set<int> set1 = { 1, 2, 3, 4, 5 };

	std::cout << "set1 초깃값: "; 
	print(set1);

	set1.insert(2);
	std::cout << "2 삽입";
	print(set1);

	set1.insert(15);
	set1.insert(120);
	std::cout << "15, 120 삽입: ";
	print(set1);

	find(set1, 3);
	find(set1, 200);

	set1.erase(2);
	std::cout<<"2 삭제: ";
	print(set1);

	find(set1, 2);

	std::cout << "std::unordered_map 예제" << std::endl;
	std::unordered_map<int, int> squareMap;

	squareMap.insert({ 2, 4 });
	squareMap[3] = 9;
	std::cout << "2, 3의 제곡 삽입: ";
	print(squareMap);

	squareMap[20] = 400;
	squareMap[30] = 900;
	std::cout << "20, 30의 제곱 삽입: ";
	print(squareMap);

	find(squareMap, 10);
	find(squareMap, 20);
	std::cout << "squareMap[3] = " << squareMap[3] << std::endl;
	std::cout << "squareMap[100] = " << squareMap[100] << std::endl;

	// []연산자는 참조를 반환
	std::cout << squareMap[20] << std::endl;
	squareMap[20] = 30;
	std::cout << squareMap[20] << std::endl;

	std::cout << squareMap.bucket_count() << std::endl;
	print(squareMap);
}

실행결과: