이번 Chapter부터는 조금 글의 양식을 바꾸도록 하겠다.

더 직관적으로? 보기 편하게? 하기위해서.

Ch.13 Table & Hash

13-1

이번 챕터도 탐색(Search)과 관련있는 내용을 다룬다.

Table?

이름을 들었을 땐 낯설다. 앞에선 ~ 리스트, ~ 트리 그렇게 다뤘는데, Table? 뉴페이스 카테고리의 등장이다. 그러면, 이게 뭔지. 기본적인 이해부터 해보자.

앞선 트리들, 그 중에서도 바로 앞에서 다뤘던 AVL트리는 탐색방면에서 매우 만족스러운 성능을 보였다. ( O(log2n)정도면 선방치지 않았는가. )

그런데, 만약 원하는 바를 "한번에" 찾아내는 방식이 있다면?

O(1)이 된다. 사실상 시간복잡도의 끝판왕인 셈이다.

이걸 왜 여기서 얘기를 꺼내냐. 테이블 자료구조의 시간복잡도가 O(1)의 시간복잡도를 보이니까!!

우선, 테이블의 기본적인 구조다.

..? 뭔가 새로운 그림이 나올 줄 알았더니, 엄청 익숙하다.

우리가 한글을 다룰때나 보던 표와 똑같다. ..테이블이 영어로 표니까.. 당장 위의 Bae 밑에 빨간 선과 오른쪽의 깜빡이(?)만 봐도 한글로 만든 티가 나긴 한다.

우리가 여기서 만약 "사번이 11113인 직원의 이름이 궁금하다" 라고 하면, 저 사번중에 11113만 찾으면 그 사번에 해당하는 직원의 이름이 Ms.Kim이라는 사실을 알 수 있다.

이 테이블은 아래의 조건을 만족할 때만 "테이블 자료구조"로서의 역할을 할 수 있다.

- 저장되는 데이터는 키(key), 값(value)이 하나의 쌍을 이룸 : 쉽게 말하면 "고유성"을 지닌다는 의미다.

- 키가 존재하지 않는 '값'은 저장할 수 없다. : "key"를 통해서 고유성이라는것을 지니게 해주는데, 이 키가 없으면 테이블 자료구조에 저장하지 못한다.

그리고 이 테이블은 사전과 같은 맥락에서 이해할 수 있다고 "사전 구조", 더불어 "맵"이라고 불린다.

그리고 구현에 앞서 알아두어야 할 것 중 하나가, key를 인덱스 값으로 하여, 그 위치에 데이터를 저장해야한다는 것이다.

그러니까 위의 사번 표를 예시로 들면, 사번(key)값인 11112, 11113.. 등을 인덱스 값으로 친다는거다.

근데 여기서 문제가 될 수 있는게, 고유번호의 범위가 1,000,000 ~ 100,000,000 까지라면? 인덱스 값이 너무 광범위해져서, 이후에 이에 관련된 해쉬에 대해서는 따로 설명해주겠다. 일단 이런 문제점이 있을수도 있다는 것. 미리 알아두자.

Table 구현 (feat. Hash)

예시로 구현된 코드를 하나 보자.

/* TableSimpleExample.c */

#include <stdio.h>

typedef struct _empInfo {
    int empNum; // 직원의 사번. 즉 key
    int age; // 직원의 나이. 즉 value
} EmpInfo;

int GetHashValue(int empNum) { // 위에서 언급한 Hash. 자세한건 아래 내용 참고
    return empNum % 1000;
}

int main() {
    EmpInfo empInfoArr[100]; // 100명 저장
    
    EmpInfo emp1 = {110112, 26};
    EmpInfo emp2 = {110113, 31};
    EmpInfo emp3 = {110444, 28};
    
    EmpInfo r1, r2, r3;
    
    // key를 인덱스 값으로 이용해서 그 위치에 데이터를 저장한다.
    empInfoArr[GetHashValue(emp1.empNum)} = emp1;
    empInfoArr[GetHashValue(emp2.empNum)} = emp2;
    empInfoArr[GetHashValue(emp3.empNum)} = emp3;
    
    // key를 인덱스 값으로 이용하여 탐색한 후
    // 해당하는 데이터를 각각 r1, r2, r3에 저장한다.
    r1 = empInfoArr[GetHashValue(110112)};
    r2 = empInfoArr[GetHashValue(110113)};
    r3 = empInfoArr[GetHashValue(110444)};
    
    // 출력
    printf("Emp Num : %d, Age : %d \n", r2.empNum, r2.age);
    
    return 0;
}

만약 사원번호 "xxoooo"가 xx는 입사 년도 (2013년 입사시 13), oooo는 그 해 몇 번째로 입사한 직원인지를 알려주는 정보라고 가정하자.

그럼 여기서, GetHashValue 함수는 무슨 역할을 할까?

앞서 인덱스 값이 너무 광범위해지면 이에 필요한 해쉬라는게 있다고 언급을 했다. 만약 이 해쉬라는게 없을 때 문제점이 뭐냐.

1. key의 범위가 배열의 idx값으로 쓰기에 적당하지 않다.
2. key의 범위를 수용할 수 있는 매우 큰 배열이 필요하다.

이다. 그런데 이 두 문제를 해결해주는 것이 해쉬함수이다.

그러면, 여기서 다시 GetHashValue 얘기로.

만약 여기서 앞서 언급한 사번 "xxoooo"에서 한 해에 200명을 새 직원으로 뽑지 않는 회사라고 가정하면, ooo정도면 충분하다. 아래의 어떤 반례를 위해, 그냥 oooo라고 하겠다. 그러면 여기서 GetHashValue 의 empNum % 1000를 f(x) 함수라고 가정하자.

그러면 당장 위의 코드에 있는 세명의 사번이 112, 113, 444로 겹칠 일이 없다. 여기서 이 f(x)를 해쉬 함수(Hash Function)라고 한다. 한줄 요약하자면, 넓은 범위의 키를 좁은 범위의 키로 변경하는 역할을 한다는 것이다. 다섯 자리의 사번을 세자리의 사번으로 고유성을 유지하면서 범위를 줄여줬으니까.

그런데, 만약 이후에 회사가 급격히 성장하며 한 해에 1000명 이상의 직원을 뽑는다고 가정하면 문제다.

만약 141112 라는 사번을 가진 직원이 들어오면, 110112라는 사번을 가진 직원과 키가 똑같아 진다. 둘 다 112, 112로.

이런 상황을 충돌(COLLISION)이라고 하는데, 충돌은 "피해야 하는" 문제방법이 아니고, "해결해야 하는 방법이다". 알아두자.

Slot

위의 TableSimpleExample.c 예시를 보면, 그냥 코드파일 하나로 단순하게 구현되지만, 무언가 구색이 깔끔하게 갖춰진 Table을 보면, 다른 자료구조들처럼 헤더파일, 소스파일이 여러개로 나뉘어진다.

그런데 여기서, 위에서 언급한 충돌이라는 문제점을 해결하기 위해서는 Slot이라는 구조체가 필요하다.

slot이란 테이블을 이루는, 데이터를 저장할 수 있는 각각 공간을 의미한다.

아래 예시를 보자. (Person형 변수엔 사람의 주민번호, 이름, 주소가 저장된다고 가정하자)

/* Slot.h */

#ifndef __SLOT_H__
#define __SLOT_H__

#include "Person.h" // github의 ch.13 참고

typedef int Key; // 주민번호가 key가 된다.
typedef Person * Value; // Person 구조체 변수의 주소값

enum SlotStatus {EMPTY, DELETED, INUSE}; // Slot의 상태를 나타내는 상수들

// EMPTY 비어있다, DELTETED 데이터가 저장되었었으나 현재는 비워져있다, INUSE 데이터 저장되어있다

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

#endif

Slot의 핵심은 slot 구조체가 데이터를 저장할 수 있는 공간을 만들어준다는 사실과, 각 slot마다 상태를 표현할 수 있는 status가 있다는 점인데, 다른건 그렇다 치고. DELETED는 왜 있는걸까?

앞서 언급한 "충돌"을 해결할 방법의 핵심이 DELETED다. 자세한 설명은, 다음 챕터에서 설명해주겠다.

What is a good condition of Hash Function?

그림 두개를 보여주겠다.

두 그림은 해쉬함수 1, 2를 사용한 결과를 그림으로 표현한 것이다.

아래의 그림에서 검은 영역은 데이터가 채워진 슬롯이고, 흰 영역은 빈 슬롯이다.

그리고, 두 그림에 저장되어있는 데이터의 양은 동일하다고 가정한다.

위의 1번, 2번 중 어떤 그림이 좋은 해쉬함수를 사용한 결과일까?

1번은 해쉬값(데이터라고 생각하자)이 고루 분포되어있어서, "충돌"이 발생할 확률이 낮다.

2번은 반대로, 해쉬값이 한곳에 집중되어 있어 "충돌"이 발생할 확률이 높다.

뭐, 이렇게 설명하면 바로 알 수 있지 않은가.

그러면, 여기서 우리가 1번과 같은 결과를 이끌어 내려면 어떻게 해쉬함수를 짜서 "좋은 해쉬 함수"를 만들어야 하는지가 의문일 수도 있다.

정답은 없지만, 노하우는 있다.

1. 키의 특성에 따라 달라진다.
2. 좋은 해쉬 함수는 "키의 일부분"을 참조하지 않고, "키 전체"를 참고하여 해쉬 값을 만들어낸다.

좋은 해쉬 함수의 디자인 방법의 여러 개중, 책에 실려있는 방법은 자릿수 선택(Digit Selection), 자릿수 폴딩(Digit Folding) 이다.

자릿수 선택은 "여러 자리의 수로 이뤄진 키중 다양한 해쉬 값 생성에 도움을 주는 몇 자리의 수를 뽑아 해쉬값을 생성한다"는 것이다. 모든 키들에 공통으로 들어가는 값 (or 중복의 비율이 높은 값)을 제외한 나머지로 해쉬값을 생성하는 방법이다.

자릿수 폴딩은 여섯 자리 숫자를 모두 반영하여 얻은 결과다. 말로 설명하긴 조금 어려운데, 아래 그림을 참고하자.

여기까지.