[자료구조, C] 해시 테이블(Hash Table)

<해시 테이블(Hash Table)>

[테이블(Table)의 이해]

이전에 공부했던 이진 탐색 트리와 AVL 트리는 탐색과 관련해서 굉장히 좋은 성능을 보였다.
이 둘은 탐색 키와의 비교 과정을 거치면서 찾는 대상에 가까워지는 방식이다.
그런데 원하는 데이터를 ‘단번에’ 찾아내는 방식이라고는 볼 수 없다.
상황에 따라서는 위의 두 자료구조의 성능은 적합하지 않을 수도 있다.
이런 상황에서 사용할 수 있는 자료구조가 테이블(Table)이다.
이진 탐색 트리와 AVL 트리는 탐색 연산이 $O(log_2n)$만큼의 시간 복잡도를 가진다.
그런데 테이블 자료구조에서 탐색 연산은 $O(1)$의 시간 복잡도를 보인다.
왜 그런지는 테이블의 탐색 원리를 알면 바로 이해가 된다.

테이블 자료구조의 예

 

위와 같은 ‘표’는 ‘테이블’ 자료구조라고 볼 수 있다.

물론, 모든 표가 테이블 자료구조라고 할 수 있는 것은 아니다.

자료구조적 관점에서 테이블은 저장된 데이터의 형태가 다음과 같을 때 테이블이라고 한다.

 

"저장되는 데이터는 키(Key)와 값(Value)이 하나의 쌍(Pair)를 이룬다."

 

여기서 키(Key)는 실질적인 데이터들 가운데 고유한 값, 중복되지 않는 값이다.

그리고 값(Value)는 실질적인 데이터 내용(정보들)을 가지고 있다.

테이블에 저장되는 모든 데이터는 ‘키’를 갖고 있어야 하고, 키는 데이터를 구분 짓는 기준이 된다.

그래서 키는 절대로 중복을 허용하지 않는다.

이 내용은 데이터베이스를 공부하면서 Primary Key와 관련되는 내용이다.

정리해서 말하면 다음과 같다.

 

" '키(Key)'가 존재하지 않는 '값'은 저장할 수 없다. 그리고 모든 키는 절대 중복되지 않는다."

 

이처럼 테이블에서의 핵심은 ‘키와 값이 쌍을 이루어 저장되는 데이터’라는 점이다.

그리고 위의 표말고도 테이블의 예로 들 수 있는 것은 '사전(dictionary)'이다.

사전은 표와 같은 구성으로 되어있지는 않다.

그렇지만 사전은 단어가 ‘키’가 되고 단어에 대한 설명이 ‘값’이라고 볼 수 있는 테이블 자료구조다.

그래서 테이블은 '사전구조' 또는 ‘맵(map)’이라고 불리우기도 한다.

 

[배열 기반의 테이블 구현]

[UnderstandTable.c]

/*
* 자료구조 - 해시 테이블 (테이블 + 해시)
* 파일명: UnderstandTable.c
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-29
* 이전 버전 작성 일자:
* 버전 내용: 테이블 자료구조에 대한 이해를 위한 코드
* 이전 버전 내용:
*/

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>

typedef struct _empInfo
{
	int empNum; // 사원 번호
	int age; // 나이
} EmpInfo;

int main()
{
	EmpInfo empInfoArr[100];
	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;
}

 

EmpInfo는 직원의 고유번호를 Key로 하였고, 직원의 나이를 Value로 하나의 쌍으로 묶기 위해 정의한 구조체다.
하지만 이것만 가지고는 테이블이라고 하기에는 부족하다.
따라서 추가적인 조건을 만족시킬 필요가 있다.

이 조건을 만족하면 단순한 배열이라 하더라도 테이블, 또는 테이블의 일부라 할 수 있다.

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

 

다시 말해서 테이블에서 의미하는 '키'는 '데이터를 찾는 도구'가 되어야 한다.

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

그래서 위의 코드에서는 저장과 탐색을 키를 이용하여 단번에 해낼 수 있는 것이다.

현재 구현한 코드를 통해서 알 수 있는 사실은 다음과 같다.

 

"직원의 사원 번호(키)를 인덱스 값으로 하여 그 위치에 데이터를 저장했다."

 

이처럼 [키의 값 = 저장 위치]라는 관계를 형성하여 단번에 데이터를 저장하고 단번에 데이터를 탐색할 수 있는 것이다.

하지만, 직원 번호가 만약 세 자리수가 아닌 여섯자리 수가 된다면?

배열의 공간을 arr[1000000]과 같이 줄 수는 없는 노릇이다.

여기서 구현한 테이블은 '해시'에 대한 개념이 빠졌기 때문에 효율적인 테이블이 아니다.

 

[테이블에 의미를 부여하는 해시 함수와 충돌 문제]

앞서 구현했던 예제를 통해서 직원 번호가 더 길어지는 경우, 엄청나게 큰 배열을 선언해야 한다는 문제가 있다.

그 문제를 분석하면 크게 두 가지로 정리할 수 있다.

 

1) 직원의 사원 번호의 범위가 배열의 인덱스 값으로 쓰기에는 적절하지 않다.

2) 직원의 사원 범위를 수용할 수 있는 굉장히 큰 배열이 필요하다.

 

이 두 가지의 문제를 해결할 수 있는 방법이 바로 '해시 함수(Hash Function)'다.

우선 해시 함수를 적용하기에 앞서 사번에 다음과 같은 가정을 추가한다.

"직원의 사원번호(key)는 입사년도 네 자리와 입사순서 네 자리로 구성된다"

그리고 아래의 코드에서는 배열 길이를 최소화하여 이전 예제의 문제를 해결한다.

 

[TableHashFunction.c]

/*
* 자료구조 - 해시 테이블 (테이블 + 해시)
* 파일명: TableHashFunction.c
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-29
* 이전 버전 작성 일자:
* 버전 내용: 해시 함수에 대한 이해를 위한 코드
* 이전 버전 내용:
*/

#include <stdio.h>

typedef struct _empinfo
{
	int empNum; // 직원의 고유 번호(Key)
	int age; // 직원의 나이(Value)
} EmpInfo;

// Hash 함수
int GetHashValue(int empNum)
{
	return empNum % 100;
}

int main()
{
	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명을 넘지 않을 것을 고려한 것이며, 데이터의 저장위치를 결정하는데 사원번호를 활용한다.

그리고 그 사원번호를 그대로 인덱스로 적용하는 것이 아니라 함수를 이용하여 가공을 한다.

위의 함수는 100의 나머지 연산(%)을 수행하여 8자리의 수로 이뤄진 직원의 사원번호를 두 자리수로 변경하게 된다.

이 함수를 $f(x)$라고 했을때, 이 함수의 기능을 다음과 같이 표현할 수 있다.

 

해시 함수와 해시 값

 

이와 같은 기능을 하는 함수 $f(x)$를 '해시 함수(Hash Function)'이라고 한다.

해시함수는 넓은 범위의 키를 좁은 범위의 키로 변경하는 역할을 수행한다.

실제로 많은 해시 함수에서 나머지 연산자(%)를 사용한다.

그리고 이 해시 함수에 의해 만들어진 해시 값을 인덱스로 사용하게 된다.

이처럼 해시 함수를 사용하게 되면 합리적인 메모리 공간을 할당하는데 도움이 된다.

 

그럼 이 함수로 인해서 문제가 모두 해결되었는가 하면 그것도 아니다.

다음과 같은 문제가 생길 수 있다.

충돌(Collision)의 발생

 

분명히 서로 다른 키임에도 해시 함수를 통과하면 똑같은 해시 값이 나오게 된다.

이와 같은 경우를 '충돌(Collision)'이라고 하는데, 충돌이 발생하면 배열의 길이를 늘리는 등의 방법으로 해결하면 안된다.

배열의 길이를 늘린다 해서 충돌을 완전히 피할 수 있는 것도 아니다.

완전히 피할 수 있다 해도 합리적인 결정도 아니다.

그래서 충돌은 피해야 할 상황이 아니라 발생할 경우 '해결해야 하는 상황'으로 인식해야 한다.

충돌의 해결 방법에 따라서 테이블의 구조가 달라지는 경우도 있을 만큼 해결 방법은 테이블에 있어 큰 의미가 있다.

 

[조금 구색을 갖춘 테이블과 해시의 구현 예시]

[Person.h]

/*
* 자료구조 - 해시 테이블 (테이블 + 해시)
* 파일명: Person.h
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-29
* 이전 버전 작성 일자:
* 버전 내용: 간단한 해시 테이블 구현
* 이전 버전 내용:
*/

#ifndef __PERSON_H__
#define __PERSON_H__

#define STR_LEN 50

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

int GetSSN(Person* p); // 객체 지향 관점 -> 엑세스 함수 (Getter)
void ShowPersonInfo(Person* p); // 객체 지향 관점 -> const 함수
Person* MakePersonData(int ssn, char* name, char* addr); // 객체 지향 관점 -> 생성자

#endif

[Person.c]

/*
* 자료구조 - 해시 테이블 (테이블 + 해시)
* 파일명: Person.c
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-29
* 이전 버전 작성 일자:
* 버전 내용: 간단한 해시 테이블 구현
* 이전 버전 내용:
*/
#define _CRT_SECURE_NO_WARNINGS

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

int GetSSN(Person* p) // 객체 지향 관점 -> 엑세스 함수 (Getter)
{
	return p->ssn;
}
void ShowPersonInfo(Person* p) // 객체 지향 관점 -> const 함수
{
	printf("주민등록번호: %d\n", p->ssn);
	printf("이름: %s\n", p->name);
	printf("주소: %s\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;
}

 

헤더 파일에서 정의한 구조체 변수의 주소값이 테이블에 저장될 '값'이다.

그리고 구조체의 멤버인 ssn, 주민등록번호가 '키'가 된다.

그래서 키를 별도로 추출하기 위한 GetSSN 함수가 정의되었다.

주석에도 달아두었지만, 객체 지향 프로그래밍을 하면 이는 엑세스 함수로 Getter가 된다.

그리고 구조체 변수의 생성과 초기화를 위해 MakePersonData라는 함수도 정의를 하였다.

이 역시 객체 지향 프로그래밍에서의 관점에서는 생성자가 된다.

 

[Slot.h]

/*
* 자료구조 - 해시 테이블 (테이블 + 해시)
* 파일명: Slot.h
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-29
* 이전 버전 작성 일자:
* 버전 내용: 간단한 해시 테이블 구현
* 이전 버전 내용:
*/

#ifndef __SLOT_H__
#define __SLOT_H__

#include "Person.h"

typedef int Key; // 주민등록번호의 데이터형이 int, 그리고 int형을 Key로
typedef Person* Value; // Person형 구조체 포인터 변수를 Value로

enum SlotStatus {EMPTY, DELETED, INUSE};

// 테이블 각각의 공간(Slot)
typedef struct _slot
{
	Key key; // Key
	Value val; // Value
	enum Slotstatus status;
} Slot;
#endif

 

Slot 같은 경우에는 테이블을 구성하는, 데이터를 저장할 수 있는 각각의 공간이다.

그리고 typedef 선언을 통해서 int를 Key로, Person*을 Value로 별칭을 붙여서 키와 값을 결정했다.

enum 열거형 타입을 선언해서 슬롯의 상태를 나타내는 EMPTY, DELETED, INUSE의 세 가지 상태를 정의했다.

EMPTY는 말 그대로 슬롯이 비었다는 뜻이다. 

DELETED는 이 슬롯에는 데이터가 저장되었으나 현재는 빈 상태라는 뜻이다.

마지막으로 INUSE는 현재 슬롯에 데이터가 저장되어 있다는 뜻이다.

현 시점에서 DELETED는 어디에 쓰는지 판단하기가 어렵다.

우선은 일반적으로 상태를 표현할 때에는 다음의 세 가지 상태로 구분한다는 사실을 알아야 한다.

그리고 DELETED는 충돌이 발생했을 때 유용하게 사용될 수 있다.

 

[Table.h]

/*
* 자료구조 - 해시 테이블 (테이블 + 해시)
* 파일명: Table.h
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-29
* 이전 버전 작성 일자:
* 버전 내용: 간단한 해시 테이블 구현
* 이전 버전 내용:
*/

#ifndef __TABLE_H__
#define __TABLE_H__

#include "Slot.h"

#define MAX_TBL 100

typedef int HashFunc(Key k); // 함수 포인터로 쓰기 위해(HashFunc) typedef 선언

// 테이블 구조체
typedef struct _table
{
	Slot tbl[MAX_TBL];
	HashFunc* hf;
} Table;

// 초기화
void TableInit(Table* pt, HashFunc* pf);

// 키와 값을 저장
void TBLInsert(Table* pt, Key k, Value v);

// 키를 근거로 테이블에서 데이터 삭제
Value TBLDelete(Table* pt, Key k);
// 키를 근거로 테이블에서 데이터 조회
Value TBLSearch(Table* pt, Key k);

#endif

 

[Table.c]

/*
* 자료구조 - 해시 테이블 (테이블 + 해시)
* 파일명: Table.c
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-29
* 이전 버전 작성 일자:
* 버전 내용: 간단한 해시 테이블 구현
* 이전 버전 내용:
*/

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

// 초기화
void TBLInit(Table* pt, HashFunc* pf)
{
	int i;

	// 모든 슬롯 초기화
	for (i = 0; i < MAX_TBL; i++)
		(pt->tbl[i]).status = EMPTY;

	// 해시 함수 등록
	pt->hf = pf;
}

// 키와 값을 저장
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) // 슬롯이 INUSE가 아니라면
		return NULL; // 찾지 못함
	else
	{
		(pt->tbl[hv]).status = DELETED; // DELETED로 변경
		return (pt->tbl[hv]).val; // 삭제 대상 값 반환
	}
}
// 키를 근거로 테이블에서 데이터 조회
Value TBLSearch(Table* pt, Key k)
{
	int hv = pt->hf(k); // 해시 함수를 통해 생성된 해시 값

	if ((pt->tbl[hv]).status != INUSE) // 슬롯이 INUSE가 아니라면
		return NULL; // 찾지 못함
	else
		return (pt->tbl[hv]).val; // 조회 대상 값 반환
}

 

해시 함수는 등록이나 변경이 가능하도록 정의할 수 있게 하였다.

그래서 typedef 선언을 통해 int HashFunc(Key k)로 함수포인터 변수로 사용할 수 있도록 데이터형처럼 선언했다.

그리고 해시 함수를 등록하거나 변경이 가능하도록 하는게 좋은데, 그 이유는 다음과 같다.

 

우리가 위와 같이 실제로 테이블을 구현해서 쓸 일은 사실상 많이 없다.

대부분 라이브러리에서 제공하는 테이블 자료구조를 이용하게 될 것이다.

그런데 거기서도 내가 별도로 정의한 해시 함수를 등록할 수도 있거나 없을 수도 있다.

이때 내가 별도로 정의한 해시 함수를 등록하지 않으면 기본적으로 제공하는 라이브러리에서 만든 해시 함수를 사용한다.

만약 별도로 정의한 해시 함수를 등록하고 싶다면, 그 방법을 라이브러리에서는 별도의 함수로 또 제공을 하게 된다.

그런 부분에 있어서 이와 같은 개념을 알아두면 나중에 라이브러리로 자료구조를 이용하는 데에 큰 도움이 될 수 있다.

 

마지막으로는 Slot의 배열로 테이블을 구성한 부분 정도가 눈여겨 봐 둘 부분이다.

 

[SimpleHashMain.c]

/*
* 자료구조 - 해시 테이블 (테이블 + 해시)
* 파일명: SimpleHashMain.c
* 파일 버전: 0.1
* 작성자: Sevenshards
* 작성 일자: 2023-11-29
* 이전 버전 작성 일자:
* 버전 내용: 간단한 해시 테이블 구현
* 이전 버전 내용:
*/

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

// 사용자 정의 해시 함수
int MyHashFunc(int k)
{
	return k % 100;
}

int main()
{
	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) // NULL이 아니라면 -> 제대로 조회가 되었다면
		ShowPersonInfo(sp); // 정보 출력
	sp = TBLSearch(&myTbl, 20130012);
	if (sp != NULL) // NULL이 아니라면 -> 제대로 조회가 되었다면
		ShowPersonInfo(sp); // 정보 출력
	sp = TBLSearch(&myTbl, 20170049);
	if (sp != NULL) // NULL이 아니라면 -> 제대로 조회가 되었다면
		ShowPersonInfo(sp); // 정보 출력

	// 데이터 삭제
	rp = TBLDelete(&myTbl, 20120003);
	if (rp != NULL) // NULL이 아니라면 -> 반환이 되었다면
		free(rp); // 메모리 할당 해제
	rp = TBLDelete(&myTbl, 20130012);
	if (rp != NULL) // NULL이 아니라면 -> 반환이 되었다면
		free(rp); // 메모리 할당 해제
	rp = TBLDelete(&myTbl, 20170049);
	if (rp != NULL) // NULL이 아니라면 -> 반환이 되었다면
		free(rp); // 메모리 할당 해제
	return 0;
}

 

해시 함수는 되게 단순하게 100으로 나눈 나머지 값을 받는 것으로 하였다.

실제로 해시 함수에 사용되는 알고리즘은 이보다 더 복잡한 것들이 많다.

그리고 이미 잘 만들어진 알고리즘들이 많기 때문에 여기서는 맛만 보라는 느낌으로 만든 것.

위의 메인 함수 부분 코드에서 테이블을 초기화하면서 해시 함수도 같이 인자로 전달하는 것을 볼 수 있다.

그리고 테이블에서 데이터를 입력, 조회, 삭제를 하는데 모두 키 값을 이용하여 진행하는 것도 확인이 가능하다.

아직 위 예제에서는 해시 함수의 충돌에 대한 처리는 일절 하지 않았다.

 

[좋은 해시 함수의 조건]

 

위의 그림처럼 좋은 해시 함수를 사용하게 되면 테이블의 전체 슬롯에 고루 분포가 되어있는 것을 볼 수 있다.

슬롯이 고르게 분포가 된다는 것은 충돌이 발생할 확률이 낮다는 것이다.

충돌이 덜 발생해야 데이터를 저장, 삭제하고 조회하는 데 효율을 늘릴 수 있다.

그래서 [좋은 해시 함수 == 충돌을 덜 일으키는 해시 함수] 라고 볼 수 있다.

 

반대로 좋지 못한 해시 함수는 그림과 같이 테이블의 특정 영역에 데이터가 몰려있는 상황이다.

이는 해쉬 함수가 특정 영역에 데이터가 몰리도록 해시 값을 생성한 결과이다.

그래서 충돌이 빈번하게 발생할 확률이 높다.

 

그럼 좋은 해시 함수를 디자인 하는 방법은 뭘까?

사실 거기에 대한 정해진 답은 없다.

이는 키의 특성에 따라서 달라질 수 있기 때문이다.

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

 

"좋은 해시 함수는 키의 일부분만 참조하여 만드는 것이 아니라 키 전체를 참조하여 해시 값을 만든다"

 

많은 수의 데이터를 조합(키 전체를 조합)해 해시 값을 만들면 다양한 값을 만들 수 있을 것이라는 기대를 근거로 한다.

 

[좋은 해시 함수를 디자인하는 방법은?]

좋은 해시 함수를 디자인하는 방법은 키의 특성에 따라 달라지게 된다.

그래서 절대적인 방법은 없지만, 키 전체를 참조하는 방법과 관련하여 다양한 방법들이 있다.

열혈 자료구조에서는 자릿수 선택(Digit Selection)과 자릿수 폴딩(Digit Folding)에 대한 이야기가 수록되어 있다.

 

1) 자릿수 선택(Digit Selection)

예) 8자리의 수로 이뤄진 키에서 다양한 해시 값 생성에 도움을 주는 4자리 수를 뽑아서 해시 값을 생성한다.

키의 특정 위치에서 중복의 비율이 높거나, 공통으로 들어가는 값을 제외한 나머지로 해쉬 값을 생성하는 방식

 

2) 자릿수 폴딩(Digit Folding)

 

폴딩(Folding)은 말 그대로 접는다는 뜻이다.

접어서 겹치는 숫자들을 합하거나 XOR 연산을 통해 해시값을 만들어 내는 방식이다.

예로 273419라는 키가 있다고 치면 이를 두 자릿수씩 끊고, 이를 모두 합치면 80이라는 수가 나온다.

이를 해시 값으로 이용하는 방식이다.

 

열혈 자료구조에서는 위의 두 가지 외에도 다른 방식도 있다는 것에 대해 가볍게 이야기하고 끝을 냈다.

사실 해시라는 개념은 자료구조 이외에도 암호화 쪽에서도 다양하게 쓰이고 있다.

요즘 프로그래밍 언어에서 만들어져 있는 라이브러리에는 기본적으로 암호학적 해시함수가 구현되어 있다.

그래서 해시 함수는 잘 만들어진, 지금까지 검증된 방법들을 사용하는 것도 좋다.

그렇다고 무조건적으로 수용하라는 것은 아니다.

어떤 데이터든 일반적으로 처리할 수 있도록 일반화가 된 해시 함수를 사용하기 때문이다.

그래서 저장하는 데이터의 특성에 따라서 해시함수를 따로 정의하고 성능을 향상시킬 수 있다면 따로 정의하는 것도 좋다.

 

+ 해시함수를 만드는 방법에 이것만 적기에는 정보가 부족한듯 하여 참고할만한 링크를 하나 가져왔다.

이처럼 다양한 방법을 이용해서 해시 함수를 만들어낸다는 것을 알아두면 된다.

 

http://wiki.hash.kr/index.php/%ED%95%B4%EC%8B%9C#.ED.95.B4.EC.8B.9C_.EB.B0.A9.EB.B2.95

해시 - 해시넷

 

[충돌(Collision)의 해결 방법]

충돌 문제는 테이블에서 핵심적인 문제다.

그런데 충돌이 발생하면 이걸 어떻게 해결해야 할까?

생각보다 많이 복잡하게 생각할 필요는 없었다.

예를 들면, 충돌이 발생한 경우에는 충돌이 발생한 그 자리를 대신해서 빈 자리를 찾는 방식을 생각해볼 수 있다.

실제로 빈 자리를 찾는 방법을 사용한다.

그리고 이 빈 자리를 찾는 방법에 따라서 해결책이 구분될 수 있다.

 

1) 선형 조사법(Linear Probing)

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

예) 해시 함수 $f(x)$ = key % 7

key가 9인 데이터를 저장하면 다음과 같이 저장된다.

키가 9인 데이터가 저장된 상황

 

그리고 key가 2인 데이터를 저장하면 충돌이 발생한다.

여기서 선형 조사법을 적용하여 충돌을 해결하면 다음과 같이 저장된다.

키가 2인 데이터가 저장된 상황 (충돌 발생 & 충돌 해결)

 

만약 옆자리가 비어있지 않을 경우에는 한 칸을 더 이동해서 자리를 확인하게 된다.

정리하자면, key가 k라고 했을 때 선형 조사법에서 빈 자리를 찾는 과정은 다음과 같다.

선형 조사법에서의 빈자리를 찾는 과정

 

선형 조사법의 문제는 충돌이 증가하면 증가할수록 클러스터(cluster, 군집화) 현상이 발생하게 된다.

다시 말해서 특정 영역에 데이터가 집중적으로 몰리는 현상이 일어난다.

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

 

2) 이차 조사법(Quadratic Probing)

이차 조사법에서의 빈자리를 찾는 과정

 

그래서 선형 조사법을 개선하고자 나온 것이 이차 조사법이다.

빈 자리를 찾는 과정을 바로 옆이 아니라 선형 조사법보다 멀리서 빈 자리를 찾는 방법이다.

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

물론 선형 조사법에 비해서는 개선된 형태인 것은 맞지만, 결국 클러스터 현상이 발생하는 문제가 생기게 된다.

 

[슬롯의 DELETED 상태가 쓰이는 이유]

앞에서 DELETED 상태는 충돌이 발생했을 때 유용하게 쓰일 수 있다고 했다.

앞선 과정에서 테이블에 저장했던 9가 지워진 상황을 생각해보자.

9가 지워진 상황, 2번 슬롯은 DELETED 상태

 

여기서 9가 저장되었던 슬롯은 DELETED로 바뀌게 된다.

그리고 키가 2인 데이터를 찾으려고 했을 때, 해시 함수에 의해서 테이블의 인덱스 2부터 확인을 하게 된다.

여기서 DELETED가 아닌 EMPTY로 놓게 되면 바로 옆에 있는 2를 찾지 못하게 되고, 결국 잘못된 결과를 불러올 수 있다.

하지만 DELETED 상태라는 것을 확인하면 충돌이 일어났었다는 사실을 확인할 수 있다.

그리고 충돌이 발생한 것을 의심하여 선형 조사법이나 이차 조사법의 방식으로 탐색을 진행하여 2를 찾을 수 있다.

따라서 DELETED 상태를 사용하는 이유에 대해 정리하면 다음과 같다.

 

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

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

 

추가적으로 테이블을 사용하면서 데이터가 계속 저장과 삭제를 반복하다보면 언젠가는 모든 슬롯이 DELETED가 된다.

이때는 탐색의 성능이 저하가 될 수 있으며, 이 부분에 대한 해결책도 고민해볼 필요가 있다.

 

[이중 해시 (Double Hash)]

앞에서 이야기했던 선형 조사법과 이차 조사법은 클러스터 현상을 유발한다고 했다.

선형 조사법은 그렇다 치더라도, 이차 조사법은 왜 클러스터 현상을 유발하는가?

선형 조사법과 마찬가지로 이차 조사법도 결국 아래와 같은 문제를 가지고 있기 때문이다.

"해시 값이 동일하면, 충돌 발생 시에 빈 슬롯을 찾기 위해 접근하는 위치가 동일하다"

이차 조사법에서의 빈 자리를 찾는 과정

 

쉽게 말해서 해시된 값 $f(k)$ 기준으로 충돌이 발생했다고 하면 다음과 같다.

 

첫 번째 조사: $1^2$칸 옆의 슬롯

두 번째 조사: $2^2$칸 옆의 슬롯

세 번째 조사: $3^2$칸 옆의 슬롯

 

선형 조사법에 비해서는 먼 곳을 조사하지만, 결국 길게 놓고 보면 빈 슬롯을 찾아서 접근하는 위치가 동일하다.

접근이 진행되는 슬롯을 중심으로 클러스터 현상이 발생할 확률은 여전히 높다.

선형, 이차 조사법은 클러스터 현상이 발생하기 때문에 실제로는 쓰이지 않는 방식이기도 하다.

 

그래서 충돌을 해결하기 위한 방식으로 '이중 해시(Double Hash)' 방법을 사용한다.

말 그대로 해시 함수를 2개를 사용하는 방법이다.

 

1차 해시 함수: 키를 이용하여 저장할 위치를 지정할 때 사용

2차 해시 함수: 충돌이 발생했을 시 몇 칸 뒤를 살필지 결정할 때 사용

 

예를 들어서 배열을 저장공간으로 사용하는 테이블이 있다고 가정을 해보겠다.

그리고 1차 해시 함수를 다음과 같이 정의하였다.

$h1(k) = k % 15$

 

1차 해시 함수를 정의하였다면, 그 다음은 2차 해시 함수를 다음과 같이 정의한다.

$h2(k) = 1 + (k % c)$ (c는 상수, constant)

 

1차 해시 함수: $h1(k) = k % 15$

2차 해시 함수: $h2(k) = 1 + (k % c)$

 

여기서 1차 해시 함수가 15의 나머지(%15)를 구한다는 것은 저장소의 길이가 15라는 것을 짐작할 수 있다.

그리고 이런 경우에 c는 15보다는 작은, 그러면서 소수(prime number) 중의 하나로 결정을 한다.

 

1차 해시 함수: $h1(k) = k % 15$

2차 해시 함수: $h2(k) = 1 + (k % 7)$

 

여기서 2차 해시 함수가 왜 위와 같은 형태로 만들어졌을까?

그 이유에 대해서는 다음과 같다.

 

1) 1을 더하는 이유: 2차 해시 값이 0이 나오는 것을 막기 위해서. 0이 그 자리 그대로이므로 충돌이 발생한다.

2) c를 15보다 작은 값으로 한 이유: 가급적이면 2차 해시 값이 1차 해시 값을 넘어서지 않게 하기 위함

1차 해시 함수의 최대 값은 14인데 2차 해시값이 그 이상이 나오면 빈 자리를 찾기가 힘들어진다.

3) c를 소수로 결정하는 이유: 소수를 선택했을 때 클러스터 현상의 발생 확률을 현저히 낮춘다는 통계를 근거로

 

마지막으로 위에서 예로 든 이중 해시를 활용하여 효과가 있는지 확인을 해보자.

만약 세 개의 키 3, 18, 33을 저장하겠다고 하면 1차 해시 함수에 의해서 다음과 같은 해시값이 나온다.

 

$h1(3) = 3%15 = 3$ / $h1(18) = 18%15 = 3$ /  $h1(33) = 33%15 = 3$

 

순서대로 저장하게 되면 키가 3인 데이터가 저장되고 18, 33인 키의 데이터를 저장할 때 충돌이 일어난다.

충돌이 발생했을 때, 2차 해시를 통해 빈 자리를 찾는 위치가 달라지는 지를 확인한다.

 

$h2(18) = 1 + (18 % 7) = 5$ / $h2(33) = 1 + (33%7) = 6$

 

이처럼 같은 1차 해시 값을 가지게 되어도 2차 해시에서는 다른 값이 나온다.

그래서 이 2차 해시값을 근거로 빈 슬롯을 찾는 과정은 다음과 같다.

 

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

그렇기 때문에 클러스터 현상의 발생 확률을 현저히 낮추는 것이 가능하다.

 

[체이닝(Chaining) 기법]

체이닝(Chaining) 기법도 해시 충돌 처리의 기법 중 하나다.

다만 이전에 소개했던 선형 조사, 이차 조사, 이중 해시와는 결이 다르다.

이전의 방식을 열린 어드레싱 방법 또는 개방 주소법(Open addressing method)라고 한다.

개방 주소법 방식은 충돌이 발생하면 다른 자리에 대신 저장할 수 있는 방법이다.

그에 비해 체이닝 기법은 닫힌 어드레싱 방법 또는 폐쇄 주소법(Closed addressing method)라고 한다.

이 방법은 다른 자리에 대신 저장하지 않고 그 자리에 이어서 저장을 하는 방법이다.

즉, 충돌이 일어나도 해당 인덱스에 저장을 하는 방식이며 이를 위해서는 저장소 공간을 크게 잡아야 한다.

 

2차원 배열을 이용한 체이닝 기반 테이블

 

연결 리스트를 이용한 체이닝 기반 테이블

 

위처럼 2차원 배열을 이용하는 방법과 연결 리스트를 이용하는 방식을 사용할 수 있다.

2차원 배열을 이용하는 경우에는 해시값별로 다수의 슬롯을 마련할 수 있지만 실제로 사용되는 방법은 아니다.

충돌이 발생하지 않는 경우에는 메모리의 낭비가 심하며, 충돌의 최대 횟수를 결정해야 한다는 문제가 있다.

그래서 보편적으로 연결리스트를 이용한 방법이 폐쇄 주소법을 대표하는 방식이라고 볼 수 있다.

그림처럼 슬롯을 생성하고 연결 리스트로 연결해나가며 사슬처럼 엮이는 모습을 볼 수 있다.

이와 같은 방식으로 충돌 문제를 해결하는 것이 '체이닝' 기법이다.

 

체이닝 기법은 하나의 해시값에 다수의 슬롯을 둘 수 있게 된다.

그래서 탐색 시 동일한 해시 값으로 묶여서 연결된 슬롯을 모두 조사해야 하는 불편함이 있다.

하지만 좋은 해시 함수를 정의해서 충돌 확률을 낮춘다면 연결되는 슬롯의 길이는 길지 않을 수도 있다.

 

[체이닝 기법 구현]

앞에서 구현했던 [조금 구색을 갖춘 테이블과 해시]의 코드를 일부 변경하였다.

[Slot.h]

/*
* 자료구조 - 해시 테이블 (테이블 + 해시)
* 파일명: Slot.h
* 파일 버전: 0.2
* 작성자: Sevenshards
* 작성 일자: 2023-11-29
* 이전 버전 작성 일자: 2023-11-29
* 버전 내용: 해시 충돌 문제 해결을 위한 체이닝 기법 구현
* 이전 버전 내용: 간단한 해시 테이블 구현
*/

#ifndef __SLOT_H__
#define __SLOT_H__

#include "Person.h"

typedef int Key; // 주민등록번호의 데이터형이 int, 그리고 int형을 Key로
typedef Person* Value; // Person형 구조체 포인터 변수를 Value로


// 테이블 각각의 공간(Slot)
typedef struct _slot
{
	Key key; // Key
	Value val; // Value
} Slot;
#endif

 

체이닝 기법에서는 충돌 이후 조사를 할 필요가 없으므로 슬롯의 상태 정보를 유지할 필요가 없다.

 

[Table.h]

/*
* 자료구조 - 해시 테이블 (테이블 + 해시)
* 파일명: Table.h
* 파일 버전: 0.2
* 작성자: Sevenshards
* 작성 일자: 2023-11-29
* 이전 버전 작성 일자: 2023-11-29
* 버전 내용: 해시 충돌 문제 해결을 위한 체이닝 기법 구현
* 이전 버전 내용: 간단한 해시 테이블 구현
*/

#ifndef __TABLE_H__
#define __TABLE_H__

#include "Slot.h"
#include "SingleLinkedList.h"

#define MAX_TBL 100

typedef int HashFunc(Key k); // 함수 포인터로 쓰기 위해(HashFunc) typedef 선언

// 테이블 구조체
typedef struct _table
{
	List tbl[MAX_TBL];
	HashFunc* hf;
} Table;

// 초기화
void TableInit(Table* pt, HashFunc* pf);

// 키와 값을 저장
void TBLInsert(Table* pt, Key k, Value v);

// 키를 근거로 테이블에서 데이터 삭제
Value TBLDelete(Table* pt, Key k);
// 키를 근거로 테이블에서 데이터 조회
Value TBLSearch(Table* pt, Key k);

#endif

 

 

테이블의 데이터형을 List로 바꾸었다.

위의 그림처럼 노드의 데이터에 Slot을 저장하는 방식을 취할 것이기 때문이다.

 

[SingleLinkedList.h]

/*
* 선형 자료구조 - 단일 연결 리스트 (더미 노드 기반)
* 파일명: SingleLinkedList.h
* 파일 버전: 0.2
* 작성자: Sevenshards
* 작성 일자: 2023-11-29
* 이전 버전 작성 일자: 2023-11-29
* 버전 내용: 해시 충돌 문제 해결을 위한 체이닝 기법 구현
* 이전 버전 내용: 더미 노드 기반 단일 연결 리스트 구현
*/
#ifndef __SINGLE_LINKED_LIST_H__
#define __SINGLE_LINKED_LIST_H__

#define TRUE 1 // 참일 경우 1
#define FALSE 0 // 거짓일 경우 0

#include "Slot.h"

typedef Slot LData; // 어떤 데이터를 쓸지 모르니 일단은 LData로 매크로 지정, 편의상 int

typedef struct _node
{
	LData data; // 노드에 담길 데이터
	struct _node* next; // 다음 노드를 가리키기 위한 포인터
} Node;

typedef struct _linkedlist
{
	Node* head; // head를 가리키는 포인터
	Node* cur; // 현재 참조하는 위치를 가리키는 포인터
	Node* before; // 현재보다 하나 앞의 위치를 가리키는 포인터
	int numOfData; // 현재 저장된 데이터 수를 확인하기 위해 사용
} LinkedList;

typedef LinkedList List;

void ListInit(List* plist); // 리스트의 초기화에 사용

void LInsert(List* plist, LData data); // 리스트의 노드를 새로 생성할 때 사용

int LFirst(List* plist, LData* pdata); // 리스트의 맨 첫번째 데이터를 참조할 때 사용

int LNext(List* plist, LData* pdata); // LFirst 이후의 데이터를 참조할 때 사용

LData LRemove(List* plist); // LFirst, LNext가 참조한 데이터를 삭제하고 메모리 해제에 사용, 연속 호출 불가

int LCount(List* plist); // 현재 리스트에 저장된 노드 수 확인

#endif

 

그리고 Slot.h 파일을 추가로 include하고 리스트에 담길 데이터의 형태의 typedef 선언을 Slot형으로 바꾼다.

 

[Table.c]

/*
* 자료구조 - 해시 테이블 (테이블 + 해시)
* 파일명: Table.c
* 파일 버전: 0.2
* 작성자: Sevenshards
* 작성 일자: 2023-11-29
* 이전 버전 작성 일자: 2023-11-29
* 버전 내용: 해시 충돌 문제 해결을 위한 체이닝 기법 구현
* 이전 버전 내용: 간단한 해시 테이블 구현
*/

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

// 초기화
void TBLInit(Table* pt, HashFunc* pf)
{
	int i;

	// 모든 슬롯 초기화
	for (i = 0; i < MAX_TBL; i++)
		ListInit(&(pt->tbl[i]));

	// 해시 함수 등록
	pt->hf = pf;
}

// 키와 값을 저장
void TBLInsert(Table* pt, Key k, Value v)
{
	int hv = pt->hf(k); // 해시 함수를 통해 생성된 해시 값
	Slot newSlot = { k, v };

	if (TBLSearch(pt, k) != NULL) // 키가 중복된다면
	{
		printf("키 중복\n");
		return;
	}
	else
		LInsert(&(pt->tbl[hv]), newSlot);
}

// 키를 근거로 테이블에서 데이터 삭제
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;
				}
			}
		}
	}

	return NULL; // 삭제를 못했다면 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; // 못찾았다면 NULL 반환
}

 

그리고 마지막으로 체이닝 기법을 반영하여 구현한 Table.c 파일.

연결 리스트를 잘 이해하고 있다면 크게 어려울 코드는 아니었다.