[자료구조] 해시 테이블 (1)

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

---

해시 테이블(Hash Table)

개요

　해시 테이블은 키(key)와 값(value)을 이용해 데이터를 저장하는 자료구조로서, 키를 주어진 데이터로부터 고유한 숫자 값을 계산하는 해시 함수(hash function)를 이용해 해시 값으로 변환한 후, 해당 해시 값에 해당하는 위치에 값을 저장한다. 여기서 해시 값(hash value)이란 해시 함수에 의해 반환되는 숫자를 의미한다.

 

　키와 값을 이용한 자료구조라는 점에서 std::map 자료구조와 비슷하다고 생각할 수 있다. 실제로 두 컨테이너는 유사하지만, 내부 구조와 동작 방식, 그리고 성능 특성 등에서 차이가 있다. 

 

	hash table	map
탐색	이진 탐색	해싱
정렬	X	O
속도	O(1)	O(logN)

---

해싱과 충돌

　해시 테이블의 핵심은 해싱이다. 해싱(hashing)은 각각의 데이터를 고유한 숫자로 표현하고, 나중에 같은 숫자 값을 사용하여 데이터의 유무를 확인하거나, 해당 숫자에 대응하는 원본 데이터를 추출하는 작업이다. 즉, 매핑하는 과정 자체를 해싱이라고 한다.

 

　이러한 해싱을 진행하다 보면, 해시함수가 해쉬 값의 개수보다 많은 키값을 해쉬값으로 변환하기 때문에 해시 함수가 서로 다른 키에 대해 같은 해시 값을 반환함으로써, 다수의 키가 같은 값을 갖게 되는 해시 충돌(Collision)이 발생하게 된다.

 

　이러한 과정을 자연수를 저장하는 간단한 사전을 만들어보면서 확인해보자.

 

#include <iostream>
#include <vector>

class hash_table
{
	std::vector<int> _hash;

public:
	hash_table(size_t n)
	{
		_hash = std::vector<int>(n, -1);
	}

　해시 테이블에서 사용할 데이터 크기를 인자로 받아 벡터를 생성한다. 이때 -1로 채우는 이유는 벡터 값이 -1일 때 해당 위치에 저장된 원소가 없음을 나타내기 위해서다. 

 

	void insert(unsigned int value)
	{
		_hash[value % _hash.size()] = value;
		std::cout << "Input the " << value << " in hash table.\n";
	}

　값을 해시 테이블에 삽입하는 insert() 함수다. 여기서 해시 함수를 모듈로 함수를 이용해 구현하였다.

 

	void lookUp(unsigned int value)
	{
		if (_hash[value % _hash.size()] == value)
			std::cout << "Find the " << value << " in hash table.\n";
		else
			std::cout << "Can't find the " << value << " in hash table.\n";
	}

　특정 원소가 함수 내에 존재하는지 확인하는 lookUp() 함수다. 룩업(look up)은 특정 원소가 컨테이너에 있는지 확인하거나 또는 컨테이너에서 특정 키에 해당하는 값을 찾는 작업을 의미하는 단어로서 널리 사용되는 개념이다.

 

	void erase(unsigned int value)
	{
		if (_hash[value % _hash.size()] == value)
		{
			_hash[value % _hash.size()] = -1;
			std::cout << "Erase the " << value << " in hash table.\n";
		}
	}
};

　특정 원소를 삭제하는 erase() 함수다. 앞서 -1의 의미는 해당 위치에 저장된 원소가 없다는 것을 나타내기로 약속했으므로, 다음과 같이 구현하였다.

 

int main()
{
	hash_table hash(7);

	hash.insert(2);
	hash.insert(25);
	hash.insert(10);

	hash.lookUp(25);

	hash.insert(100);
	hash.lookUp(100);
	hash.lookUp(2);

	hash.erase(25);
}

　다음과 같이 main() 함수를 구성하였을 때, 이상한 결과가 출력될 것이다.

 

실행 결과

 

　분명 2, 25, 10, 100이란 값을 넣었는데 hash_table에서 2라는 값을 찾지 못하고 있다. 이러한 현상이 발생하는 이유를 다음 그림에서 확인해 보자.

 

 

　크기가 7인 해시 테이블을 만들고 2, 10, 25를 테이블에 넣은 후 25란 값을 찾는 과정이다. 여기까진 큰 문제가 없다.

 

 

　문제는 여기서 발생한다. 2 % 7 = 2, 100 % 7 = 2이므로 기존의 2가 있는 곳에 100이 덮기 때문에 2라는 값이 사라져 버렸다. 여기서 충돌 문제가 발생한 것이다. 이를 해결하기 위해서 키에 대응하는 값을 넣어야 하는데, 이러한 방법들을 다음 포스팅에서 알아보도록 하자.

 

총합본

##include <iostream>
#include <vector>

class hash_table
{
	std::vector<int> _hash;

public:
	hash_table(size_t n)
	{
		_hash = std::vector<int>(n, -1);
	}

	void insert(unsigned int value)
	{
		_hash[value % _hash.size()] = value;
		std::cout << "Input the " << value << " in hash table.\n";
	}

	void lookUp(unsigned int value)
	{
		if (_hash[value % _hash.size()] == value)
			std::cout << "Find the " << value << " in hash table.\n";
		else
			std::cout << "Can't find the " << value << " in hash table.\n";
	}
    
    	void erase(unsigned int value)
	{
		if (_hash[value % _hash.size()] == value)
		{
			_hash[value % _hash.size()] = -1;
			std::cout << "Erase the " << value << " in hash table.\n";
		}
	}
};

int main()
{
	hash_table hash(7);

	hash.insert(2);
	hash.insert(25);
	hash.insert(10);

	hash.lookUp(25);

	hash.insert(100);
	hash.lookUp(100);
	hash.lookUp(2);

	hash.erase(25);
}