해쉬 테이블 - Collison 문제 해결책

 

오픈 어드레싱 방법(Open addressing method)

오픈 어드레싱 방법은 충돌이 발생하면 다른 자리에 대신 저장한다는 의미가 담겨있다.
 

선형 조사법과 이차 조사법

선형 조사법이란?

충돌이 발생했을 때 옆자리가 비었는지 살펴보고,
비었을 경우 그 자리에 대신 저장하는 것이다.
 
예를 들어서 다음과 같이 정의된 함수 f(x)가 있고
테이블의 내부 저장소가 배열이라고 가정해보자.
 

• 해쉬 함수 key % 7

 
그러면 키가 9인 데이터는 해쉬 값이 2이므로 인덱스가 2인 위치에 저장된다.
 
이어서 키가 2인 데이터가 등장했다고 가정하면,
이 경우 해쉬 값이 2이기 때문에 앞서 저장한 키가 9인 데이터와 충돌이 발생한다.
이렇듯 충돌이 발생했을 때 인덱스 값이 3인 바로 옆자리를 살피는 것이 선형 조사법이다.
따라서 키가 2인 데이터의 저장결과는 3번 인덱스에 저장이 된다.
 
물론 옆자리가 비어있지 않을 경우,
한 칸 더 이동해서 자리를 살피게 된다.
 
정리하자면, k의 키에서 충돌 발생시 선형 조사법의 조사 순서는(빈자리 찾는 순서는) 다음과 같이 전개가 된다.
 
f(k)+1 -> f(k)+2 -> f(k)+3 -> f(k)+4 . . . 
 
그런데 이런 선형 조사법은 충돌 횟수가 증가함에 따라 클러스터 현상이 발생한다는 단점이 있다.
(클러스터 현상이란,
특정 영역에 데이터가 집중적으로 몰리는 현상이다.)
 
이러한 클러스터 현상을 해소하기위해
좀 더 멀리서 빈 공간을 찾는 것이 이차 조사법이다.
 
f(k)+1^2 -> f(k)+2^2 -> f(k)+3^2 -> f(k)+4^2 . . .
 
선형 조사법은 충돌 발생시 N칸 옆의 슬롯을 검사한다면,
이차 조사법은 N^2칸 옆의 슬롯을 검사한다.
 

이중 해쉬

 
이차 조사법은 선행 조사법의 문제점을 어느 정도 해결하지만,
전혀 문제가 없는 것은 아니다.
이차 조사법의 문제점으로 지적되는 사항은 다음과 같다.
 
해쉬 값이 같으면, 충돌 발생시 빈 슬롯을 찾기 위해서 접근하는 위치가 늘 동일하다.
 
이렇듯 해쉬 값이 같을 경우, 빈 슬롯을 찾아서 접근하는 위치가 동일하기 때문에,
선형 조사법보다는 낮지만, 접근이 진행되는 슬롯을 중심으로 클러스터 현상이 발생할 확륙은
여전히 높을 수 밖에 없다.
 
이러한 방법을 해결할 수 있는 것이 이중 해쉬이다.

 
이중 해쉬란?

이중 해쉬는 빈 공간을 선택하는 방식을 불규칙적으로 구성하는 것이다.
 
이중 해쉬 방법에서는 두 개의 해쉬 함수를 마련한다.
하나는 키를 근거로 저장위치를 결정하는 것이고
다른 하나는 충돌이 발생했을 때, 몇 칸 뒤에 위치한 슬롯을 살펴볼 그 거리를 결정하기 위한 것이다.
 

• 1차 해쉬 함수    키를 근거로 저장위치를 결정하기 위한 것
• 2차 해쉬 함수    충돌 발생시 몇 칸 뒤를 살필지 결정하기 위한 것

 
그럼 확실한 이해를 위해서 이중 해쉬의 두 해쉬 함수를 정의해보겠다.
 

• 1차 해쉬 함수   h1(k) = k % n
• 2차 해쉬 함수   h2(k) = 1 + (k % c)

 
위 2차 해쉬 함수가 절대적인 해쉬 함수식은 아니지만, 일반적인 형태이다.
보통 c는 일반적으로 배열의 길이보다 작은 소수 중 하나로 결정하게 된다.
 
1을 더하는 이유는 2차 해쉬 값이 0이 되는 것을 방지하기 위해서이다.
배열의 길이보다 작은 값을 선정하는 이유는 가급적 1차 해쉬 값을 넘어서지 않게 하기 위함이다.
소수로 결정하는 이유는, 클러스터 현상 발생 확률을 현저히 낮춘다는 통계를 근거로 한 것이다.
 
이러한 이유로 클러스터 현상의 발생 확률을 현저히 낮출 수 있다.
참고로 실제로도 이중 해쉬는 이상적인 충돌 해결책으로 알려져있다.
 

클로즈드 어드레싱 방법(Closed addressing method)

닫힌 주소 방법은 무슨 일이 있어도 자신의 자리에 저장한다는 의미이다.

 
 

체이닝

충돌 해결책은 앞서 소개한 방법들과 해결 방식이 근본적으로 다르다.
클로즈드 어드레싱 방법으로 자리를 여러 개 마련하여 충돌을 해결하는 것이다.
 
여러 개의 자리를 마련하는 방법으로는 배열과 리스트를 이용할 수 있다.
배열을 이용하게 되면 메모리 낭비가 너무 심하게 발생하게 된다.
 
때문에 체이닝은 주로 리스트를 이용한다.
따라서 탐색을 위해서는 동일한 해쉬 값으로 묶여있는 연결된
충돌의 확률이 높지 안다면 연결된 슬롯의 길이는 부담스럽지 않을 정도이다.
 

 

출동 문제의 해결을 위한 체이닝 구현

 
 

#pragma once
#include "person.h"

typedef int Key;
typedef Person* Value;

typedef struct _slot {
	Key key;
	Value val;
} Slot;

 
열린 어드레싱 방법은 enum 선언과 관련 구조체의 정보가 없다.
이는 닫힌 어드레싱을 하는 경우에는 슬롯의 상태 정보를 표시할 필요가 없기 때문이다.
 

#include "Slot2.h"
#include "DLinkedList.h"

#define MAX_TBL	100

typedef int (*HashFunc)(Key h);

typedef struct _table
{
	List tbl[MAX_TBL];
	HashFunc* hf;
} Table;

void TBLInit(Table* pt, HashFunc* f);
void TBLInsert(Table* pt, Key k, Value v);
Value TBLDelete(Table* pt, Key k);
Value TBLSearch(Table* pt, Key k);

 
이전에 보인 Table.h와 가장 큰 차이점은
테이블의 저장소였던 Slot형 배열을 List형 배열로 바꾸었다는 점이다.
각 요소가 연결 리스트로 이뤄진 셈이 되었다.
 
체이닝의 구현(연결리스트로 구현)을 위한 두 가지 방법이 있다.

• 슬롯이 연결 리스트의 노드 역할을 하게 하는 방법
• 연결 리스트의 노드와 슬롯을 구분하는 방법

 
연결 리스트와 구조체 Slot관계에서
구조체 Slot을 연결리스트 노드로 활용하는 것 보단,
슬롯과 노드를 엄연히 구분하는 것이 좋은 구조로 알려져있는 방법이다.
이는 노드에 슬롯의 주소 값을 저장하는 형태이다.
 
 
채이닝 기법 해쉬 구현 소스코드는 아래와 같다.

#include <stdio.h>
#include <stdlib.h>
#include "Table2.h"
#include "DLinkedList.h"

void TBLInit(Table* pt, HashFunc* f)
{
	int i;

	for (i = 0; i < MAX_TBL; i++)
		ListInit(&(pt->tbl[i]));

	pt->hf = f;
}

void TBLInsert(Table* pt, Key k, Value v)
{
	int hv = pt->hf(k);
	Slot ns = { k,v };

	if (TBLSearch(pt, k) != NULL)
	{
		printf("키 중복 오류 발생 \n");
		return;
	}
	else
	{
		LInsert(&(pt->tbl[hv]), ns);
	}
}

Value TBLDelete(Table* pt, Key k)
{
	int hv = pt->hf(k);
	Slot cSlot;

	if (LFirst(&(pt->tbl[hv]), &cSlot)) {
		if (cSlot.key == k) {
			LRemove(&(pt->tbl[hv]));
			return cSlot.val;
		}
	}
	else {
		while (LNext(&(pt->tbl[hv]), &cSlot))
		{
			if (cSlot.key == k) {
				LRemove(&(pt->tbl[hv]));
				return cSlot.val;
			}
			else {
				while (LNext(&(pt->tbl[hv]), &cSlot))
				{
					if (cSlot.key == k) {
						LRemove(&(pt->tbl[hv]));
						return cSlot.val;
					}
				}
			}
		}
	}

	return NULL;
}

Value TBLSearch(Table* pt, Key k)
{
	int hv = pt->hf(k);
	Slot cSlot;

	if (LFirst(&(pt->tbl[hv]), &cSlot)) {
		if (cSlot.key == k) {
			return cSlot.val;
		}
		else {
			while (LNext(&(pt->tbl[hv]), &cSlot))
			{
				if (cSlot.key == k) return cSlot.val;
			}
		}
	}

	return NULL;
}

 
실행 결과