테이블(Table)과 해쉬(Hash)

1. 빠른 탐색을 보이는 해쉬 테이블

이번에 소개하는 내용도 탐색과 관련이 있다는 점에서 탐색 1과 탐색 2의 연장으로 볼 수 있다.

하지만 트리와 관련된 어떠한 것도 언급하지 않는다는 점에서 구분이 된다.

이번에 소개하는 내용은 앞 탐색 챕터보다 어렵지 않으니 긴장을 조금 풀어도 좋다.

---

앞서 소개한 AVL 트리는 탐색과 관련하여 매우 만족스러운 성능을 보였다.

하지만 탐색 키의 비교 과정을 거치면서 찾는 대상에 가까워지는 방식이기 때문에, 원하는 바를 '단번에' 찾아내는 방식이라고 말하기는 어렵다.

때문에 상황에 따라서는 이러한 AVL 트리의 성능에 만족하지 못할 수도 있다.

그리고 이러한 상황에서 도입을 검토할 수 있는 자료구조가 바로 '테이블'이다.

"그럼 테이블을 이용하면 탐색대상을 단번에 찾을 수 있나요?"

AVL 트리의 탐색 연산이 $O(log n)$의 시간 복잡도를 보이는 반면, 테이블 자료구조의 탐색 연산은 $O(1)$의 시간 복잡도를 보이니, 테이블의 탐색 성능을 표현하는데 있어서 '단번에'라는 표현을 써도 괜찮지 않겠는가!

참고로 테이블의 탐색원리를 이해하면 테이블의 시간 복잡도가 $O(1)$인 이유를 바로 알 수 있다.

자! 그럼 그림을 통해서 테이블 자료구를 소개하겠다.

위의 그림에서 보이는 것은 문서편집 과정에서 한 번 정도는 만들어 봤을법한 '표'이다.

그리고 이것이 바로 '테이블'이다(아시다시피 표를 영어로 테이블이라 한다).

하지만 자료구조의 관점에서 모든 표를 가리켜 테이블이라 하지는 않는다.

표에 저장된 데이터의 형태가 다음과 같을 때만 테이블로 구분 짓는다.

"저장되는 데이터는 키(key)와 값(value)이 하나의 쌍을 이룬다."

이렇듯 테이블에 저장되는 모든 데이터들은 이를 구분하는 '키'가 있어야 하고, 이 키는 데이터를 구분하는 기준이 되기 때문에 중복이 되어서는 안 된다.

정리하면, 테이블에는 키와 관련해서 다음의 조건이 존재한다.

"키(key)가 존재하지 않는 '값'은 저장할 수 없다."

"그리고 모든 키는 중복되지 않는다."

이렇듯 테이블의 핵심은, 키와 값이 하나의 쌍을 이루어 저장되는 데이터의 유형에 있다.

어느 정도 테이블이라는 자료구조를 이해하였을 것이다.

---

그럼 배열을 기반으로 누구나 쉽게 이해할 수 있는 간단한 예제를 작성하여, 테이블 자료구조를 코드상에서 보이도록 하겠다.

#include <stdio.h>

typedef struct _empInfo
{
	int empNum;    // 직원의 고유번호
	int age;     // 직원의 나이
}EmpInfo;

int main(void)
{
	EmpInfo empInfoArr[1000];
	EmpInfo ei;
	int eNum;

	printf("사번과 나이 입력: ");
	scanf("%d %d", &(ei.empNum), &(ei.age));
	empInfoArr[ei.empNum] = ei;    // 단번에 저장!

	printf("확인하고픈 직원의 사번 입력: ");
	scanf("%d", &eNum);

	ei = empInfoArr[eNum];    // 단번에 탐색!
	printf("사번 %d, 나이 %d \n", ei.empNum, ei.age);
	return 0;
}

저장과 탐색의 원리만 확인할 수 있도록 main 함수를 간단히 작성하였다.

그럼 위 코드에서 선언된 구조체를 관찰해보자.

typedef struct _empInfo
{
	int empNum;    // 직원의 고유번호
	int age;     // 직원의 나이
} EmpInfo;

이는 키와 값을 하나의 쌍으로 묶기 위해서 정의된 구조체이다.

즉, 직원의 고유번호를 키로 결정하였다.

그럼 이어서 이 구조체를 기반으로 하는 다음 배열 선언을 보자.

EmpInfo empInfoArr[1000]; // 직원들의 정보를 저장하기 위해 선언된 배열

이 배열을 가리켜 '테이블'이라 하기엔 많은 것이 부족해 보인다.

이것이 테이블이라 할 수 있으려면 다음 조건을 만족해야 하기 때문이다.

다시 말해서 다음 조건만 만족한다면 이렇듯 단순한 배열도 테이블, 또는 테이블의 일부라 할 수 있다.

"키를 결정하였다면, 이를 기반으로 데이터를 단번에 찾을 수 있어야 한다."

즉, 테이블에서 의미하는 키는 데이터를 찾는 도구가 되어야 한다.

그것도 단번에 찾을 수 있는 도구가 되어야 한다.

따라서 다음과 같은 코드를 예제에서 작성하였다.

• 저장

empInfoArr[ei.empNum] = ei;    // 단번에 저장!

• 탐색

ei = empInfoArr[eNum];    // 단번에 탐색!

이 두 개의 문장을 통해서 알 수 있는 사실은 다음과 같다.

"직원의 고유번호를 인덱스 값으로 하여, 그 위치에 데이터를 저장한다."

이렇듯 '키의 값은 저장위치'라는 관계를 형성하여, 단번에 데이터를 저장하고 단번에 데이터를 탐색할 수 있게 하였다.

따라서 위의 배열은 테이블의 구현결과라 할 수 있다.

"그럼 직원 고유번호의 범위가 10000~999999라면 어떻게 해야 하나요?"

"위와 같은 방식으로 테이블을 구성하려면 매우 큰 배열이 필요하겠죠?"

문제점을 정확히 지적하였다!

이러한 문제점은 앞서 보인 테이블의 예에서 테이블의 핵심인 '해쉬'와 관련된 내용이 빠졌기 때문에 등장한 것이다.

---

예제에서 보인 테이블과 관련하여 지적한 문제점 두 가지를 정리하면 다음과 같다.

"직원 고유번호의 범위가 배열의 인덱스 값으로 사용하기에 적당하지 않다."

"직원 고유번호의 범위를 수용할 수 있는 매우 큰 배열이 필요하다."

이 두 가지 문제를 동시에 해결해주는 것이 바로 '해쉬 함수'이다.

그럼 해쉬 함수의 소개를 위해서 앞서 보인 예제를 재구현하되, 다음과 같은 가정을 추가하겠다.

"직원의 고유번호는 입사 년도 네 자리와 입사순서 네 자리로 구성된다."

예를 들어서 2012년에, 그리고 이 회사에 세 번째로 입사한 직원의 고유번호는 20120003이 되고, 뒤를 이어서 같은 해에 입사한 직원의 고유번호는 20120004가 된다.

이렇듯 입사 순서를 네 자리로 구성한 것을 보면 직원의 수가 언젠가는 천명을 넘어설 수 있다는 생각을 한 모양인데, 이는 먼 훗날의 이야기이고 실제로는 백 명 이상을 채용할지도 의문인 상황이다.

따라서 배열 길이의 최소화를 위해 노력한다는 가정하에 예제를 재구현하였다.

#include <stdio.h>

typedef struct _empInfo
{
	int empNum;    // 직원의 고유번호
	int age;     // 직원의 나이
}EmpInfo;

int GetHashValue(int empNum)
{
	return empNum % 100;
}

int main(void)
{
	EmpInfo empInfoArr[100];

	EmpInfo emp1={20120003, 42};
	EmpInfo emp2={20130012, 33};
	EmpInfo emp3={20170049, 27};

	EmpInfo r1, r2, r3;

	// 키를 인덱스 값으로 이용해서 저장
	empInfoArr[GetHashValue(emp1.empNum)] = emp1;
	empInfoArr[GetHashValue(emp2.empNum)] = emp2;
	empInfoArr[GetHashValue(emp3.empNum)] = emp3;

	// 키를 인덱스 값으로 이용해서 탐색
	r1 = empInfoArr[GetHashValue(20120003)];
	r2 = empInfoArr[GetHashValue(20130012)];
	r3 = empInfoArr[GetHashValue(20170049)];

	// 탐색 결과 확인
	printf("사번 %d, 나이 %d \n", r1.empNum, r1.age);
	printf("사번 %d, 나이 %d \n", r2.empNum, r2.age);
	printf("사번 %d, 나이 %d \n", r3.empNum, r3.age);
	return 0;
}

위의 예제에서는 길이가 100인 배열을 선언하였다.

직원의 수가 100명을 넘길 경우를 고려하지 않은 것이다.

그리고 데이터의 저장위치를 결정하는데 있어서 직원의 고유번호를 활용하되, 다음 함수를 이용해서 가공의 과정을 거쳤다.

int GetHashValue(int empNum)
{
	return empNum % 100;
}

위의 함수에서 100으로 % 연산을 하는 것은 다음의 의미를 지닌다.

"여덟 자리의 수로 이뤄진 직원의 고유번호를 두 자리의 수로 변경한다."

실제로는 앞의 숫자 여섯 개를 잘라낸 것이지만 이것도 변경의 일종이다.

그럼 100으로 나눠서 그 나머지를 취하는 이 연산을 함수 $f(x)$라 하자.

그러면 이 함수의 기능은 다음과 같이 표현할 수 있다.

위 그림에서 보이는 $f(x)$를 가리켜 '해쉬 함수(hash function)'라 한다.

그리고 이러한 해쉬 함수는 넓은 범위의 키로 변경하는 역할을 한다.

실제로 위의 예제에서는 해쉬 함수와 관련해서 흔히 거론되는 % 연산자를 이용하여 여덟 자리의 키를 두 자리의 키로 바꾸었다.

그럼 이어서 위 예제의 문제점을 생각해보자.

상황은 이렇다!

직원의 수가 100명을 넘어선 것이다!

그리하여 직원번호 20210103이 형성되었고 이로 인해 다음과 같은 문제가 발생하였다.

위 그림에서 보이듯이 서로 다른 두 개의 키가 해쉬 함수를 통과하였는데, 그 결과가 03으로 모두 동일하다.

이러한 상황을 가리켜 '충돌(collision)'이라 하는데, 이러한 충돌은 배열의 길이를 늘리는 등의 방법으로 피해야 할 상황이 아니다.

배열의 길이를 늘리는 방법으로 충돌을 완전히 피할 수 있을지 의문도 들지만, 완전히 피할 수 있다 하더라도 매우 비합리적인 방법일 수밖에 없다.

때문에 충돌은 피해야 하는 상황이 아니라 '해결해야 하는 상황'인 것이다.

우리는 아직 해쉬 함수에 대한 이야기도 다 하지 않았으니, 충돌의 해결방법에 대한 언급은 잠시 뒤로 미뤄두겠다.

참고로 충돌의 해결방법에 따라서 테이블의 구조가 달라지는 경우가 있을 정도로 충돌의 해결방법은 테이블에 있어서 큰 의미를 갖는다.

---

앞서 예제를 통해서 테이블과 해쉬 함수의 구현을 간단히 보였지만, 테이블의 구현사례로는 부족한 감이 없지 않다.

따라서 어느 정도 모습을 갖춰서 다시 한 번 구현하고자 한다.

그럼 먼저 테이블에 저장할 대상에 대한 헤더파일과 소스파일을 보이겠다.

Person.h

#ifndef __PERSON_H__
#define __PERSON_H__

#define STR_LEN    50

typedef struct _person
{
	int ssn;    // 주민등록번호 
	char name[STR_LEN];    // 이름
	char addr[STR_LEN];    // 주소
} Person;


int GetSSN(Person * p);

void ShowPerInfo(Person * p);

Person * MakePersonData(int ssn, char * name, char * addr);

#endif

---

Person.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "Person.h"

int GetSSN(Person * p)
{
	return p->ssn;
}

void ShowPerInfo(Person * p)
{
	printf("주민등록번호: %d \n", p->ssn);
	printf("이름: %s \n", p->name);
	printf("주소: %s \n\n", p->addr);
}

Person * MakePersonData(int ssn, char * name, char * addr)
{
	Person * newP = (Person*)malloc(sizeof(Person));

	newP->ssn = ssn;
	strcpy(newP->name, name);
	strcpy(newP->addr, addr);
	return newP;
}

위의 헤더파일에 정의된 Person 구조체의 변수가(정확히는 구조체 변수의 주소 값이) 테이블에 저장될 '값'이다.

그리고 그 중에서 구조체의 멤버 ssn, 즉 주민등록번호를 '키'로 결정하였다.

따라서 키를 별도로 추룰하는데 사용하기 위해서 GetSSN 함수를 정의하였다.

그리고 Person 구조체 변수의 생성 및 초기화의 편의를 위해서 MakePersonData 함수도 정의하였다.

이어서 테이블의 구현과 관련이 있는 파일들을 소개하겠다.

첫 번째로 소개하는 헤더파일은 테이블의 슬롯(이에 대해서 아직 설명하지 않았음)을 정의한 헤더파일이다.

---

Slot.h

#ifndef __SLOT_H__
#define __SLOT_H__

#include "Person.h"

typedef int Key;
typedef Person * Value;

enum SlotStatus {EMPTY, DELETED, INUSE};

typedef struct _slot
{
	Key key;
	Value val;
	enum SlotStatus status;
}Slot;

// Slot과 관련해서는 별도의 함수를 정의하지 않는다.
#endif

위에서 보인 구조체 Slot을 통해서 짐작했겠지만, 슬롯이란 '테이블을 이루는, 데이터를 저장할 수 있는 각각의 공간'을 의미한다.

그리고 위의 typedef 선언에서도 보이듯이 키와 값은 다음과 같이 결정하였다.

- 키: 주민등록번호

- 값: Person 구조체 변수의 주소 값

그리고 enum 선언을 통해서 슬롯의 상태를 나타내는 상수 EMPTY, DELETED, INUSE가 정의되었고, 이를 기반으로 다음과 같이 Slot 구조체의 멤버를 선언하였다.

enum SlotStatus status; // 슬롯의 상태를 나타내는 멤버

- EMPTY: 이 슬롯에는 데이터가 저장된 바 없다.

- DELETED: 이 슬롯에는 데이터가 저장된 바 있으나 현재는 비워진 상태다.

- INUSE: 이 슬롯에는 현재 유효한 데이터가 저장되어 있다.

이 중에서 EMPTY와 INUSE의 필요성은 이해되지만, DELETED의 필요성에는 의문이 생길 것이다.

사실 잠시 후에 보일 테이블의 구현결과만 놓고 본다면 DELETED는 우리에게 불필요하다.

그러나 보편적으로 슬롯의 상태는 위와 같이 세 가지로 구분한다는 사실을 알고 있을 필요가 있어서 DELETED를 추가하였다.

이것이 필요한 이유는 '충돌'의 해결책을 소개하면서 같이 소개하겠다

그럼 이어서 테이블의 실질적인 구현에 해당하는 헤더파일과 소스파일을 보이겠다.

---

Table.h

#ifndef __TABLE_H__
#define __TABLE_H__

#include "Slot.h" 

#define MAX_TBL     100

typedef int HashFunc(Key k);

typedef struct _table
{
	Slot 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);

#endif

---

Table.c

#include <stdio.h>
#include <stdlib.h>
#include "Table.h"

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

	for(i=0; i<MAX_TBL; i++)
		(pt->tbl[i]).status = EMPTY;

	pt->hf = f;
}

void TBLInsert(Table * pt, Key k, Value v)
{
	int hv = pt->hf(k);
	pt->tbl[hv].val = v;
	pt->tbl[hv].key = k;
	pt->tbl[hv].status = INUSE;
}

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

	if((pt->tbl[hv]).status != INUSE)
	{
		return NULL;
	}
	else
	{
		(pt->tbl[hv]).status = DELETED;
		return (pt->tbl[hv]).val;
	}
}

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

	if((pt->tbl[hv]).status != INUSE)
		return NULL;
	else
		return (pt->tbl[hv]).val;
}

직접 정의한 해쉬 함수를 등록하도록 디자인되었다는 사실과 Slot의 배열로 테이블을 구성하였다는 사실에만 주목을 하면 나머지는 쉽게 이해할 수 있다.

그럼 이어서 위의 테이블을 대상으로 하는 main 함수를 소개하겠다.

---

SimpleHashMain.c

#include <stdio.h>
#include <stdlib.h>
#include "Person.h"
#include "Table.h"

int MyHashFunc(int k)
{
	return k % 100;    // 키를 부분적으로만 사용한 별로 좋지 않은 해쉬의 예!!!
}

int main(void)
{
	Table myTbl;
	Person * np;
	Person * sp;
	Person * rp;

	TBLInit(&myTbl, MyHashFunc);

	// 데이터 입력
	np = MakePersonData(20120003, "Lee", "Seoul");
	TBLInsert(&myTbl, GetSSN(np), np);

	np = MakePersonData(20130012, "KIM", "Jeju");
	TBLInsert(&myTbl, GetSSN(np), np);

	np = MakePersonData(20170049, "HAN", "Kangwon");
	TBLInsert(&myTbl, GetSSN(np), np);

	// 데이터 검색
	sp = TBLSearch(&myTbl, 20120003);
	if(sp != NULL)
		ShowPerInfo(sp);

	sp = TBLSearch(&myTbl, 20130012);
	if(sp != NULL)
		ShowPerInfo(sp);

	sp = TBLSearch(&myTbl, 20170049);
	if(sp != NULL)
		ShowPerInfo(sp);

	// 데이터 삭제
	rp = TBLDelete(&myTbl, 20120003);
	if(rp != NULL)
		free(rp);

	rp = TBLDelete(&myTbl, 20130012);
	if(rp != NULL)
		free(rp);

	rp = TBLDelete(&myTbl, 20170049);
	if(rp != NULL)
		free(rp);

	return 0;
}

이로써 우리가 모델로 삼을 수 있는 테이블의 구현이 완료되었다.

물론 위의 테이블 구현은 '충돌'에 대한 해결책을 담고 있지 않다.

따라서 잠시 후에는 이 예제에 충돌에 대한 해결책까지 담을 예정이다.

---

좋은 해쉬 함수의 조건을 언급하기에 앞서 좋은 해쉬 함수를 사용한 결과와 좋지 않은 해쉬 함수를 사용한 결과를 비교해 보이겠다.

먼저 좋은 해쉬 함수를 사용한 결과는 다음과 같다.

위 그림은 테이블의 메모리 상황을 표현한 것이다.

그림에서 검은 영역은 데이터가 채워진 슬롯을 의미하고, 반대로 흰 영역은 빈 슬롯을 의미한다.

이 그림을 보면 데이터가 테이블의 전체 영역에 고루 분포되어 있음을 알 수 있다.

이렇듯 고루 분포된다는 것은 그만큼 '충돌'이 발생할 확률이 낮다는 것을 의미한다.

충돌의 해결책이 마련되어 있다 하더라도 충돌이 덜 발생해야 데이터의 저장, 삭제 및 탐색의 효율을 높일 수 있다.

때문에 좋은 해쉬 함수는 '충돌을 덜 일으키는 해쉬 함수'라고도 말할 수 있다.

반면 다음 그림에서는 좋지 못한 해쉬 함수의 사용결과를 보이고 있다.

위 그림에서는 테이블의 특정 영역에 데이터가 몰린 상황을 보이고 있다.

이는 해쉬 함수가 특정 영역에 데이터가 몰리도록 '해쉬 값(해쉬 함수가 만들어 낸 값)'을 생성한 결과이다.

때문에 충돌이 발생할 확률이 그만큼 높은 상황이다.

그렇다면 좋은 해쉬 함수를 디자인하는 방법은 무엇일까?

여기에 정답은 없다.

상황에 따라서, 다시 말해서 키의 특성에 따라서 달라지기 때문이다.

하지만 일반적으로 다음의 사항을 고려해서 해쉬 함수를 정의하라고 조언한다.

"좋은 해쉬 함수는 키의 일부분을 참조하여 값을 만들지 않고, 키 전체를 참조하여 해쉬 값을 만들어 낸다."

아무래도 적은 수의 데이터를 조합하여(키의 일부분을 조합하여) 해쉬 값을 생성하는 것보다 많은 수의 데이터를 조합하여(키 전부를 조합하여) 해쉬 값을 생성했을 때, 보다 다양한 값의 생성을 기대할 수 있을 것이다.

위의 조언은 바로 이런 단순한 사실을 근거로 한 것이다.

---

좋은 해쉬 함수의 디자인 방법은 키의 특성에 따라 달라진다.

때문에 해쉬 함수의 디자인에 있어서 절대적인 방법은 존재하지 않는다.

다만 위의 조언, 키 전체를 참조하는 방법과 관련하여 다양한 방법이 소개되고 있는데, 그 중 하나는 다음과 같다.

"여덟 자리의 수로 이뤄진 키에서 다양한 해쉬 값 생성에 도움을 주는 네 자리의 수를 뽑아서 해쉬 값을 생성한다."

키의 특정 위치에서 중복의 비율이 높거나, 아예 공통으로 들어가는 값이 있다면, 이를 제외한 나머지를 가지고 해쉬 값을 생성하는 지극히 상식적인 방법이다.

그리고 이와 유사한 방법으로 '비트 추출 방법'이라는 것이 있다.

이는 탐색 키의 비트 열에서 일부를 추출 및 조합하는 방법이다.

이어서 소개할 방법의 이름은 '자릿수 폴딩'이다.

폴딩은 '접는다'는 뜻이 있다.

그럼 다음 그림에서 보이듯이 숫자를 종이에 쓴 다음에 이를 삼등분 하여 접어보자.

그러면 27과 34, 34와 19가 겹치게 된다.

이렇게 겹친 두 자릿수 숫자를 모두 더하면 그 결과는 80이 되는데, 이를 해쉬 값이라 하면 이는 여섯 자리의 숫자를 모두 반영하여 얻은 결과라 할 수 있다.

이렇듯 폴딩은 종이를 접듯이 숫자를 겹치게 하여 더한 결과를 해쉬 값으로 결정하는 방법이다.

이외에도 키를 제곱하여 그 중 일부를 추출하는 방법, 폴딩의 과정에서 덧셈 대신 XOR 연산을 하는 방법, 그리고 둘 이상의 방법을 조합하는 방법 등 통계적으로 넓은 분포를 보이는 다양한 방법들이 소개되고 있는데, 해쉬 함수를 디자인할 때에는 이러한 방법들보다 키의 특성과 저장공간의 크기를 고려하는 것이 우선이다.

---

2. 충돌(Collision) 문제의 해결책

테이블의 핵심주제라 할 수 있는 충돌 문제를 고민할 차례가 왔다.

그런데 이 충돌의 해결책이란 것이 우리가 생각하는 수준을 크게 벗어나지 않는다.

예를 들어서 충돌이 발생하면, 충돌이 발생한 그 자리를 대신해서 빈 자리를 찾아야 한다.

다반 빈 자리를 찾는 방법에 따라서 해결책이 구분될 뿐이다.

---

충돌이 발생했을 때 그 옆자리가 비었는지 살펴보고, 비었을 경우 그 자리에 대신 저장하는 것이 바로 '선형 조사법'이다.

예를 들어서 다음과 같이 정의된 해쉬 함수 $f(x)$가 있고 테이블의 내부 저장소가 배열이라고 가정해보자.

해쉬 함수: key % 7

그러면 키가 9인 데이터는 해쉬 값이 2이므로 다음과 같이 인덱스가 2인 위치에 저장이 된다.

이어서 키가 2인 데이터가 등장했다고 가정해보자.

이 경우 해쉬 값이 2이기 때문에 앞서 저장한 키가 9인 데이터와 충돌이 발생한다.

이렇듯 충돌이 발생했을 때 인덱스 값이 3인 바로 옆자리를 살피는 것이 선형 조사법이다.

따라서 키가 2인 데이터의 저장결과는 다음과 같다.

물론 옆자리가 비어있지 않을 경우, 한 칸 더 이동을 해서 자리를 살피게 된다.

정리하면, $k$의 키에서 충돌 발생시 선형 조사법의 조사 순서는(빈자리를 찾는 순서는) 다음과 같이 전개가 된다.

그런데 이러한 선형 조사법은 충돌의 횟수가 증가함에 따라서 '클러스터(cluster) 현상', 쉬운 표현으로 '특정 영역에 데이터가 집중적으로 몰리는 현상'이 발생한다는 단점이 있다.

그리고 이러한 클러스터 현상은 충돌의 확률을 높이는 직접적인 원인이 된다.

그렇다면 이러한 선형 조사법의 단점은 어떻게 극복하면 되겠는가?

"좀 멀리서 빈 공간을 찾으면 되지 않을까요?"

좋은 생각이다!

그리고 이러한 생각을 근거로 탄생한 것이 '이차 조사법'이다.

충돌 발생시 이차 조사법의 조사 순서는 다음과 같이 전개가 된다.

이를 선형 조사법의 조사 순서와 비교하면 그 차이를 쉽게 알 수 있다.

선형 조사법은 충돌 발생시 $n$칸 옆의 슬롯을 검사한다면, 이차 조사법은 $n^2$칸 옆의 슬롯을 검사한다.

이렇듯 좀 멀리서 빈 공간을 찾으려는 노력이 이차 조사법에는 담겨 있다.

물론 이차 조사법에도 나름의 문제가 있는데, 이는 잠시 후 '이중 해쉬'를 소개하면서 언급하기로 하겠다.

---

이번에는 슬롯의 상태 정보를 별도로 관리해야 하는 이유에 대해서 언급하겠다.

이를 위해 앞서 보인 그림을 보자.

이 그림에서는 선형 조사법이 사용되었고, 키가 2인 상황에서의 충돌 해결 결과를 보이고 있다.

바로 이 상황에서 키가 9인 데이터를 삭제해보자.

그러면 다음의 상황에 놓이게 된다.

위의 그림에 표시된 슬롯의 상태 EMPTY, DELETED, INUSE가 의미하는 바는 다음과 같다.

- EMPTY: 이 슬롯에는 데이터가 저장된 바 없다.

- DELETED: 이 슬롯에는 데이터가 저장된 바 있으나 현재는 비워진 상태다.

- INUSE: 이 슬롯에는 현재 유효한 데이터가 저장되어 있다.

위의 그림에서 주목할 것은 데이터가 삭제된 슬롯의 상태 정보를 DELETED로 두고, EMPTY와 구분하였다는 것이다.

이렇듯 EMPTY가 아닌 DELETED로 두어야 하는 이유는 키가 2인 데이터의 탐색과정을 살펴보면 알 수 있다.

키가 2인 데이터의 탐색을 진행하기 위해서는 %7의 해쉬 함수를 거친다.

그리고 그 결과로 얻은 2를 인덱스 값으로 하여 탐색을 진행하게 된다.

만약에 그 위치의 슬롯 상태가 EMPTY라면, 데이터가 존재하지 않는다고 판단하여 탐색을 종료하게 된다.

그 옆자리는 확인도 하지 않은 채 말이다.

반면 DELETED 상태임을 확인한다면 충돌이 발생했음을 의심하여 선형 조사법에 근거한 탐색의 과정을 진행해야 한다.

따라서 우리는 다음 두 가지 사실을 추가로 정리해야 한다.

"선형, 이차 조사법과 같은 충돌의 해결책을 적용하기 위해서는 슬롯의 상태에 DELETED를 포함시켜야 한다."

"선형, 이차 조사법을 적용하였다면, 탐색의 과정에서도 이를 근거로 충돌을 의심하는 탐색의 과정을 포함시켜야 한다."

이렇듯 슬롯의 DELETED 상태는 충돌의 해결책과 관련이 있다.

그래서 앞서 보인 예제에서, 당시에는 불필요했던 슬롯의 상태 중 하나인 DELETED를 포함시켰던 것이다.

---

비록 충돌의 해결 방식을 소스코드상에서 확인하지는 않았지만, '이렇게 구현하면 되겠구나'라는 정도의 느낌은 받았을 것이다.

일단은 그 정도로 만족하고 이야기를 이어나가자.

앞서 소개한 이차 조사법은 선형 조사법의 문제를 어느 정도 해결하였지만, 그래도 문제가 전혀 없는 것은 아니다.

이차 조사법의 문제점으로 지적되는 사항은 다음과 같다.

"해쉬 값이 같으면, 충돌 발생시 빈 슬롯을 찾기 위해서 접근하는 위치가 늘 동일하다."

예를 들어서 해쉬 값 $f(k)$가 같다면, $k$가 다르더라도 빈 슬롯을 찾아서 접근하는 위치가 동일하기 때문에, 선형 조사법보다는 낫지만, 접근이 진행되는 슬롯을 중심으로 클러스터 현상이 발생할 확률은 여전히 높을 수밖에 없다.

그렇다면 이러한 단점은 어떻게 극복해야 하겠는가?

"이중 조사법은 좀 멀리서 빈 공간을 찾긴 하지만,

그 빈 공간을 선택하는 방식이 한 칸, 네 칸, 아홉 칸.. 이런식으로 규칙적이잖아요.

이걸 좀 불규칙하게 구성하면 될 것 같은데요?"

이러한 생각을 반영한 것이 '이중 해쉬' 방법이다.

이는 두 개의 해쉬 함수를 사용하기 때문에 붙여진 이름이다.

이중 해쉬 방법에서는 두 개의 해쉬 함수를 마련한다.

하나는 앞서 보인 것과 마찬가지로 키를 근거로 저장위치를 결정하기 위한 것이다.

반면 다른 하나는 충돌이 발생했을 때, 몇 칸 뒤에 위치한 슬롯을 살펴볼지 그 거리를 결정하기 위한 것이다.

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

먼저 배열을 저장소로 하는 테이블이 존재한다고 가정하자.

그리고 이 테이블의 해쉬 함수는 다음과 같이 정의되어 있다고 본다면, 이는 이중 해쉬의 관점에서 1차 해쉬 함수가 된다.

• 1차 해쉬 함수

$h1\left(k\right)=k\%15$

• 2차 해쉬 함수

$h2\left(k\right)=1+\left(k\%c\right)$

위의 식은 처음 보면 당황스럽다.

하지만 설명을 통해서 쉽게 이해할 수 있다.

그리고 위의 2차 해쉬 함수식이 절대적인 것은 아니지만 일반적인 형태라고는 할 수 있다.

1차 해쉬 함수를 %15로 결정한 것으로 보아, 배열의 길이가 15라고 예상해 볼 수 있다.

이런 경우 c는 15보다 작은, 그러면서도 소수(prime number) 중 하나로 결정하게 된다.

따라서 다음과 같이 1차 해쉬 함수와 2차 해쉬 함수를 결정할 수 있다.

여기서는 c를 7로 결정하였는데, 이와 다른 값으로 결정해도 무리가 없다.

그럼 2차 해쉬 함수를 결정하는 일반적인 형태가 위와 같은 이유에 대해서 생각해보자.

먼저 1을 더하는 이유는 2차 해쉬 값이 0이 되는 것을 막기 위해서이다.

충돌 발생 이후에 다른 자리를 살피는 상황에서 2차 해쉬 값이 0이 되면 안되지 않겠는가?

그럼 1차 해쉬 함수인 %15를 근거로, 15보다 작은 소수로 c를 결정하는 이유는 무엇일까?

15보다 작은 값으로 결정하는 이유는, 가급적 2차 해쉬 값이 1차 해쉬 값을 넘어서지 않게 하기 위함이다.

예를 들어서 1차 해쉬의 최대 값이 14인데 2차 해쉬의 최대 값이 32라면 빈 자리를 찾아서 몇 바퀴를 돌아야 할지 모르는 일 아니겠는가?

그렇다면 소수로 결정하는 이유는 무엇일까?

이는 소수로 선택했을 때 클러스터 현상의 발생 확률을 현저히 낮춘다는 통계를 근거로 한 것이다.

그럼 마지막으로 2차 해쉬 함수의 활용에 대한 예를 하나 들겠다.

앞서 정의한 1차 해쉬 함수에 세 개의 키 3, 18, 33을 적용하여 해쉬 값을 구하면 다음과 같다.

때문에 키가 3, 18, 33인 데이터를 순서대로 저장하면, 키가 18과 33인 데이터를 저장할 때 충돌이 발생한다.

따라서 이 두 개의 키를 대상으로 2차 해쉬 값을 계산해보겠다.

위에서 보이듯이 1차 해쉬 값이 같아도 2차 해쉬 값은 다르다.

그리고 이 2차 해쉬 값을 근거로 빈 슬롯을 찾는 과정은 각각 다음과 같이 전개가 된다.

이렇듯 2차 해쉬 값의 크기만큼 건너 뛰면서 빈 슬롯을 찾게 되므로, 키가 다르면 건너 뛰는 길이도 달라진다.

따라서 클러스터(cluster) 현상의 발생 확률을 현저히 낮출 수 있다.

참고로 실제로도 이중 해쉬는 이상적인 충돌 해결책으로 알려져 있다.

---

이번에 소개할 충돌 해결책은 앞서 소개한 방법들과 해결방식이 근본적으로 다르다.

앞서 소개한 유형의 방법들을 가리켜 '열린 어드레싱 방법(open addressing method)'이라 하는데, 이는 충돌이 발생하면 다른 자리에 대신 저장한다는 의미가 담겨 있다.

반면 이번에 소개하는 유형의 방법을 가리켜 '닫힌 어드레싱 방법(closed addressing method)'이라 한다.

그리고 여기에는 무슨 일이 있어도 자신의 자리에 저장을 한다는 의미가 담겨 있다.

"무슨 일이 있어도 자신의 자리에 저장을 한다는 것은 충돌이 발생해도 자신의 자리에 들어가겠다는 의미인가요?"

그렇다! 그런 의미이다.

그런데 그것이 어떻게 가능할 수 있을까?

자리를 여러 개 마련하는 수밖에 별다른 방법이 없지 않겠는가?

여러 개의 자리를 마련하는 방법으로는 배열을 이용하는 방법과 연결 리스트를 이용하는 방법이 있는데, 다음 그림은 배열을 이용하는 방법을 보여준다.

위 그림에서 보이듯이 2차원 배열을 구성해서, 해쉬 값 별로 다수의 슬롯을 마련할 수 있다.

하지만 이는 닫힌 어드레싱 방법 중에서 흔히 거론되는 방법이 아니다.

충돌이 발생하지 않을 경우 메모리 낭비가 심하고, 또 충돌의 최대 횟수를 결정해야 하는 부담도 있기 때문이다.

따라서 '체이닝'이라는, 다음 그림에서 보이듯이 연결 리스트를 이용해서 슬롯을 연결하는 방법이 닫힌 어드레싱 방법을 대표한다.

위 그림에서 보이듯이, 슬롯을 생성하여 연결 리스트의 모델로 연결해나가는 방식으로 충돌 문제를 해결하는 것이 '체이닝' 방법이다.

위의 그림을 보면서 짐작할 수 있겠지만, 체이닝 방법을 적용하면 하나의 해쉬 값에 다수의 슬롯을 둘 수 있다.

따라서 탐색을 위해서는 동일한 해쉬 값으로 묶여있는 연결된 슬롯을 모두 조사해야 한다는 불편이 따른다.

하지만 해쉬 함수를 잘 정의한다면, 그래서 충돌의 확률이 높지 않다면 연결된 슬롯의 길이는 부담스러운 정도가 아닐 것이다.