[자료구조] 뻐꾸기 해싱

해시 테이블

이번글은 뻐꾸기 해싱(Cuckoo Hashing)에 대한 글입니다!

해시 테이블의 핵심은 '해싱'입니다.

'해싱'이란 각각의 주어진 데이터를 최대한 고유한 숫자 값으로 표현하여 나중에 해당 데이터의 유무를 확인하거나 해당 데이터에 대응하는 원본 데이터를 추출 하는 작업입니다.

그리고 주어진 데이터로 부터 고유한 숫자 값을 계산하는 함수를 '해시 함수'라고합니다.

 

그래서 해시 함수를 무엇을 정하느냐에 따라 해시 함수를 통해 나오는 '해시 값'이 각기 달라지겠지만 가장 일반적인 방법으로는 입력 받은 데이터 : x 가 있을 때 (x % n)으로 '해시 값'을 반환합니다.

이런 방법으로 해시 맵을 구성하여 데이터를 넣다보면 n이 7이라 가정을 했을 때 x가 3, 10 순으로 들어오게 된다면 

(x % 3) == (x % 7)의 나머지 값이 같기 때문에 '충돌'이 발생할 것입니다. 

 

부하율

충돌은 '부하율(load factor)'수식으로 표현할 수 있는데요 부하율이란 해시 테이블에서 각각의 리스트에 저장되는 키의 평균 개수를 뜻하며, ( '전체 키 개수' / '해시 테이블 크기' ) 로 부하율을 구할 수 있습니다.

키의 개수와 해시테이블의 크기가 같다면 부하율은 1로 이상적인 상태이며, 부하율이 1보다 작으면 리스트당 키가 하나도 저장되어 있지 않은 경우가 있는다는 것이고 메모리 낭비를 뜻합니다.

부하율이 1보다 크면 리스트의 평군 길이가 1보다 크다는 의미이며 검색, 삭제 등의 작업에 약간 느리게 동작할 가능성이 있습니다. 1보다 너무 커지거나 작아지면 해시 함수를 변경하여 '재해싱'이 발생합니다. 재해싱을 하여 부하율을 1에 가깝게 만드는 것이지요.

하지만 부하율이 해시 테이블의 성능을 결정하는 유일한 요소는 아니라는 것을 기억해주세요! 

 

뻐꾸기 해싱

충돌을 피하기 위한 해시 기법으로 '체이닝', '열린 주소 방식' 등이 사용되었지만 문제점들이 존재 합니다.

'체이닝'의 경우 해당 해시값에 연결 리스트를 저장하여 계속해서 연결해 나가는 방식입니다. 그런데 이렇게 되면 

(x % 7)의 값이 계속 같은 값으로 나오게 될 경우 연결 리스트에 계속 push_back을 반복해서 나중에 데이터를 찾는경우 해시 맵의 장점인 O(1)은 없어지고 O(n)로 선형적으로 탐색을 하게되는 문제점이 있습니다.

 

그래서 다른 해시 기법들의 문제점들을 거의 다 해결하는 해시 기법이 있는데, 이게 바로 '뻐꾸기 해싱'입니다.

뻐꾸기 해싱은 크기가 같은 두개의 테이블을 사용하고 각각의 해시 테이블은 서로 다른 해시 함수를 가집니다.

(해시 테이블의 개수는 두개가 고정이 아닙니다. 다만 저는 구현을 할 때 해시 테이블이 두개가 있는 버젼을 구현하였습니다.)

 

'룩업' 연산의 경우 두개의 해시 테이블만 확인하면 되므로 O(1)

'삽입' 연산의 경우 빠르게 동작하기는 하지만 조금 오래걸릴 수 있습니다.

가령 해시 테이블 A, 해시 테이블 B가 있다고 가정을 하도록 하겠습니다.

 

A테이블에 a가 삽입된다고 가정을 하면 기존에 b를 A -> B로(c의 자리에)옮기고 c를 A테이블로 옮깁니다.

하지만 c를 A테이블로 옮기는 과정에서 D가 A테이블에 존재하는 경우 '순환(cycle)'이 발생합니다.

 이렇게 되면 새로운 해시 함수를 통해 재해싱을 진행해야합니다. 그래서 뻐꾸기 해싱은 높은 성능을 보장하려면 부하율의 값을 0.5 보다 작게 설정하는 것이 유리합니다.

 

구현

#include <iostream>
using namespace std;

#include <vector>
#include <list>
#include <algorithm>

using ui = unsigned int;

class hash_map
{
	vector<int> data1;
	vector<int> data2;
	int size;

public:
	int hash1(int key) const
	{
		return key % size;
	}

	int hash2(int key) const
	{
		return (key / size) % size;
	}

public:
	hash_map(int n) : size(n)
	{
		data1 = vector<int>(size, -1);
		data2 = vector<int>(size, -1);
	}

	vector<int>::iterator lookup(int key)
	{
		auto hash_value1 = hash1(key);
		if (data1[hash_value1] == key)
		{
			cout << "1번 테이블에서 " << key << "를 찾았습니다" << endl;
			return data1.begin() + hash_value1;
		}

		auto hash_value2 = hash2(key);
		if (data2[hash_value2] == key)
		{
			cout << "2번 테이블에서 " << key << "를 찾았습니다" << endl;
			return data2.begin() + hash_value2;
		}

		return data2.end();
	}
	
	void erase(int key)
	{
		auto position = lookup(key);
		if (position != data2.end())
		{
			*position = -1;
			cout << key << " 에 해당하는 원소를 삭제 했습니다!" << endl;
		}
		else
		{
			cout << key << " 를 찾지 못했습니다!" << endl;
		}
	}

	void insert(int key)
	{
		insert_impl(key, 0, 1);
	}
	void insert_impl(int key, int cnt, int table)
	{
		if (cnt >= size)
		{
			cout << key << " 삽입 시 순환 발생! 재해싱이 필요합니다!" << endl;
			return;
		}

		if (table == 1)
		{
			int hash = hash1(key);
			if (data1[hash] == -1)
			{
				cout << table << "번 테이블에 " << key << " 삽입" << endl;
				data1[hash] = key;
			}
			else
			{
				int old = data1[hash];
				data1[hash] = key;
				cout << table << "번 테이블에 " << key << " 삽입 : 기존의 " << old << " 이동 -> ";
				insert_impl(old, cnt + 1, 2);
			}
		}
		else
		{
			int hash = hash2(key);
			if (data2[hash] == -1)
			{
				cout << table << "번 테이블에 " << key << " 삽입" << endl;
				data2[hash] = key;
			}
			else
			{
				int old = data2[hash];
				data2[hash] = key;
				cout << table << "번 테이블에 " << key << " 삽입: 기존의 " << old << " 이동 -> ";
				insert_impl(old, cnt + 1, 1);
			}
		}
	}

public:
	void print()
	{
		cout << "Index : ";
		for (int i = 0; i < size; ++i)
		{
			cout << i << '\t';
		}
		cout << endl;

		cout << "Data1 : ";
		for (auto i : data1) cout << i << '\t';
		cout << endl;

		cout << "Data2 : ";
		for (auto i : data2) cout << i << '\t';
		cout << endl;
	}
};

int main()
{
	hash_map m(7);
	m.print();
	cout << endl;

	m.insert(10);
	m.insert(20);
	m.insert(30);
	cout << endl;


	m.insert(104);
	m.insert(2);
	m.insert(70);
	m.insert(9);
	m.insert(90);
	m.insert(2);
	m.insert(7);
	cout << endl;

	m.print();
	cout << endl;

	m.insert(14);

	return 0;
}