[열혈자료구조] 13강. 해쉬 테이블

* 본 글은 [윤성우의 열혈 자료구조 - C언어를 이용한 자료구조 학습서] 를 바탕으로 작성하였습니다.

 

앞서 나왔던 자료구조 중 일반적인 상황에서 탐색에 가장 효율적인 것은 AVL 트리(https://cascade.tistory.com/99)로 O(logN)의 시간 복잡도를 가지고 있었다. 본 포스팅에서 다룰 자료구조는 탐색을 한 번에 하는, O(1) 짜리 자료구조인 테이블이다. 테이블이란, 사원번호 - 이름 표와 같이 key와 value로 저장된 데이터 구조이다. 여기에는 세 가지 규칙이 있다.

• Key는 반드시 Value와 쌍을 이룬다
• Key가 존재하지 않는 값은 저장할 수 없다.
• 어떤 Key도 중복되지 않는다.

먼저, 배열을 기반으로 테이블 자료구조를 구현하자.

배열 기반의 테이블 구현

위에서 든 예와 같이, 사원번호와 이름을 매칭하는 테이블을 만든다고 하면, 모든 번호와 이름은 쌍으로 존재하므로 아래와 같은 구조체를 잡을 수 있다.

typedef struct _empInfo
{
	int empNum;
	int name;
}EmpInfo;

 

이때, main 함수에 아래와 같이 선언을 한다면, 키를 기반으로 데이터를 바로 찾을 수 있어야 한다.

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

	return 0;
}

 

즉, 저장과 탐색은 각각 아래와 같이 할 수 있다.

empInfoArr[ei.empNum] = ei; // 저장
ei = empInfpArr[eNum]; // 탐색

 

이는 직원의 고유번호를 인덱스로 하여 그 위치에 데이터를 저장하는 방식이다. 그러나, 이런 방식으로 테이블을 만들면, 고유번호가 0~999까지인 직원만 저장할 수 있어, 1000을 넘는 번호를 저장할 수 없다. 이를 해결하기 위해, 해쉬 함수를 도입한다.

해쉬 함수의 이용

앞서 배열로 구현한 테이블의 단점은 키가 가질 수 있는 값이 많아질 때 그만큼 큰 배열이 필요하다는 것이었다. 이를 해결하는 방법은, 넓은 범위의 키를 좁은 범위의 키로 대응시키는 것이다. 이런 기능을 하는 함수를 해쉬 함수(Hash function)라고 한다. 예를 들어, 고유번호를 100으로 나눈 나머지를 반환하는 함수 f(x)를 해쉬 함수로 잡는다면, 배열의 길이가 100만 되어도 될 것이다. 그런데, 이때 또 생기는 문제는 112번과 2112번이 같은 키 값을 가지는 것인데, 이를 충돌 문제(collision)이라고 한다.

 

이를 해결하기에 앞서, 먼저 Slot을 정의하자. Slot은 테이블을 이루는 데이터가 저장되는 공간으로, key와 value가 저장되며, 슬롯의 상태를 나타내는 enum이 들어간다.

enum SlotStatus {EMPTY, DELETED, INUSE};

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

 

좋은 해쉬 함수의 조건

 

좋은 해쉬 함수는 데이터가 테이블의 전체 영역에 고루 분포되는 함수이다. 이는 충돌의 확률을 낮추는 역할을 한다. 반면 나쁜 해쉬 함수는 테이블의 특정 영역에 데이터가 몰리게 한다. 키의 일부분만 참조하는 해쉬 함수는 일반적으로 나쁜 해쉬 함수이고, 키 전체를 참조하는 함수는 좋은 함수이다.

 

좋은 해쉬 함수를 만드는 방법은 상황마다 다른데, 그 예시로는 자릿수 선택(digit selection)과 자릿수 폴딩(digit folding) 방법이 있다.자릿수 선택은 키의 특정 부분에서 중복 비율이 높은 부분 혹은 공통부분이 있을 때, 이를 제외하는 방법을 말한다. 자릿수 폴딩은 자릿수별로 쪼개어 더한 값을 해쉬로 결정하는 방법이다.

 

충돌 문제의 해결 1: 일차, 이차 조사법

 

만약의 가능성으로 충돌이 발생했을 때 그 자리를 대신하여 빈 자리를 찾아 데이터를 저장해야 한다. 이러한 빈 자리를 찾는 방법으로는 선형 조사법(Linear Probing)과 이차 조사법(Quadratic Probing)이 있다. 먼저 선형 조사법은 키 k에 대해 f(k)에서 충돌이 났을 때, f(k) + 1, f(k) + 2 등과 같이 선형적으로 빈 자리를 찾는 방법이다. 이 방법은 충돌의 횟수가 늘어나면 클러스터 현상(데이터가 한쪽으로 몰리는 현상)이 일어난다는 단점이 있다.

 

다음으로 이차 조사법은 마찬가지로 f(k)에서 충돌이 났을 때 f(k) + 1^2, f(k) + 2^2, ... 과 같이 조사하는 방법이다. 일차 조사법에 비해 , 충돌이 발생한 곳보다 먼 곳에서 조사를 하는 것이다.

 

위에서 정의한 enum에서 슬롯의 상태를 EMPTY와 INUSE로만 구분하지 않고 DELETED까지 넣은 이유가 그것이다. 슬롯에 존재했다가 삭제된 데이터 중, 삭제되기 전에 충돌을 일으켜 조사법에 의해 다른 위치에 저장된 데이터가 있을 수도 있기 때문이다. 따라서, DELETED을 넣는 이유는 조사법을 적용하기 위해서이다.

 

충돌 문제의 해결 2:  이중 해쉬

 

이차 조사법의 문제는, 해쉬 값이 같을 때 충돌 발생 시 접근 위치가 항상 같다는 점이다. 즉, 클러스터가 발생할 확률이 여전히 높은 것이다. 이는 f(k) + n^2 와 같이 뒤에 붙는 조사 항이 너무 규칙적이기 때문에 일어나는 문제이다. 따라서, 해쉬 함수를 아래와 같이 두 가지로 나눌 수 있다.

1. 1차 해쉬: 키를 통해 저장 위치(index)를 결정
2. 2차 해쉬: 충돌이 생겼을 때 몇 칸 뒤를 살필지 결정

예를 들어, 1차와 2차 해쉬를 아래와 같이 정의할 수 있다.

h1(k) = k%15 (배열 길이 15)
h2(k) = 1+(k%c) (c는 15보다 작은 어떤 소수)

 

즉 키가 다르면 건너뛰는 칸의 수도 달라지기 때문에, 이차 조사법에 비해 훨씬 클러스터가 적게 발생한다.

 

충돌 문제의 해결 3: 체이닝

 

앞선 두 가지 방법은 충돌이 발생하면 다른 자리에 저장하는 open-addressing 방법이지만, 체이닝은 충돌이 발생해도 같은 곳에 저장하는 closed-addressing 방법이다. 이는 배열을 잡아서, 배열의 각 칸에 연결 리스트를 넣어 만든다. 즉 체이닝을 하면 하나의 해쉬 값에 대해 여러 개의 슬롯을 할당할 수 있다. 단, 해당 해쉬에 연결된 슬롯을 모두 조사해야 한다는 단점이 있다. 그러나 좋은 성능의 해쉬 함수를 사용하면 체인의 길이가 유의미하게 줄어들 것이므로 큰 문제는 아니다

 

체이닝의 구현

먼저, 아래와 같이 슬롯을 정의하였다.

#ifndef __SLOT2_H__
#define __SLOT2_H__

#include "Person.h"

typedef int Key;
typedef Person * Value;

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

#endif

 

다음으로, 아래와 같이 테이블을 정의하였다. 테이블이 slot의 배열이었던 이전과 달리, 이번에는 연결 리스트의 배열이다.

#ifndef __TABLE2_H__
#define __TABLE2_H__

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

#define MAX_TBL     100

typedef int HashFunc(Key k);

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);

#endif

 

이를 통해 슬롯이 연결 리스트의 노드 역할을 하게 할 수 있다. 또한, 연결 리스트의 노드와 슬롯을 구분해야 하는데, 이를 위해 node에 저장되는 data값으로 슬롯의 주소를 저장할 수 있다.

typedef Slot LData;

typedef struct _node
{
	LData data;
	struct _node * next;
} Node;