자료구조/알고리즘 DAT,HT 3장

LV03 DAT,HT(해시테이블) 패턴찾기

1. Direct Address Table

Direct address table은 키 값을 배열의 인덱스로 환산해서 데이터에 접근하는 자료구조이다.

Direct address table은 키 K가 테이블 SLOT T[K]에 저장되기 때문에, 테이블의 크기는 전체 키 [U]개수가 된다.

direct address table은 중복 키가 없고, 테이블의 크기가 작은경우에 사용함.

아래는 구현 코드와 같다.

#include <iostream>
using namespace std;

char vect[12] = "BTABCCQABC";
char pattern[4] = "ABC";

bool isPattern(int startIdx)
{
	for (size_t i = 0; i < 3; i++)
	{
		if (pattern[i] != vect[startIdx + i])
		{
			return false;
		}
	}

	return true;
}

int main()
{
	int cnt = 0;
	for (size_t i = 0; i < 7; i++)
	{
		if (isPattern(i) == true)
		{
			cout << "Pattern found at index: " << i << endl;

			break;
		}
	}

	return 0;
}

해당 코드를 자세히 해석을 해보자면,

int main(){

int cnt = 0;
(size_t i = 0; i < 7; i++)
	{
		if (isPattern(i) == true)
		{
			cout << "Pattern found at index: " << i << endl;

			break;
		}
	}

	return 0;
}

1. is pattern함수에 i 값을 넣는다.
2. is pattern함수에는 startIDX로 들어가게 되는데,
3. pattern[i] != vect[startIdx + i] 같지 않으면 false

같다면 true로 반환하게 된다.

해당코드는 2차원 배열로도 구현할 수 있고, 아래는 예시 코드와 같다.

#include <iostream>
using namespace std;

int vect[3][5] =
{
	1,2,3,4,1,
	3,1,0,0,1,
	2,3,4,1,2,
};
int pattern[3] = {3,4,1};

bool isPattern(int dy, int dx)
{
	for (size_t i = 0; i < 3; i++)
	{
		if (pattern[i] != vect[dy][dx + i])
		{
			return false;
		}
	}

	return true;
}

int main()
{
	bool ret = false;
	for (int y = 0; y < 3; y++)
	{
		for (size_t x = 0; x <3; x++)
		{
			ret = isPattern(y, x);
			if (ret)
				break;
		}
	}

	if (ret == true)
	{
		// 존재
	}
	else
	{
		// 존재하지 않음
	}

	return 0;
}

Hash Table(해시 테이블)

해시 테이블(Hash table)이란 검색하고자 하는 키값을 입력받아서 해쉬 함수를 통해 얻은 해시를 배열의 인덱스로 환산해서 데이터에 접근하는 자료구조이다.

키(key)와 데이터(value)를 저장하는 자료구조를 말한다. 기본연산으로는 탐색(Search), 삽입(Insert), 삭제(Delete)가 있다.

더 설명 않고, 자세히 코드로 설명을 해보겠다.

int bucket[256] = {};

char str[7] = "ADBFAD";
for (int i = 0; i < 6; i++)
{
		bucket[str[i]]++; //str[i](아스키코드)값 자체를 index로 활용
}

만약 i = 0을 넣는다면, bucket[str[0]]++; 이므로

bucket[’A’]++;이 되므로 → 아스키코드상 A = 65

bucket[65]++;이니 bucket의 65번째가 0→1로 오르게 되는 원리이다.

HASH TABLE

해시함수를 사용하여 특정 해시값을 알아내고 그 해시값을 인덱스로 변환하여 키 값과 데이터를 저장하는 자료구조이다. 이는 보통 알고 있는 해시 테이블을 얘기하며 개념자체가 어려운 것은 아니지만 문제가 되는 것은 충돌(Collision)이다. 충돌에 대해서 이해하기 위해선 먼저 적재율(Load Factor)에 대해서 이해해야 한다.

적재율이란 해시 테이블의 크기 대비, 키의 개수를 말한다. 즉, 키의 개수를 K, 해시 테이블의 크기를 N 이라고 했을 때 적재율은 K/N 이다. Direct Address Table은 키 값을 인덱스로 사용하는 구조이기 때문에 적재율이 1 이하이며 적재율이 1 초과인 해시 테이블의 경우는 반드시 충돌이 발생하게 된다.

만약, 충돌이 발생하지 않다고 할 경우 해시 테이블의 탐색, 삽입, 삭제 연산은 모두 O(1) 에 수행되지만 충돌이 발생할 경우 탐색과 삭제 연산이 최악에 O(K) 만큼 걸리게 된다. 이는 같은 인덱스에 모든 키 값과 데이터가 저장된 경우로 충돌이 전부 발생했음을 말한다. 따라서, 충돌을 최대한으로 줄여서 연산속도를 빠르게 하는 것이 해시 테이블의 핵심인데 이에 중요하게 작용하는 것이 바로 해시함수를 구현하는 해시 알고리즘이다. 해시 알고리즘이 견고하지 못하게 되면 해시함수로 도출된 값들이 같은 경우가 빈번하게 발생하게 되므로 잦은 충돌로 이어지게 되는 것이다.