본문 바로가기
C/자료구조와 알고리듬

Chapter 09. 해시 테이블(Hash Table)

by GameStudy 2021. 11. 12.

Chapter 06. 목차.

 

  6.1 아이디어

  6.2 해시 셋

  6.3 해시 함수와 해시 값.

  6.4 해시 테이블 With 배열

  6.5 해시 테이블 With Doubly Linked list

 

6.1 탄생 배경과 구현 방법

  - 우리의 뇌가 어떤 기억을 상기시키는 메커니즘을 생각해보자.

    자신이 살아온 모든 기억을 선형 탐색하며 찾진 않음.

    마치 어떤 Key가 있고, 해당 Value를 순식간에 찾아냄.

 

  - 병원에가도 마찬가지임. 주민번호를 읊으면 순식간에 

    5천만명중 정확하게 내 정보만 나오게 됨.

    만약 선형 탐색한다면? 탐색하다 사망할 수도 있음.

    이진 탐색은? 정렬되어 있지 않아서 사용 불가.

    5천만개의 자료를 정렬하는데도 오래걸림.

 

  - 우체통도 각 가구마다 번호가 적혀 있어서 편하게 가져갈 수있음.

    그러나 큰 바구니에다가 모든 가구의 우편을 섞어둔다면?

 

  - 이런 식으로, 임의의 크기를 가진 입력 값[우편물]을

    고정된 크기를 가진 값[가구 주소]으로 변환 시키는 작업을

    Hashing이라 함. 혹은 Hash 기법이라고 부름.

    아무리 큰 고기도 잘게 썰어버리면,

    우리가 원하는 모양으로 만들 수 있어서

    이런 이름이 채택 된 것이 아닐까 싶음.

    조금 엄밀한 정의는 이번 포스트를 진행하면서 알게 됨.

 

  - 이런 기법을 활용하여 만든 자료구조를

    Hash Set, Hash Map, Hash Table이라 부름.

 

  - Java 기준, 관련 자료구조들의 정리를 보면 좀 더 이해가 잘됨.

    Set: 순서는 중요치 않으며, 그저 데이터를 집합시킨 자료구조.

    Hash Set: 중복 없이 데이터를 집합시키게끔 설계된 자료구조.

    Map: Key와 Value로 데이터를 접근하게끔 설계된 자료구조.
    Hash Map: 동기화를 보장하지 않음.

    Hash Table: 동기화를 보장함.

    여기서 동기화란, thread의 memory race condition을 막는 것.

 

  - 구현 방법 1: 입력값의 최댓값만큼 배열 크기로 잡기.

    가장 단순하면서도 무식한 방법.

    즉, 이 경우에 입력값이 곧 배열의 색인이 됨.

    그러나, 입력값이 너무나도 크다면? 너무 비효율적임.

    그래도 배열의 크기가 크면 클수록 해시 테이블을 구현하는데

    더 좋을 것이라는 걸 알 수 있음.

 

  - 구현 방법 2: 입력값 % 배열의크기로 색인 만들기

    입력값이 배열의 크기내에서 움직이게 됨.

    그런데 동일한 색인을 갖는 입력값들이 생기게됨.

    궁여지책으로 배열의 크기를 늘린다 한들,

    겹치는 색인이 덜생길 뿐 여전히 존재함.

 

  - 구현 방법 3: 배열의 크기를 2배로 계속 키움 && 소수로 나머지 연산하기

    배열의 크기가 커지면, 겹치는 색인이 줄어들 수 있음.

    소수는 약수가 1과 자기 자신 뿐인 수이므로,

    임의의 수가 들어왔을 때, 소수의 배수일 확률이 급격하게 줄어듬.

 

  - 구현 방법 3도 결국 중복 색인 문제가 발생함.

    구한 색인 위치 이후에 빈 공간을 찾아서 저장하게끔 하자.

 

6.2 해시 셋(Hash Set)

  - 해시 테이블을 구현하기 위해서는 먼저 해시 셋을 구현해야 함.

    Value를 중복 없이 저장 가능해야 하기 때문.

 

  - 집합 내의 임의의 데이터를 중복 없이 저장하는 자료구조.

 

  - 구현 방법으로는 기본적으로 배열을 활용한 구현 방법과
    배열 + 연결 리스트를 활용하는 방법이 있음.

 

  - 배열 + 연결 리스트를 활용하면, 배열의 색인 중복을 막기위해

    다음 해시값에 저장 안해도 됨. 그냥 해당 칸에 노드를 추가하는 식.

    즉, 같은 해시값을 가져도 됨. 굳이 남의 해시값을 뺏지 않음.

    따라서 배열만 활용해서 만든 해시 셋보단 빨라짐.

    다만 최악의 경우, 모두 같은 해시값을 가진다면 똑같이 O(N).

    그럴 일이 많진 않음.

 

  Ex) 해시 셋 With 배열
    중복 색인을 해결 하기 위해서, 빈 색인 위치가 아니라면

    1씩 증가해서 빈 색인 위치를 찾아내도록 설계함.

    빈 색인 위치에는 INT_MIN을 넣어둠.

    초 간단 해시 셋의 예. 중복 색인이 없다면 검색/삽입/삭제 모두 O(1)

    그러나 중복 색인이 나타날 확률이 엄청 큼.

<hide/>

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
#include <limits.h>

enum {
    FALSE = 0,
    TRUE = 1,
    INVALID_INDEX = -1,
    BUCKET_SIZE = 7
};

typedef struct HashSet {
    int nArray[BUCKET_SIZE];
} HashSet_t;

void initHashSet(HashSet_t* _pHashSet);
int isInHashSet(HashSet_t* _pHashSet, int _nData);
int insert(HashSet_t* _pHashSet, int _nData);
int delete(HashSet_t* _pHashSet, int _nData);
void print(HashSet_t* _pHashSet);

int main(void)
{
    HashSet_t hashSet;
    initHashSet(&hashSet);

    insert(&hashSet, 123);  /* 4 */
    insert(&hashSet, 699);  /* 6 */
    insert(&hashSet, 541);  /* 2 */
    insert(&hashSet, 8341); /* 4 */
    insert(&hashSet, 136);  /* 3 */

    print(&hashSet);

    delete(&hashSet, 541);
    delete(&hashSet, 8341);

    print(&hashSet);

    return 0;
}

void initHashSet(HashSet_t* _pHashSet)
{
    size_t i;
    for (i = 0; i < BUCKET_SIZE; ++i) 
    {
        _pHashSet->nArray[i] = INT_MIN;
    }
}

int isInHashSet(HashSet_t* _pHashSet, int _nData)
{
    int i, nStartIndex = _nData % BUCKET_SIZE;

    if (nStartIndex < 0)
    {
        nStartIndex += BUCKET_SIZE;
    }

    i = nStartIndex;
    do {
        if (_nData == _pHashSet->nArray[i])
        {
            return TRUE;
        }
        else if (INT_MIN == _pHashSet->nArray[i])
        {
            return FALSE;
        }

        i = (i + 1) % BUCKET_SIZE;
    } while (i != nStartIndex);

    return FALSE;
}

int insert(HashSet_t* _pHashSet, int _nData)
{
    int i, nStartIndex = _nData % BUCKET_SIZE;

    if (nStartIndex < 0)
    {
        nStartIndex += BUCKET_SIZE;
    }

    i = nStartIndex;
    do {
        if (_nData == _pHashSet->nArray[i] || INT_MIN == _pHashSet->nArray[i])
        {
            _pHashSet->nArray[i] = _nData;

            return TRUE;
        }

        i = (i + 1) % BUCKET_SIZE;
    } while (i != nStartIndex);

    return FALSE;
}

int delete(HashSet_t* _pHashSet, int _nData)
{
    int i, nStartIndex = _nData % BUCKET_SIZE;

    if (nStartIndex < 0) 
    {
        nStartIndex += BUCKET_SIZE;
    }

    i = nStartIndex;
    do {
        if (_nData == _pHashSet->nArray[i])
        {
            _pHashSet->nArray[i] = INT_MIN;
            
            return TRUE;
        }
        else if (INT_MIN == _pHashSet->nArray[i])
        {
            return FALSE;
        }

        i = (i + 1) % BUCKET_SIZE;
    } while (i != nStartIndex);

    return FALSE;
}

void print(HashSet_t* _pHashSet)
{
    size_t i;
    for (i = 0; i < BUCKET_SIZE; ++i)
    {
        if (INT_MIN == _pHashSet->nArray[i])
        {
            printf("[%zu]: %s\n", i, "INT_MIN");
        }
        else
        {
            printf("[%zu]: %d\n", i, _pHashSet->nArray[i]);
        }
        
    }
    printf("\n");
}

 

6.3 해시 함수와 해시 값

  - 6.2에서 임의의 크기를 가진 데이터를

    고정 크기를 가진 데이터로 대응되게끔 하는 것을

    Hashing이라고 정의함.

    이렇게 대응되게끔 하는 함수를 해시 함수라 함.

 

  - 해시 함수를 통해 나온 고정 크기를 가진 데이터를

    해시 값이라고 함.

 

  - 정수값 % BUCKET_SIZE는 해시 함수일까?

    그냥 정해진 배열 안에 우겨 넣기 위해서 쓴 것이지

    해시 함수로 사용한건 아님.

    하지만, 정수 값의 경우 두 값이 같으면 ID도 같음.

    그래서 정수값 == ID == 유사 해시라고 할 수 있음.

   

  - 해시 함수의 성질은 아래와 같음.

    첫번째. 함수이므로, 입력값이 같으면 출력값도 언제나 같음.

    두번째. 입력값이 달라도 출력값이 같을 수 있음.

 

  - 두번째와 같은 경우를 해시 충돌(Hash Collision)이라 함.

    이런 경우가 최대한 없을 수록 좋음.

    따라서 출력값으로부터 입력값을 찾을 수 있다는 보장이 없음.

 

  - 즉 해시 값은 임의의 크기를 가진 데이터를

    대표하는 값이라고 할 수 있음.

    ex. 사람은 숫자가 아니지만, 주민번호가 그 사람을 대표함.

      즉, 주민번호는 해시 값이라고 할 수 있음.

 

  - 6.2에서의 예제 코드는 정수 값을 Hash set에 저장해 봄.

    근데 대부분의 해시 관련 자료구조들은 배열의 색인으로

    변환이 쉬운 정수 값을 해시 값으로 사용함.(모듈러 연산이 가능하기때문.)

    즉, 정수 값은 이미 그 자체가 해시 값이라고도 부를 수 있음.

 

  - 따라서 배열의 색인으로 변환이 어려운 문자열이 입력으로 

    들어온다 해보자. 그럼 이를 해시 값으로 변환해 줄

    해시 함수가 필요해짐.

 

  - 문자열의 각 요소를 합쳐서(ASCII Code) 해시 값을 만들고,

    해시 값을 통해서 배열의 색인을 만들어 내는 식으로 구현 해보자.

 

Ex) ASCII Code의 합으로 해시 함수 구현

<hide/>

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <string.h>

enum {
    FALSE = 0,
    TRUE = 1,
    INVALID_INDEX = -1,
    BUCKET_SIZE = 7
};

typedef struct HashSet {
    const char* pArray[BUCKET_SIZE];
} HashSet_t;

void initHashSet(HashSet_t* _pHashSet);
size_t hash(const char* _pData);
int isInHashSet(HashSet_t* _pHashSet, const char* _pData, size_t (*hash_function)(const char*));
int insert(HashSet_t* _pHashSet, const char* _pData, size_t (*hash_function)(const char*));
int delete(HashSet_t* _pHashSet, const char* _pData, size_t (*hash_function)(const char*));
void print(HashSet_t* _pHashSet);

int main(void)
{
    HashSet_t hashSet;
    initHashSet(&hashSet);

    insert(&hashSet, "Park\0", hash);  /* 4 */
    insert(&hashSet, "Hwang\0", hash);  /* 4 */
    insert(&hashSet, "Lee\0", hash);  /* 4 */
    insert(&hashSet, "Kim\0", hash);  /* 4 */
    insert(&hashSet, "coco\0", hash);  /* 4 */
    insert(&hashSet, "ococ\0", hash);  /* 4 */

    print(&hashSet);

    delete(&hashSet, "ococ\0", hash);
    delete(&hashSet, "Lee\0", hash);

    print(&hashSet);

    return 0;
}

void initHashSet(HashSet_t* _pHashSet)
{
    size_t i;
    
    for (i = 0; i < BUCKET_SIZE; ++i) 
    {
        _pHashSet->pArray[i] = NULL;
    }
}

size_t hash(const char* _pData)
{
    size_t uHashValue = 0;
    const char* pTemp = _pData;
    while (*pTemp != '\0')
    {
        uHashValue += (size_t)(*(pTemp++));
    }

    return uHashValue;
}

int isInHashSet(HashSet_t* _pHashSet, const char* _pData, size_t (*hash_function)(const char*))
{
    size_t i, uStartIndex;
    size_t uHashValue = hash_function(_pData);
    uStartIndex = uHashValue % BUCKET_SIZE;

    i = uStartIndex;
    do {
        if (NULL != _pHashSet->pArray[i] && strcmp(_pData, _pHashSet->pArray[i]) == 0)
        {
            return TRUE;
        }
        else if (NULL == _pHashSet->pArray[i])
        {
            return FALSE;
        }

        i = (i + 1) % BUCKET_SIZE;
    } while (i != uStartIndex);

    return FALSE;
}

int insert(HashSet_t* _pHashSet, const char* _pData, size_t (*hash_function)(const char*))
{
    size_t i, uStartIndex;
    size_t uHashValue = hash_function(_pData);
    uStartIndex = uHashValue % BUCKET_SIZE;

    i = uStartIndex;
    do {
        if (NULL == _pHashSet->pArray[i] || strcmp(_pData, _pHashSet->pArray[i]) == 0)
        {
            /* intentional short-circuit. 자리 바꾸면 안됨. NULL 포인터 역참조 문제 발생.*/
            _pHashSet->pArray[i] = (char*)malloc(sizeof(_pData));
            memcpy((void*)_pHashSet->pArray[i], _pData, strlen(_pData) + 1);

            return TRUE;
        }

        i = (i + 1) % BUCKET_SIZE;
    } while (i != uStartIndex);

    return FALSE;
}

int delete(HashSet_t* _pHashSet, const char* _pData, size_t (*hash_function)(const char*))
{
    size_t i, uStartIndex;
    size_t uHashValue = hash_function(_pData);
    uStartIndex = uHashValue % BUCKET_SIZE;

    i = uStartIndex;
    do {
        if (strcmp(_pData, _pHashSet->pArray[i]) == 0)
        {
            _pHashSet->pArray[i] = NULL;
            
            return TRUE;
        }
        else if (NULL == _pHashSet->pArray[i])
        {
            return FALSE;
        }

        i = (i + 1) % BUCKET_SIZE;
    } while (i != uStartIndex);

    return FALSE;
}

void print(HashSet_t* _pHashSet)
{
    size_t i;
    
    for (i = 0; i < BUCKET_SIZE; ++i)
    {
        if (NULL == _pHashSet->pArray[i])
        {
            printf("[%zu]: %s\n", i, "NULL");
        }
        else
        {
            printf("[%zu]: %s\n", i, _pHashSet->pArray[i]);
        }
        
    }
    printf("\n");
}

  - 그러나, 이런식으로 만들면, O(1)이 아님.

    해시 함수에서 문자열의 길이만큼 반복문을 돌기 때문.

    즉, O(문자열길이)만큼의 시간 복잡도를 갖게됨.

 

  - 위 문제를 해결 하기 위해서는

    해시 함수를 최초 한 번만 호출하고, 해시 값을 기억해둠.

    그리고 필요할 때마다 해시 값으로 해시 셋 관련 함수들을 호출함. 

    근데 이러려면, 모든 키 값들을 이미 알고 있어야 함.

    그리고 충돌이 나지 않는다는 가정하에, 진정한 O(1)이 가능해짐.

    ex. 게임 내 모든 몬스터는 무한하지 않기에, 이런게 가능함.

 

  - 즉, 해시 셋에서 데이터에 해당하는 키 개념을 도입하면

    해시 테이블이 됨. 키와 벨류 쌍으로 모든 데이터를 저장하는 자료구조.

 

6.4 해시 테이블(Hash Table)

  Def) 어떤 Key에 대응하는 어떤 Value를 쌍으로 저장하는 자료구조.

    해당 키 위치의 값을 꺼내온다는 의미. 

    이런 형태를 보통 해시테이블. 엄밀히는 해시맵이라고 부름.

    C#에서의 Dictionary가 이 자료구조에 해당함.

 

  Ex) 해시 테이블 코드

<hide/>

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

enum {
    FALSE = 0,
    TRUE = 1,
    INVALID_INDEX = -1,
    BUCKET_SIZE = 23 // 2배보다 더 큰 소수
};

enum {
    SEARCH_FAIL_BY_ABCENT,
    INSERT_SUCCESS,
    INSERT_FAIL_BY_DUPLICATION,
    INSERT_FAIL_BY_CAPACITY,
    DELETE_SUCCESS,
    DELETE_FAIL_BY_EMPTY,
    DELETE_FAIL_BY_ABCENT
};

typedef struct HashTable {
    char* mpKeyArray[BUCKET_SIZE];
    int mnValueArray[BUCKET_SIZE];
} HashTable_t;

void InitHashTable(HashTable_t* pHashTable);
size_t HashFunction(const char* pKey);
int Search(HashTable_t* pHashTable, const char* pKey, size_t (*HashFunction)(const char*));
int Insert(HashTable_t* pHashTable, const char* pKey, const int nValue, size_t (*HashFunction)(const char*));
int Delete(HashTable_t* pHashTable, const char* pKey, size_t (*HashFunction)(const char*));
void DeleteAll(HashTable_t* pHashTable);
void Print(HashTable_t* pHashTable);

int main(void)
{
    HashTable_t hashTable;

    InitHashTable(&hashTable);

    Insert(&hashTable, "Park\0", 100, HashFunction);  
    Insert(&hashTable, "Hwang\0", 72, HashFunction);  
    Insert(&hashTable, "Lee\0", 88, HashFunction);  
    Insert(&hashTable, "Kim\0", 90, HashFunction);  
    Insert(&hashTable, "coco\0", 56, HashFunction);  
    Insert(&hashTable, "ococ\0", 66, HashFunction);  

    Print(&hashTable);

    printf("%s's score is %d\n", "Hwang", Search(&hashTable, "Hwang\0", HashFunction));
    Delete(&hashTable, "Hwang\0", HashFunction);

    printf("%s's score is %d\n", "Lee", Search(&hashTable, "Lee\0", HashFunction));
    Delete(&hashTable, "Lee\0", HashFunction);

    Print(&hashTable);

    DeleteAll(&hashTable);

    return 0;
}

void InitHashTable(HashTable_t* _pHashTable)
{
    size_t i;
    for (i = 0; i < BUCKET_SIZE; ++i)
    {
        _pHashTable->mpKeyArray[i] = NULL;
        _pHashTable->mnValueArray[i] = INT_MIN;
    }
}
size_t HashFunction(const char* pKey)
{
    size_t uHash = 0;

    const char* pTemp = pKey;
    while (*pTemp != '\0')
    {
        uHash += (size_t)(*(pTemp++));
    }

    return uHash;
}

int Search(HashTable_t* pHashTable, const char* pKey, size_t(*HashFunction)(const char*))
{
    size_t i, uStartIndex;
    size_t uHash = HashFunction(pKey);
    uStartIndex = uHash % BUCKET_SIZE;

    i = uStartIndex;
    do {
        if (NULL != pHashTable->mpKeyArray[i] && strcmp(pKey, pHashTable->mpKeyArray[i]) == 0)
        {
            return pHashTable->mnValueArray[i];
        }
        else if (NULL == pHashTable->mpKeyArray[i])
        {
            return SEARCH_FAIL_BY_ABCENT;
        }

        i = (i + 1) % BUCKET_SIZE;
    } while (i != uStartIndex);

    return SEARCH_FAIL_BY_ABCENT;
}

int Insert(HashTable_t* pHashTable, const char* pKey, const int nValue, size_t(*HashFunction)(const char*))
{
    size_t i, uStartIndex;
    size_t uHash = HashFunction(pKey);
    uStartIndex = uHash % BUCKET_SIZE;

    i = uStartIndex;
    do {
        if (NULL == pHashTable->mpKeyArray[i] || 0 == strcmp(pKey, pHashTable->mpKeyArray[i]))
        {
            pHashTable->mpKeyArray[i] = (char*)malloc(sizeof(pKey));
            memcpy((void*)pHashTable->mpKeyArray[i], pKey, strlen(pKey) + 1);

            pHashTable->mnValueArray[i] = nValue;

            return INSERT_SUCCESS;
        }

        i = (i + 1) % BUCKET_SIZE;
    } while (i != uStartIndex);

    return INSERT_FAIL_BY_CAPACITY;
}

int Delete(HashTable_t* pHashTable, const char* pKey, size_t(*HashFunction)(const char*))
{
    size_t i, uStartIndex;
    size_t uHash = HashFunction(pKey);
    uStartIndex = uHash % BUCKET_SIZE;

    i = uStartIndex;
    do {
        if (NULL != pHashTable->mpKeyArray[i] && 0 == strcmp(pKey, pHashTable->mpKeyArray[i]))
        {
            free((void*)pHashTable->mpKeyArray[i]);
            pHashTable->mpKeyArray[i] = NULL;

            return DELETE_SUCCESS;
        }
        else if (NULL == pHashTable->mpKeyArray[i])
        {
            return DELETE_FAIL_BY_ABCENT;
        }
    } while (i != uStartIndex);

    return DELETE_FAIL_BY_EMPTY;
}

void DeleteAll(HashTable_t* pHashTable)
{
    size_t i;
    for (i = 0; i < BUCKET_SIZE; ++i)
    {
        if (NULL != pHashTable->mpKeyArray[i])
        {
            free((pHashTable->mpKeyArray[i]));
            pHashTable->mpKeyArray[i] = NULL;
        }
    }
}

void Print(HashTable_t* pHashTable)
{
    size_t i;

    printf("===============\n");
    for (i = 0; i < BUCKET_SIZE; ++i)
    {
        if (NULL == pHashTable->mpKeyArray[i])
        {
            printf("[%zu]: %s\n", i, "NULL");
        }
        else
        {
            printf("[%zu]: %s (%d)\n", i, pHashTable->mpKeyArray[i], pHashTable->mnValueArray[i]);
        }
    }
    printf("===============\n");
}

 

 

  Def) 키(Key)

    데이터의 위치를 의미하는 데이터.

    꼭 정수가 아니어도 상관 없음. 문자열도 가능하며, 구조체도 가능.

 

  Def) 값(Value)

    실제 저장되는 데이터. 

 

  Note) 위에서 배운 해시 테이블에서는 두 가지 충돌이 발생함.

    첫 번째로, 해시 충돌. 키가 다르지만 같은 해시 값이 나올 수 있음.

    두 번째로, 색인 충돌. 해시 값이 다르지만 같은 색인이 나올 수 있음.

    두 번째는 어느정도 해결을 해봄.

 

  Note) 그런데 사실 해시 충돌 문제는 해결 안해도 되긴 함.

    색인 충돌 문제의 해법으로 같이 해결되기 때문.

    해시 충돌을 막는 방법은 훌륭한 해시 함수를 작성하는 것.

 

  Note) 훌륭한 해시 함수란,

    - 첫째, 입력이 어떤 경우라도 고정된 크기의 해쉬 값으로 변환 가능.

      여기서 어떤 경우란, 자료형 혹은 데이터의 크기에 상관 없이라는 뜻.

 

    - 둘째, 해시 충돌이 거의 없어야 함. 이것이 좋고 나쁨의 척도.

  

    - 해시 함수 테스트 표를 참고하면 훌륭한 해시 함수를 선택 가능함.

 

  Ex) 65599 해시 함수를 이용한 해시 테이블

<hide/>

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

enum {
    FALSE = 0,
    TRUE = 1,
    INVALID_INDEX = -1,
    BUCKET_SIZE = 23 // 2배보다 더 큰 소수
};

enum {
    SEARCH_FAIL_BY_ABCENT,
    INSERT_SUCCESS,
    INSERT_FAIL_BY_DUPLICATION,
    INSERT_FAIL_BY_CAPACITY,
    DELETE_SUCCESS,
    DELETE_FAIL_BY_EMPTY,
    DELETE_FAIL_BY_ABCENT
};

typedef struct HashTable {
    char* mpKeyArray[BUCKET_SIZE];
    int mnValueArray[BUCKET_SIZE];
} HashTable_t;

void InitHashTable(HashTable_t* pHashTable);
size_t HashFunction(const char* pKey);
size_t hash_65599(const char* pKey);
int Search(HashTable_t* pHashTable, const char* pKey, size_t (*HashFunction)(const char*));
int Insert(HashTable_t* pHashTable, const char* pKey, const int nValue, size_t (*HashFunction)(const char*));
int Delete(HashTable_t* pHashTable, const char* pKey, size_t (*HashFunction)(const char*));
void DeleteAll(HashTable_t* pHashTable);
void Print(HashTable_t* pHashTable);

int main(void)
{
    HashTable_t hashTable;

    InitHashTable(&hashTable);

    Insert(&hashTable, "Park\0", 100, hash_65599);
    Insert(&hashTable, "Hwang\0", 72, hash_65599);
    Insert(&hashTable, "Lee\0", 88, hash_65599);
    Insert(&hashTable, "Kim\0", 90, hash_65599);
    Insert(&hashTable, "coco\0", 56, hash_65599);
    Insert(&hashTable, "ococ\0", 66, hash_65599);

    Print(&hashTable);

    printf("%s's score is %d\n", "Hwang", Search(&hashTable, "Hwang\0", hash_65599));
    Delete(&hashTable, "Hwang\0", hash_65599);

    printf("%s's score is %d\n", "Lee", Search(&hashTable, "Lee\0", hash_65599));
    Delete(&hashTable, "Lee\0", hash_65599);

    Print(&hashTable);

    DeleteAll(&hashTable);

    return 0;
}

void InitHashTable(HashTable_t* _pHashTable)
{
    size_t i;
    for (i = 0; i < BUCKET_SIZE; ++i)
    {
        _pHashTable->mpKeyArray[i] = NULL;
        _pHashTable->mnValueArray[i] = INT_MIN;
    }
}
size_t HashFunction(const char* pKey)
{
    size_t uHash = 0;

    const char* pTemp = pKey;
    while (*pTemp != '\0')
    {
        uHash += (size_t)(*(pTemp++));
    }

    return uHash;
}

/*
    65599를 일부로 곱해서 오버플로가 나게끔 하는 해시 함수.
    간단하고 성능도 나쁘지 않아서, 이 해시 함수를 사용.
*/

static size_t hash_65599(const char* pKey)
{
    size_t i;
    size_t hash_id = 0;
    size_t length = strlen(pKey);

    hash_id = 0;
    for (i = 0; i < length; ++i) {
        hash_id = 65599 * hash_id + pKey[i];
    }

    return hash_id ^ (hash_id >> 16);
}

int Search(HashTable_t* pHashTable, const char* pKey, size_t(*HashFunction)(const char*))
{
    size_t i, uStartIndex;
    size_t uHash = HashFunction(pKey);
    uStartIndex = uHash % BUCKET_SIZE;

    i = uStartIndex;
    do {
        if (NULL != pHashTable->mpKeyArray[i] && strcmp(pKey, pHashTable->mpKeyArray[i]) == 0)
        {
            return pHashTable->mnValueArray[i];
        }
        else if (NULL == pHashTable->mpKeyArray[i])
        {
            return SEARCH_FAIL_BY_ABCENT;
        }

        i = (i + 1) % BUCKET_SIZE;
    } while (i != uStartIndex);

    return SEARCH_FAIL_BY_ABCENT;
}

int Insert(HashTable_t* pHashTable, const char* pKey, const int nValue, size_t(*HashFunction)(const char*))
{
    size_t i, uStartIndex;
    size_t uHash = HashFunction(pKey);
    uStartIndex = uHash % BUCKET_SIZE;

    i = uStartIndex;
    do {
        if (NULL == pHashTable->mpKeyArray[i] || 0 == strcmp(pKey, pHashTable->mpKeyArray[i]))
        {
            pHashTable->mpKeyArray[i] = (char*)malloc(sizeof(pKey));
            memcpy((void*)pHashTable->mpKeyArray[i], pKey, strlen(pKey) + 1);

            pHashTable->mnValueArray[i] = nValue;

            return INSERT_SUCCESS;
        }

        i = (i + 1) % BUCKET_SIZE;
    } while (i != uStartIndex);

    return INSERT_FAIL_BY_CAPACITY;
}

int Delete(HashTable_t* pHashTable, const char* pKey, size_t(*HashFunction)(const char*))
{
    size_t i, uStartIndex;
    size_t uHash = HashFunction(pKey);
    uStartIndex = uHash % BUCKET_SIZE;

    i = uStartIndex;
    do {
        if (NULL != pHashTable->mpKeyArray[i] && 0 == strcmp(pKey, pHashTable->mpKeyArray[i]))
        {
            free((void*)pHashTable->mpKeyArray[i]);
            pHashTable->mpKeyArray[i] = NULL;

            return DELETE_SUCCESS;
        }
        else if (NULL == pHashTable->mpKeyArray[i])
        {
            return DELETE_FAIL_BY_ABCENT;
        }
    } while (i != uStartIndex);

    return DELETE_FAIL_BY_EMPTY;
}

void DeleteAll(HashTable_t* pHashTable)
{
    size_t i;
    for (i = 0; i < BUCKET_SIZE; ++i)
    {
        if (NULL != pHashTable->mpKeyArray[i])
        {
            free((pHashTable->mpKeyArray[i]));
            pHashTable->mpKeyArray[i] = NULL;
        }
    }
}

void Print(HashTable_t* pHashTable)
{
    size_t i;

    printf("===============\n");
    for (i = 0; i < BUCKET_SIZE; ++i)
    {
        if (NULL == pHashTable->mpKeyArray[i])
        {
            printf("[%zu]: %s\n", i, "NULL");
        }
        else
        {
            printf("[%zu]: %s (%d)\n", i, pHashTable->mpKeyArray[i], pHashTable->mnValueArray[i]);
        }
    }
    printf("===============\n");
}

 

저작자표시 비영리 변경금지

'C > 자료구조와 알고리듬' 카테고리의 다른 글

Chapter 11. 이진 탐색 트리(Binary Search Tree)  (0) 2021.11.21
Chapter 10. 트리(Tree)  (0) 2021.11.19
Chapter 08. 연결 리스트(Linked List)  (0) 2021.11.12
Chapter 07. 큐(Queue)  (0) 2021.11.10
Chapter 06. 스택(Stack)  (2) 2021.11.10

관련글

댓글

티스토리툴바