해시 테이블(Hash Table)

해시함수와 함께 데이터 검색을 효율적으로 하기 위해 사용되는 구조

키(key)와 값(value)이 한 쌍을 이루는 데이터를 저장

 

특정 키값 K를 갖는 데이터를 찾는 문제에서 활용

 

원하는 데이터를 선형탐색으로 구할 수는 있지만, 데이터 양에 비례해서 계산시간이 늘어난다는 단점이 있다.

배열 탐색에 시간이 걸리므로, 적합하지 않은 구조 👉 해시테이블의 등장

 

🟩 배열을 만들고 데이터를 추가할 때, '해시 함수' 이용

키 값을 해시 테이블의 주소로 변환하는 함수

계산이 용이해야 하며, 적은 충돌 발생 👉 각 키를 테이블의 각 슬롯에 균등하게 사상시킬 수 있어야 

 

🌟 해시 함수의 종류

1. 제산잔여법

키 값을 해시 함수에 넣어 나오는 해시값을 배열의 갯수로 나누어 나머지를 구한다. 예) 4928 % 5 = 3

구한 수와 같은 배열의 3번 상자(a[3])에 데이터를 저장. 다른 데이터들도 반복

 

키를 해시 테이블의 인덱스로 변환하는 과정에서 사용

키를 해시 테이블의 크기로 나눈 나머지를 해당 키의 해시 값으로 사용

EX) 해시 테이블의 크기 = 10, 키=27  👉 27 % 10 = 7 👉 키 27은 해시값 7로 매핑된다.

 

이 방법은 단순하지만, 균일한 해시 값을 생성하기 위해서는 해시 테이블의 크기를 키의 소수와 관련시키는 것이 일반적이다. 그렇지 않으면 일부 키들이 같은 해시 값을 가지는 충돌이 발생할 수 있다. EX) 크기가 10이고 키가 17인 경우와 27인 경우는 같은 해시값인 7을 가진다.

👉 이러한 충돌을 최소화하기 위해 해시 테이블의 크기를 키의 소수와 관련시켜서 선택함으로써 해결 가능

 

2. 비닝

데이터를 그룹으로 나누는 과정이나 방법

데이터를 구간(버킷)으로 나누거나 이산적인 값으로 변환하여 그룹을 형성한다. 이것은 데이터를 더 작은ㄴ 세트로 분할하여 분석하기 쉽게 만드는 기술이다. 주로 연속형 데이터를 이산적인 그룹으로 변환하는데 사용된다.

 

3. 중간 제곱법

입력 값의 제곱한 값의 중간 부분을 해시 값으로 사용하는 방식

단순하고 빠르지만, 일부 키에 대해 충돌이 발생할 수 있으며, 특히 중간 부분이 반복되는 경우에는 해시값의 분포가 균일하지 않을 수 있다. 또한, 입력값의 범위에 따라 해시값의 분포가 크게 달라질 수 있다. 따라서 중간 제곱법은 간단한 해시 함수로 사용되지만, 보안이나 큰 데이터 셋에 대한 해싱에는 적합하지 않을 수 있다.

 

1. 키를 제곱한다.

2. 제곱한 값을 문자열로 변환하고, 중간 부분을 선택한다.

3. 선택한 중간 부분이 해시 값으로 사용된다.

 

EX) 3자리의 입력값 45를 사용한다고 가정

1. 45 제곱시 2025

2. 2025의 문자열은 "2025", 중간 부분은 "02"

3. "02"가 해시값으로 사용된다.

 

👉 45의 해시값은 "02"

 

4. 문자열을 위한 비닝

문자열 데이터를 이산적인 그룹 또는 범주로 나누는 과정을 의미한다. 이는 문자열 데이터를 처리하고 분석하는 과정에서 유용하게 활용될 수 있다. 비닝은 문자열 데이터를 더 쉽게 처리하고 분석하기 위해 사용될 수 있다.

 

1. 알파벳 구간 분할 : 문자열을 알파벳의 범주로 나누는 것. EX) 영어 알파벳을 사용하는 문자열의 경우 A~Z 알파벳을 여러 그룹으로 나눌 수 있다.

2. 문자열 길이 기반 비닝 : 문자열의 길이를 기준으로 그룹을 형성하는 것.EX) 문자열의 길이가 15글자, 610글자, 11글자 이상 등으로 구분 가능

3. 문자 패턴 비닝 : 문자열의 특정 패턴이나 서브스트링을 기준으로 그룹을 형성하는 것 EX) 이메일 주소의 경우 "@" 문자를 기준으로 사용자 이름과 도메인을 분리하여 비닝 가능

4. 단어 빈도 비닝 : 문자열에서 단어의 출현 빈도를 기준으로 그룹을 형성하는 것.EX) 특정 빈도의 출현 빈도가 낮은 경우 "적은 빈도", 중간 수준의 경우 "중간 빈도", 높은 경우 "높은 빈도"로 비닝 가능

 

5. 문자열을 위한 단순합

주어진 데이터의 각 문자에 대한 ASCII  값 또는 유니코드 코드 포인트를 더한 후에 모듈로 연산을 통해 해시 값을 생성하는 방식

 

EX) "hello"ASCII 값 분석

h = 104

e = 101

l = 108

l = 108

o = 111

 

👉 합 = 104+101+108+108+111=532

532를 해시 테이블의 크기로 나눈 나머지를 해시 값으로 사용할 수 있다.

 

단순합은 해시 충돌을 발생할 수 있는 단점이 있다. 예를 들어 "hello"와 "olleh"는 모두 같은 해시값을 갖게 된다.

간단하고 빠르지만, 충돌이 발생할 가능성이 높은 경우에 사용된다.

 

6. 문자열을 위한 가중합

문자열의 각 문자에 가중치를 부여한 후 이를 합산하여 해시 값을 생성하는 방식

이 방법은 문자열을 고정된 길이의 해시값으로 매핑하는 데 사용된다.

 

1. 각 문자에 대해 가중치를 할당한다. 이 가중치는 일반적으로 문자의 위치나 ASCII 값 등과 관련된 값을 가질 수 있다.

2. 문자열을 순회하면서 각 문자에 해당하는 가중치를 곱한다.

3. 곱한 값을 모두 합산하여 해시값을 생성한다.

4. 생성된 해시 값을 해시 테이블의 크기로 나눈 나머지를 최종 해시 값으로 사용한다.

 

EX) "hello"

1. 각 문자에 대해 ASCII 값을 가중치로 사용한다. 문자 'h'의 ASCII 값은 104, e는 101, l은 108, o는 111이다.

2. 각 문자에 해당하는 ASCII 값을 해당 문자의 위치에 곱한 후 이를 합산한다.

 

h의 위치는 1이므로, 104*1 = 104

e의 위치는 2이므로, 101 * 2 = 202

l의 위치는 3이므로, 108 * 3 = 324

l의 위치는 4이므로, 108 * 4 = 432

o의 위치는 5이므로, 111 * 5 = 555

 

합산된 값을 모두 더한다. 104 + 202 + 324 + 432 + 555 = 1617

생성된 합산 값은 해시 테이블의 크기로 나눈 나머지를 최종 해시 값으로 사용한다. 이 예시는 해시 테이블의 크기가 100으로 가정하자. 따라서 최종 해시값은 1617 % 100 = 17

 

🟩 이미 데이터가 들어 있는 경우, 데이터 저장 위치가 겹쳐 '충돌' 발생. 이 때 값을 '동의어'라 한다.

데이터를 찾을 때, 키 값의 해시값을 구한다 예) 1539(해시값) % 5 = 4 (4번 상자에 저장되어 있다)

해당 박스에 리스트 형태로 데이터가 많다면, 선두를 시작으로 선형 탐색을 하여 구한다.

 

🚀 충돌 시 처리 방법

1. 연쇄법(체이닝)

개방 해싱

충돌된 데이터를 테이블 밖의 별도의 장소에 저장/관리 👉 연결 리스트 사용

해당 박스의 위치에 있던 기존 데이터와 연결한다.

#include <stdio.h>
#define LENGTH 10
#define TRUE -1

int hashTable[LENGTH] = { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 };

int hashFunc(int key) {
	return key % 10;
}

int main(void) {
	int data, hashValue;

	do {
		printf("\n저장할 데이터 = ");
		scanf_s("%d", &data);

		if (data < 0) {
			break;
		}

		// 해시값 구하기
		hashValue = hashFunc(data);
		printf("해시값 = %d %% 10 = %d\n", data, hashValue); // %%는 화면에 %문자를 표시한다.

		// 해시 테이블에 저장
		hashTable[hashValue] = data;
		printf("hashTable[%d]에 %d를 저장합니다.\n", hashValue, data);
	} while (TRUE);

	do {
		printf("\n탐색할 데이터 = ");
		scanf_s("%d", &data);

		if (data < 0) {
			break;
		}

		// 해시값 구하기
		hashValue = hashFunc(data);
		printf("해시값 = %d %% 10 = %d\n", data, hashValue);

		// 탐색한 결과 표시
		if (hashTable[hashValue] == data) {
			printf("hashTable[%d]값은 %d이므로, 발견된 위치를 표시합니다.\n", hashValue, data);
			printf("%d번째에서 발견되었습니다.\n", hashValue);
		}
		else {
			printf("hashTable[%d]값은 %d가 아니므로, '찾을 수 없습니다'를 표시합니다.\n", hashValue, data);
			printf("찾을 수 없습니다.\n");
		}

	} while (TRUE);

	return 0;
}

 

2. 개방 주소법

폐쇄 해싱

해시 테이블 내의 다른 슬롯에 충돌된 데이터를 저장/관리

충돌이 발생한 경우, 다음 후보가 될 주소(배열상의 위치)를 구해서 거기에 저장하는 방식. 해당 주소에도 데이터가 존재한다면 다음 후보 주소를 구하며 비어 있는 곳을 찾을 때까지 다음번 주소를 구한다. '다음 주소'를 어떻게 구하는가는 해시 함수를 여러 개 사용하는 방법이나 '선형 탐색' 등 몇 가지 방법이 있다.

종류 👉  버킷 해싱, 선형 탐사, 이차 탐사, 이중 해싱

#include <stdio.h>
#define LENGTH 10
#define TRUE -1

int hashTable[LENGTH] = { -1, -1, -1, -1, -1, -1, -1, -1, -1, -1 };

int hashFunc(int key) {
	return key % 10;
}

int main(void) {
	int data, hashValue;
	int pos; // 저장 위치, 검색 위치

	do {
		printf("\n저장할 데이터 = ");
		scanf_s("%d", &data);

		if (data < 0) {
			break;
		}

		// 해시값 구하기
		hashValue = hashFunc(data);
		printf("해시값 = %d %% 10 = %d\n", data, hashValue); // %%는 화면에 %문자를 표시한다.

		// 데이터의 저장 위치를 정함
		pos = hashValue;
		printf("저장 위치 pos = %d\n", pos);
		while (hashTable[pos] != -1) {
			// 다음 배열 요소에서 데이터를 저장할 수 있는지 확인
			pos++;

			// 배열 마지막 요소까지 데이터 저장 가능 여부를 확인하면 배열 첫 번째 요소를 지정
			if (pos >= LENGTH) {
				pos = 0;
			}
			printf("저장 위치 pos = %d\n", pos);

			// 해시값의 배열 요소 위치까지 돌아오면
			// 해시 테이블에 데이터가 가득 찬 것이므로 반복을 종료
			if (pos == hashValue) {
				break;
			}
		}

		if (hashTable[pos] == -1) {
			// 해시 테이블에 데이터가 가득 차지 않았다면 데이터를 저장
			hashTable[pos] = data;
			printf("hashTable[%d]에 %d를 저장합니다\n", pos, data);
		}
		else {
			printf("해시 테이블이 가득 찼습니다.\n");
		}
	} while (TRUE);

	do {
		printf("\n탐색할 데이터 = ");
		scanf_s("%d", &data);

		if (data < 0) {
			break;
		}

		// 해시값 구하기
		hashValue = hashFunc(data);
		printf("해시값 = %d %% 10 = %d\n", data, hashValue);

		// 데이터를 검색
		pos = hashValue;
		printf("탐색 위치 pos = %d\n", pos);
		while (hashTable[pos] != -1 && hashTable[pos] != data) {
			// 다음 배열 요소로 탐색 위치를 이동
			pos++;

			// 배열 마지막 요소까지 탐색하면 배열 첫 번째 요소를 지정
			if (pos >= LENGTH) {
				pos = 0;
			}
			printf("탐색 위치 pos = %d\n", pos);

			// -1을 찾았거나, 해시값의 인덱스 위치로 돌아오면, 데이터를 찾을 수 없는 것이므로 반복을 종료
			if (hashTable[pos] == -1 || pos == hashValue) {
				break;
			}
		}

		// 탐색한 결과를 표시
		if (hashTable[pos] == data) {
			printf("hashTable[%d]값은 %d이므로, 발견한 위치를 표시합니다.\n", pos, data);
			printf("%d번째에서 발견되었습니다.\n", pos);
		}
		else {
			printf("hashTable[%d]값은 %d이므로, '찾을 수 없습니다.'를 표시합니다.\n", pos, hashTable[pos]);
			printf("찾을 수 없습니다.\n");
		}

	} while (TRUE);

	return 0;
}

 

 

do~while 문을 사용하면 조건식과 상관없이 무조건 실행한 후 조건이 맞는지 검사하므로  반복해서 데이터를 저장하기 좋다.

해시 테이블의 이상적인 시간 복잡도는 O(1)이다. 하지만 해시 충돌이 일어나면 한 번으로는 찾을 수 없다.

데이터 저장뿐 아니라, 탐색에서도 해시 충돌을 해결해야 한다.

 

🌟 버킷 해싱

충돌이 발생하면 해시 값에서 일정한 간격으로 떨어진 위치를 찾아 해당 위치에 데이터를 삽입한다.

이 방식은 일정한 간격을 유지하기 때문에 충돌이 발생했을 때, 연속된 위치에 데이터가 저장될 가능성이 있다.

하지만 간격을 적절히 선택하지 않으면 '클러스터링' 문제가 발생할 수 있다.

 

🌟 선형 탐사

충돌이 발생하면 해시 값에서 일정한 간격(보통 1)만큼 떨어진 위치를 찾아 해당 위치에 데이터를 삽입한다.

이후에 충돌이 발생하면 다음 위치를 탐사하면 빈 버킷을 찾을 때까지 반복한다.

선형 탐사는 간단하고 구현하기 쉽지만, 클러스터링 문제가 발생할 수 있다.

 

🌟 이차 탐사

충돌이 발생하면 해시 값에서 일정한 간격(1, 4, 9, 16 ...) 의 제곱만큼 떨어진 위치를 찾아 해당 위치에 데이터를 삽입한다.

선형 탐사보다는 좀 더 분산된 위치에 데이터를 저장할 수 있다.

하지만 이차 탐사 역시 클러스터링 문제를 완전히 해결할 수는 없다.

 

🌟 이중 해싱

충돌이 발생하면 해시값과 더불어 또 다른 해시 함수를 사용하여 새로운 위치를 계산한다.

이차 탐사보다 더 분산된 위치에 데이터를 저장할 수 있으며, 클러스터링 문제를 완화할 수 있다.

이중 해싱에서는 두 번째 해시 함수의 선택이 중요하다. 충돌이 발생할 때마다 적절한 두 번째 해시 값을 선택해야 한다.

 

🚀 해시 테이블의  문제점

배열의 크기가 너무 작으면 충돌이 많아지고, 선형 탐색의 빈도가 높아지게 된다. 너무 많으면 데이터가 없는 빈 상자가 많아져서 메모리를 낭비하게 된다. 따라서 배열의 크기를 적절히 설정하는 것이 중요하다.

 

'해시값으로부터 원래 값을 추측할 수 없다'

암호 등의 보안 용도로 사용되는 조건으로서 해시 테이블에서는 필수적인 조건은 아니다.

 

🟩 삭제

데이터의 삭제가 차후의 탐색을 방해하면 안된다.

👉 단순히 빈 슬롯으로 두면 탐색이 해당 슬롯에서 종료되므로 그 이후의 데이터는 고립된다.

삭제로 생긴 빈 슬롯은 나중에 삽입 과정에서 사용되어야 한다.

 

🌟 비석

삭제된 데이터의 위치에 '비석'이라는 특별한 표시를 한다.

탐색 : 탐색하는 동안 비석을 만나면 탐색을 계속 진행

삽입 : 비석이 표시된 위치를 빈 위치로 간주하여 새 데이터를 삽입

비석의 개수가 증가할수록 평균 탐색 거리가 증가