[알고리즘] 해쉬 테이블(hash table) - 선형 프로빙(linear probing)

오늘은 오픈 어드레싱 중에서 선형 프로빙(linear probing)에 대해 알아보겠습니다.

 

해쉬테이블은 저장할 key 값은 달라도 hash function을 수행한 결과값은 동일할 수 있습니다.

이를 충돌(collision)이라고 부릅니다.

충돌을 해결하기 위한 방법에는 체인을 이용하거나 오픈 어드레싱 등을 이용할 수 있습니다.

오픈 어드레싱은 충돌을 피하기 위해 key를 해쉬 테이블에 직접 저장하는 방법입니다.

오픈 어드레싱에는 선형 프로빙(linear probing), 이차식 프로빙(quadratic probing), 이중 해싱(double hashing)이 있습니다.

그 중에서 선형 프로빙(linear probing)은  hash function을 수행한 결과값은 동일할 경우 뒤로 한 칸씩 미루면서 빈 칸이 존재한다면 그곳에 저장하는 방법입니다.

h(k,i) = (k+i) mod m으로 표현할 수 있습니다.

  (k: key값

   i: 중복 횟수

   m: 해쉬 테이블의 크기)

 

선형 프로빙(linear probing)의 장점: 구현이 쉽다.

선형 프로빙(linear probing)의 단점: primary clusturing (한 번 충돌 발생 시 그 부분에서 계속 충돌 발생)

 

m = 13,

k = {5, 14, 29, 25, 17, 21, 18, 32, 20, 9, 15, 27},

h(k,i) = (k+i) mod 13

인 경우에 대해 살펴보겠습니다.

(i는 중복횟수이므로 처음에는 당연히 0 입니다.)

 

 

이런식으로 진행하다보면 결과는 이렇게 될 것입니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define hash_mod 13

void insert(int table[], int key, int table_size) {
	int i = 0;
	int result = key % hash_mod;
	while (i < table_size) {
		if (table[result + i] == 0) {
			table[result + i] = key;
			break;
		}
		else 
			i++;
	}
}

void search(int table[], int key, int table_size) {
	int i = 0;
	int result = key % hash_mod;
	while (1) {
		if (table[result + i] == key) {
			printf("\nhash table[%d]: %d", result + i, table[result + i]);
			break;
		}	
		else 
			i++;

		if (table[result + i] == NULL || i == table_size) {
			return -1;
			break;
		}
	}
}
int main() {
	int t[13] = { NULL, };
	int k[12] = { 5,14,29,25,17,21,18,32,20,9,15,27 };

	for (int i = 0; i < 12; i++) {
		insert(t, k[i], 13);
	}
	for (int i = 0; i < 13; i++) {
		printf("%d\n", t[i]);
	}

	search(t, 27, 13);
	return 0;
}