자료구조 - HashTable

2017-12-24

HashTable

HashTable 또는 HashMap이란 키값을 이용하여 값을 저장하는 구조로 키값을 해시함수에 넣어 인덱스로 변환한 후 테이블에 접근해 저장하는 자료구조이다. 해시테이블은 해시함수를 통해 테이블의 인덱스를 계산하고 이 값을 통해 테이블에 직접 접근하기 때문에 O(1)의 빠른 접근시간을 가지고 있다.

위 그림을 보면 왼쪽에 사람의 이름에 해당하는 key 값들이 존재한다. John Smith, Lisa Smith.. 이 값들은 키값이 되고 이 값들은 해시함수를 통해 계산되어 01,02,04와 같은 숫자의 인덱스 번호로 바뀌게 된다.

가장 간단한 문자열에 대한 해시함수를 보자면 각 자리의 아스키 코드 값을 더한 값을 해시값으로 리턴하는 것이다. 하지만 이 asdf fdsa와 같이 구성된 문자가 같은데 순서가 다른 문자에 대해서도 똑같은 값으로 취급되기 때문에 충돌이 많이 일어난다. 따라서 각 자리마다 가중치를 두어서 그 가중치를 곱해준 값을 더해주면 충돌을 조금이나마 줄일 수 있다.

해시 함수에서 가장 문제되는 것은 ‘충돌’이다. 현재까지 나와 있는 해시 함수 계산법들도 완전하게 충돌을 피해갈 수 없다고 한다. 즉 충돌을 허용하되 충돌이 일어나면 어떻게 이 문제를 해결할 것인가를 생각해보아야 한다. 대표적으로 이 해결법에는 probing과 chaining이 있다.

체이닝

체이닝은 위의 그림과 같이 충돌이 일어나는 값에 대해 링크드 리스트를 이용해 저장해 주는 방법이다. 계산된 해시값에 대해서 충돌이 일어나게 되면 단순히 이어 붙이기만 하면 되기 때문에 구현이 쉽지만 포인터를 통해 간접적으로 계속 찾아나가기 때문에 연속된 메모리 공간에서 해결하는 probing 방식보다는 조금 느리다는 단점이 있다.

Probing

Probing은 Chaining의 방식과 달리 충돌이 나면 원래 테이블내 공간에서 해결하는 개방적 방법이다. 해시 값이 충돌이 나게되면 어떠한 방법을 통해 다시 해시값을 계산한 후 빈공간을 찾아 저장하는 방식이다. 위의 그림에서는 충돌이 일어나면 (get_hash(key) +2table_size를 통해 +2만큼 된 곳에서 빈 곳을 찾아 저장하였다. 이러한 Linear Probing 방식은 간단하지만 값이 클러스터링될 가능성이 높아 자료가 많아지면 클러스터링 된 곳에서 충돌이 많이 발생할 가능성이 높다.

#include <iostream>
#include <vector>
#include <string>

using namespace std;


class HashTable
{
private:
	vector<vector<string>> table; // 체인을 이용하여 충돌의 문제를 완화한다.
	int getHash(string s)
	{
		int sum = 0;
		int base = 1;
		for (int i = 0; i < s.length(); i++)
		{
			sum += s[i] * base;
			base *= 2;
		}
		return sum % table.size();
	}
public:
	HashTable()
	{
		for (int i = 0; i < 1000; i++)
		{
			vector<string> chain;
			table.push_back(chain);
		}
	}
	void setValue(string key,string value)
	{
		int index = getHash(key);
	
		table[index].push_back(value);
	}
	vector<string> getValue(string key)
	{
		int index = getHash(key);

		vector<string> result;
		for (int i = 0; i < table[index].size(); i++)
		{
			result.push_back(table[index][i]);
		}
		return result;
	}
};



void main()
{
	ios::sync_with_stdio(false);cin.tie(0);

	HashTable ht;

	ht.setValue("Value", "flow");
	ht.setValue("Value", "flower");
	ht.setValue("Value", "falut");
	ht.setValue("value", "Areo");
	ht.setValue("value", "Bucket");

	vector<string> result = ht.getValue("Value");
	vector<string> result2 = ht.getValue("value");

	for (int i = 0; i < result.size(); i++)
		cout << result[i]<<endl;
	for (int i = 0; i < result2.size(); i++)
		cout << result2[i] << endl;
}

Gunner

ProgrammingDataStructure

자료구조 - HashTable