[Data Structures] Hash Table (해시 테이블)

Hashing

Hashing은 데이터의 삽입, 삭제, 조회를 상수 시간에 수행하기 위해 사용되는 기술이다.

 

Hash Table

Hash Table은 Key와 Value를 포함하는 고정된 길이의 배열이다.

 

Hash Function

Hash function은 각각의 Key를 Hash Table의 특정 셀에 맵핑한다. 이는 가능한 계산하기 간단해야 하며, Collision(충돌, 후술 할 것)을 최소화 하도록 설계되는 것이 좋다. 또한 Hash Function의 값은 Uniform한 분포를 따라야 한다.

 

Implementation of Simple Hash Table

주민번호가 key이고 주민 객체가 value인 간단한 Hash Table을 구현할 것이다.

다음은 Person의 ADT와 구현체이다.

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

 

#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;
}

 

Table을 구현하기 전에 Table에 Slot(각각의 칸)들을 먼저 정의할 것이다.

#include "Person.c"

typedef int Key;
typedef Person *Value;

enum SlotStatus
{
    EMPTY,
    DELETED,
    INUSE
};

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

 

Table의 Slot은 각각의 Key와 Value, 그리고 상태값을 가질 것이다.

 

다음은 Table의 ADT와 구현체이다.

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

#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; // 탐색 대상의 값 반환
}

Collision

  Collision(충돌)은 서로 다른 key가 Hash Function에 의해 같은 셀에 맵핑 될 때 발생한다. 이것의 발생을 최소화하는 Hash Function일 수록 좋다.

  위에서 구현한 예시에서는 hash function이 주민 번호 뒤의 두자리를 반환하는 함수라면 20120003과 20210103은 같은 03이라는 값으로 충돌이 발생하게 된다.

 

 

Resolving Collision : Separating Chaining (Open Hashing, Closed Addressing)

 

  위 그림에서 보이듯 슬롯을 생성하여 연결 리스트의 모델로 연결해나가는 방식으로 충돌 문제를 해결하는 것이 Chaining 방법이다. Chaining 방법을 적용하면 하나의 해쉬 값에 다수의 슬롯을 둘 수 있다. 따라서 탐색을 위해서는 동일한 해쉬 값으로 묶여있는 연결된 슬롯을 모두 조사해야 한다는 불편이 따른다. 하지만 해쉬 함수를 잘 정의한다면, 그래서 충돌의 확률이 높지 않다면 연결된 슬롯의 길이는 부담스러운 정도가 아닐 것이다.

 

Implementation of Chaining Hash Table

다음은 Chaining에 맞게 Slot을 재정의 한 것이다.

#include "Person.c"

typedef int Key;
typedef Person * Value;

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

 

Chaining을 사용할 경우 상태 정보가 필요가 없기 때문에 삭제 하였다.

 

다음은 Chaining에 맞게 Table을 재정의 및 재구현 한 것이다.

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

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

#include <stdio.h>
#include <stdlib.h>
#include "Table2.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;
                }
            }
        }
    }

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

 

Resolving Collision : Open Addressing (Closed Hashing)

- Linear Probing and Quadratic Probing

  충돌이 발생했을 때, 그 옆자리가 비었는지 살펴보고, 비었을 경우 그 자리에 대신 저장하는 방식이다. 단, 이 방식은 충돌의 횟수가 증가함에 따라서 '클러스터(Cluster) 현상', 쉬운 표현으로 '특정 영역에 데이터가 집중적으로 몰리는 현상'이 발생한다. 이러한 클러스터 현상은 충돌의 확률을 높이는 직접적인 원인이 된다. 이러한 단점을 극복하기 위해 충돌이 일어난 지점에서 약간 더 멀리 있는 빈 공간을 찾는 방식이 Quadratic Probing이다.

  요약하자면 Linear Probing은 충돌 발생 시 n칸 옆의 슬롯을 검사한다면, Quadratic Probing은 n^2칸 옆의 슬롯을 검사한다.

 

- Double Hashing

말 뜻 그대로 이중으로 Hash function을 사용하는 것이다.

 

1차 Hash Function : Key를 근거로 저장 위치를 결정하기 위한 것 [Hash_1(key) = key % 10]

2차 Hash Function : 충돌 발생 시 몇 칸 뒤를 살필지 결정하기 위한 것 [Hash_2(key) = 7 - (key % 7)]

가 있다.

가 있을 때, 

Hash(key) = {Hash_1(key) + Hash_2(key)} % 10

로 예를들 수 있다.