[자료구조] 해시 태이블 (3)

CS/자료구조

[자료구조] 해시 태이블 (3)

nowkoes 2023. 5. 2. 01:42

<본 카테고리는 "코딩 테스트를 위한 자료 구조와 알고리즘 with C++을 기반으로 작성하였습니다>

뻐꾸기 해싱

구현

　지금부터 뻐꾸기 해싱을 구현해 보도록 하겠다. 이때 값을 삽입하고, 찾고, 삭제하는 메서드를 추가할 것이다. 필자가 스스로 구현한 코드와, 책에서 예제로 구현한 코드를 같이 첨부할 것이다 (내가 작성한 코드가 오류가 없다고 자신할 수 없어서..)

#include <iostream>
#include <vector>

class cuckoo_hash
{
	std::vector<int> _table1, _table2;
	int _size;

	int hash1(int key) const
	{
		return key % _size;
	}

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

public:
	cuckoo_hash(int size) : _size(size)
	{
		_table1 = std::vector<int>(size, -1);
		_table2 = std::vector<int>(size, -1);
	}

　두 개의 해시 테이블을 초기화하고, 모듈러 연산을 이용한 해시 함수를 구현하였다. 그리고 테이블을 -1로 채우는데, -1의 의미는 비어있음을 의미하는 것이다.

class cuckoo_hash
{
	...
	bool find(int key, std::vector<int> table)
	{
		auto value1 = hash1(key);
		auto value2 = hash2(key);

		if (table[value1] == key || table[value2] == key)
			return true;

		else
			return false;
	}

public:
	...

	void lookUp(int key)
	{
		if (find(key, _table1))
			std::cout << "Find the " << key << " from the table1\n";

		else if (find(key, _table2))
			std::cout << "Find the " << key << " from the table2\n";

		else
			std::cout << "Cannot find the " << key << " from the table\n";
	}

　값을 찾는 lookUp() 함수다. 실제로 찾는 find 함수는 private 멤버로 선언했으며, _table1과 _table2에 키가 있는지 검사한 후 bool 값을 리턴한다.

class cuckoo_hash
{
	...
public:
	...
	void erase(int key)
	{
		auto value = hash1(key);

		if (find(key, _table1))
		{
			_table1[value] = -1;
			std::cout << "Remove the " << key << " from table1\n";
			std::cout << "\n";
			return;
		}

		else
		{
			std::cout << key << " not detected from table1\n";
		}

		value = hash2(key);

		if (find(key, _table2))
		{
			_table2[value] = -1;
			std::cout << "Remove the " << key << " from table2\n";
		}

		else
			std::cout << key << " not detected from table2\n";

		std::cout << "\n";
	}

　값을 삭제하는 erase() 함수다. key가 양쪽 테이블에 있는지 확인한 후, 존재한다면 key를 -1로 바꾸고 삭제한다.

class cuckoo_hash
{
	...
	void Insert(int key, int count, int table)
	{
		if (count >= _size)
		{
			std::cout << "Cycle detected. Cannot insert " << key << "\n";
			return;
		}

		if (table == 1)
		{
			int value = hash1(key);

			if (_table1[value] == -1)
			{
				std::cout << "Input the " << key << " into table1\n";
				_table1[value] = key;
			}

			else
			{
				int oldkey = _table1[value];
				_table1[value] = key;
				std::cout << "Input the " << key << " into table1: Exsiting " << oldkey << " is moved -> ";
				Insert(oldkey, count + 1, 2);
			}
		}

		else
		{
			int value = hash2(key);

			if (_table2[value] == -1)
			{
				std::cout << "Input the " << key << " into table2\n";
				_table2[value] = key;
			}

			else
			{
				int oldkey = _table2[value];
				_table2[value] = key;
				std::cout << "Input the " << key << " into table2: Exsiting " << oldkey << " is moved -> ";
				Insert(oldkey, count + 1, 1);
			}
		}
	}

public:
	...
	void insert(int key)
	{
		Insert(key, 0, 1);
		std::cout << "\n";
	}
};

　값을 삽입하는 insert() 함수다. 삽입은 재귀적으로 동작해야 하기 때문에 실제 삽입 구현 함수를 따로 만들어 놨다. 삽입 함수에서는 순환 여부를 검사해야 하므로 재귀 호출 횟수가 해시 테이블의 크기보다 크면 순환이라고 판단하게 구현하였다.

int main()
{
	cuckoo_hash ck(7);
	
	ck.insert(10);
	ck.insert(20);
	ck.lookUp(20);
	ck.insert(30);
	ck.erase(30);
	ck.lookUp(30);

	ck.insert(104);
	ck.lookUp(20);
	ck.insert(2);
	ck.insert(70);
	ck.insert(9);
	ck.insert(90);
	ck.insert(2);
	ck.insert(7);
	ck.insert(14);
}

　마지막으로 main 함수에서 해당 알고리즘이 잘 돌아가는지 확인해 보자.

총합본

#include <iostream>
#include <vector>

class cuckoo_hash
{
	std::vector<int> _table1, _table2;
	int _size;

	int hash1(int key) const
	{
		return key % _size;
	}

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

	bool find(int key, std::vector<int> table)
	{
		auto value1 = hash1(key);
		auto value2 = hash2(key);

		if (table[value1] == key || table[value2] == key)
			return true;

		else
			return false;
	}

	void Insert(int key, int count, int table)
	{
		if (count >= _size)
		{
			std::cout << "Cycle detected. Cannot insert " << key << "\n";
			return;
		}

		if (table == 1)
		{
			int value = hash1(key);

			if (_table1[value] == -1)
			{
				std::cout << "Input the " << key << " into table1\n";
				_table1[value] = key;
			}

			else
			{
				int oldkey = _table1[value];
				_table1[value] = key;
				std::cout << "Input the " << key << " into table1: Exsiting " << oldkey << " is moved -> ";
				Insert(oldkey, count + 1, 2);
			}
		}

		else
		{
			int value = hash2(key);

			if (_table2[value] == -1)
			{
				std::cout << "Input the " << key << " into table2\n";
				_table2[value] = key;
			}

			else
			{
				int oldkey = _table2[value];
				_table2[value] = key;
				std::cout << "Input the " << key << " into table2: Exsiting " << oldkey << " is moved -> ";
				Insert(oldkey, count + 1, 1);
			}
		}
	}

public:
	cuckoo_hash(int size) : _size(size)
	{
		_table1 = std::vector<int>(size, -1);
		_table2 = std::vector<int>(size, -1);
	}

	void lookUp(int key)
	{
		if (find(key, _table1))
			std::cout << "Find the " << key << " from the table1\n";

		else if (find(key, _table2))
			std::cout << "Find the " << key << " from the table2\n";

		else
			std::cout << "Cannot find the " << key << " from the table\n";

		std::cout << "\n";
	}

	void erase(int key)
	{
		auto value = hash1(key);

		if (find(key, _table1))
		{
			_table1[value] = -1;
			std::cout << "Remove the " << key << " from table1\n";
			std::cout << "\n";
			return;
		}

		else
		{
			std::cout << key << " not detected from table1\n";
		}

		value = hash2(key);

		if (find(key, _table2))
		{
			_table2[value] = -1;
			std::cout << "Remove the " << key << " from table2\n";
		}

		else
			std::cout << key << " not detected from table2\n";

		std::cout << "\n";
	}

	void insert(int key)
	{
		Insert(key, 0, 1);
		std::cout << "\n";
	}
};

int main()
{
	cuckoo_hash ck(7);
	
	ck.insert(10);
	ck.insert(20);
	ck.lookUp(20);
	ck.insert(30);
	ck.erase(30);
	ck.lookUp(30);

	ck.insert(104);
	ck.lookUp(20);
	ck.insert(2);
	ck.insert(70);
	ck.insert(9);
	ck.insert(90);
	ck.insert(2);
	ck.insert(7);
	ck.insert(14);
}

원본 코드

#include <iostream>
#include <vector>

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

	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 = std::vector<int>(size, -1);
		data2 = std::vector<int>(size, -1);
	}

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

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

		return data2.end();
	}

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

	void insert(int key)
	{
		insert_impl(key, 0, 1);
	}

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

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

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

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

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

int main()
{
	hash_map map(7);
	map.print();
	std::cout << std::endl;

	map.insert(10);
	map.insert(20);
	map.insert(30);
	std::cout << std::endl;

	map.insert(104);
	map.insert(2);
	map.insert(70);
	map.insert(9);
	map.insert(90);
	map.insert(2);
	map.insert(7);
	std::cout << std::endl;

	map.print();
	std::cout << std::endl;

	map.insert(14); // 사이클 발생!
}

요약

해시 테이블
1. 정의: 키와 값을 이용해 데이터를 저장하는 자료구조로서, 키를 해시함수를 이용해 해시 값으로 변환한 후, 해당 해시 값에 해당하는 위치에 값을 저장
2. 충돌
　a. 정의: 다수의 키가 같은 값을 갖게 되는 현상
　b. 해결: 체이닝, 열린 주소 지정, 선형 탐색, 이차함수 탐색, 뻐꾸기 해싱

저작자표시 비영리 변경금지

'CS > 자료구조' 카테고리의 다른 글

[자료구조] 블룸 필터 (2)	2023.05.06
[자료구조] 해시 테이블 (2) (0)	2023.04.27
[자료구조] 해시 테이블 (1) (0)	2023.04.26
[자료구조] 그래프 (0)	2023.04.24
[자료구조] 힙 (2)	2023.04.20

현재글[자료구조] 해시 태이블 (3)

개발일지