[자료구조] 테이블과 해쉬 - 2

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

앞선 테이블에서의 문제점을 정리하자면

• 직원 고유번호의 범위가 배열의 인덱스 값으로 사용하기 적당하지 않다.
• 직원 고유번호의 범위를 수용할 수 있는 매우 큰 배열이 필요하다.

그렇기에 우리는 해쉬 함수를 활용해 이 문제점들을 해결할려고한다.

이 함수를 소개하기전 앞서 보인 예제를 "직원의 고유번호는 입사년도 네자리와 입사순서 네자리로 구성된다"의 가정을 추가하여 재구현 해보겠다.

어떤가!
배열의 길이를 100으로 하였다는건 직원의 수가 100명을 넘길 경우를 고려하지 않은것이고!
GetHashValue()라는 함수를 통해 가공을 거치게되었다

100 % 연산의 의미는

"여덟 자리 수로 이뤄진 직원의 고유번호를 2자리의 수로 변경하라"

라는 의미이다!
이 함수를 에프엑스라고하면 !

이 함수를 가리켜 해쉬함수라고 한다.

그런데... 생각해보자..
100명을 넘어서
20210003
20210103
이 두명의 사원이 들어왔다.
그러면!!

충돌이 일어난다!!!!

이러한 충돌은 피해야 할 상황이 아니라 "해결해야 하는 상황"이다

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

그럼! 다시한번 구현해보자!

어느 정도 갖춰진 테이블과 해쉬의 구현의 예

어느정도 모습을 갖춘 테이블과 해쉬의 구현을 위해
테이블에 저장할 대상에 대한 헤더파일과 소스파일을 보자
Person.h

//
//  Person.h
//  HashTable
//
//  Created by 서희찬 on 2021/04/22.
//

#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_h */

Person.c

//
//  Person.c
//  HashTable
//
//  Created by 서희찬 on 2021/04/22.
//
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "Person.h"

int GetSSN(Person * p)
{
    return p->ssn; // key 값이니 별도로 함수를 짜주었다.
}

void ShowPerInfo(Person * p)
{
    printf("주민등록번호 : %d \n",p->ssn);
    printf("이름 : %s",p->name);
    printf("주소: %s",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 이 "키"이다! 그렇기에 따로 추출하는 함수도 정의해주었다.

이어서 테이블의 구현과 관련있는 파일들을 소개하겠다!
슬롯에 대한 파일들이다!

Slot.h

//
//  Slot.h
//  HashTable
//
//  Created by 서희찬 on 2021/04/22.
//

#ifndef Slot_h
#define Slot_h
#include "Person.h"

typedef int Key; // ssn
typedef Person * Value;

enum SlotStatus {EMPTY, DELETED, INUSE};

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

#endif /* Slot_h */

슬롯이란 "테이블을 이루는, 데이터를 저장할수 있는 각자의 공간"을 의미함을 구조체 슬롯을 스윽~ 보면 알것이다.

• 키 : 주민
• 값 : Person 구조체 변수의 주소 값

같이 설정하고 enum 선언을 통해 슬롯상태를 나타내는 상수를 정의하였다.
상수들의 의미하는 바는 다음과 같다.

• EMPTY 이 슬롯에는 데이터가 저장된바 없다.
• DELETED 저장되었으나 현재는 비워진 상태
• INUSE 현재 유효한 데이터가 저장되어 있다.

DELETED 의 필요성에는 의문이 생기겠지만 보편적으로 위의 세가지로 구분한다는것을 알아야한다!!!

그럼 이어서 table의 실질적 구현에 해당하는 헤더와 소스파일을 보자

Table.h

//
//  Table.h
//  HashTable
//
//  Created by 서희찬 on 2021/04/22.
//

#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_h */

Table.c

//
//  Table.c
//  HashTable
//
//  Created by 서희찬 on 2021/04/22.
//
#include <stdio.h>
#include <stdlib.h>
#include "Table.h"


void TBLInit(Table * pt, HashFunc * f)
{
    int i;
    
    // reset all slot
    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; // 탐새 대상의 값 반환
}

이제 이를 대상으로 하는 main func 을 소개하겠다.
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, "Seo", "MASAN");
    TBLInsert(&myTbl, GetSSN(np), np);
    
    np = MakePersonData(20120025, "Hwe", "SEOUL");
    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, 20120025);
    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, 20120025);
    if(rp != NULL)
        free(rp);
    
    return 0;
}

성공적으로 출력이 된다!!!

이로써 우리가 모델로 삼을 수 있는 테이블의 구현이 완료되었지만 여전히 충돌에 대한 해결책을 담고 있지 않다 !
이제 다음포스트에서 충돌에 대한 해결책을 담아보자 !