자료구조: Hash

티스토리 뷰

🏋️‍♀️ 기반 다지기/자료구조와 알고리즘

자료구조: Hash

dirmathfl 2021. 1. 10. 15:28

728x90

해시에 대한 개념보다는 C로 해시를 구현하고, data type에 자유롭게 사용할 수 있도록 구현적 측면에서 해시를 다루고자 한다. key-value pair를 구조체에서 별도로 명시하지 않고, entry에 다른 구조체를 포인팅함으로써 더 많은 자료를 다룰 수 있도록 구현하였다.

Hash?

해시는 위의 그림과 같이, key 값을 생성하는 `해시 함수(hash function)`를 통해 배열에 어떤 값이 있는지 즉각적을 찾을 수 있는 자료구조이다. 트리의 경우 한쪽으로 탐색을 하여 범위를 좁혀가면서 탐색을 한다. 하지만 해시의 경우 해시 함수를 통해, 찾고자 하는 값의 key를 즉각적으로 알 수 있으므로 탐색에 매우 효율적인 자료구조이다.

하지만 해시에서도 문제점은 있다. `충돌(Collision)`이 발생하는 경우, 어떤 식으로 처리하느냐에 따라, 효율성이 급격히 달라진다. 다시 말하면, 충돌을 적게 일으키는 해시 함수의 성능에 따라 해당 자료구조의 성능이 좌우된다. 구현에서는 `Jenkins hash function`을 사용하였다.

코드

header

#ifndef HASH_H
#define HASH_H

typedef struct entry {
    struct entry *next;
    char data[0];
} entry_t;

typedef struct {
    int size;
    entry_t **table;
} hash_t;

hash_t *init_hash(unsigned int table_size, int data_size);
void free_hash(hash_t *hash);
void ins_data_in_hash(hash_t *hash, const void *data, const void *key,
            int data_size, int (*compare)(const void *, const void *));
void *get_data_in_hash(hash_t *hash, const void *key, int (*compare)(const void *, const void *));
void del_data_in_hash(hash_t *hash, const void *key, int (*compare)(const void *, const void *));
void print_hash(hash_t *hash, void (*print_item)(const void *));
#endif

entry가 포인팅 하는 값을 하나로 지정하지 않고, `char data[0]`로 선언하였다. 또한, 주요 함수의 인자를 `const void *` 타입으로 선언하여 `data type`에 종속적이지 않도록 구현하였다.

init

hash_t *init_hash(unsigned int table_size, int data_size)
{
    unsigned int i;
    hash_t *hash = NULL;

    /* hash 구조체 할당 */
    if ((hash = (hash_t *)malloc(sizeof(hash_t))) == NULL) {
        //error logging
        return NULL;
    }

    /* hash의 테이블 구조체 할당 */
    if ((hash->table = malloc((sizeof(entry_t) + data_size) * table_size)) == NULL) {
        //error logging
        return NULL;
    }

    for (i = 0; i < table_size; i++) 
         hash->table[i] = NULL;

    hash->size = table_size;

    return hash;
}

`init`를 하기 위해서는 다른 부분은 크게 신경 쓸 필요가 없고, `entry`에 할당하는 구조체 또는 데이터 타입의 크기를 명시하여 타입에 상관없이 공간을 사용할 수 있도록 하여야 한다.

free

static void free_chaining_entry(entry_t *entry)
{
    if (entry->next)
        free_chaning(entry->next);
    free(entry);
}

static void free_all_entry(hash_t *hash)
{
    unsigned int i;

    for (i = 0; i < hash->size; i++) {
        if (hash->table[i] == NULL)
            continue;
		
        free_chaining_entry(hash->table[i]);
    }
}

void free_hash(hash_t *hash)
{
    free_all_entry(hash);
    free(hash->table);
    free(hash);
}

`entry`의 data가 포인팅할 값도 동적 할당으로 구현하였기에, 각 `entry`에 대해 `free`를 진행하여야 한다. 단순히 해시 테이블에 대해서만 `free`를 하게 되면 메모리 누수가 발생한다. 따라서 `free_chaining_entry`와 같이 재귀 호출을 통해 연결된 `entry`들이 있는지 확인하여, 모두 해제하여야 한다.

insert

static int get_hash_key(hash_t *hash, const void *key);
static entry_t *init_entry(const void *data, int data_size);
void ins_data_in_hash(hash_t *hash, const void *data, const void *key,
        int data_size, int (*compare_key)(const void *, const void *))
{
    unsigned int hash_key = 0;
    entry_t *new = NULL;
    entry_t *next = NULL;
    entry_t *last = NULL;

    hash_key = get_hash_key(hash, key);
    next = hash->table[hash_key];

    while (next && next->data && compare_key(next->data, key) < 0) {
        last = next;
        next = next->next;
    }

    /* 이미, 삽입하고자 하는 데이터가 있는 경우 */
    if (next && next->data && compare_key(next->data, key) == 0)
        memcpy(next->data, data, data_size);
    /* 삽입하고자 하는 데이터가 없는 경우 */
    else {
        new = init_entry(data, data_size);

        if (next == hash->table[hash_key]) {
            new->next = next;
            hash->table[hash_key] = new;
        } else if (next == NULL)
            last->next = new;
        else {
            new->next = next;
            last->next = new;
        }
    }
}

현재 `table`에 삽입하고자 하는 값이 존재하는지 여부에 따라, 처리하는 로직이 달라지게 된다. `compare_key`는 다른 함수를 포인팅 하므로 처리하고자 하는 data type에 따라 함수를 별도로 선언하여야 한다.

delete

void del_data_in_hash(hash_t *hash, const void *key, int (*compare_key)(const void *, const void *))
{
    unsigned int hash_key;
    entry_t *entry = NULL;

    hash_key = get_hash_key(hash, key);

    entry = hash->table[hash_key];

    if (!entry)
        return;

    // 인덱스 첫 번째 값이 지우고자 하는 값인 경우
    if (entry->data && compare_key(entry->data, key) == 0) {
        hash->table[hash_key] = NULL;
        free(entry);
        return;
    // 나머지 경우
    } else {
        entry_t *next = entry->next;
        entry_t *last = NULL;

        while (next && next->data && compare_key(next->data, key) != 0) {
            last = next;
            next = next->next;
        }

        if (next == NULL)
            return;

        last->next = next->next;
        free(next);
    }
}

특정 값을 해시 테이블에서 삭제하기 위해서는 테이블의 첫 번째 값과 일치하는 경우는 단순히 삭제하면 된다. 하지만 `chainig`이 된 경우라면, 삭제된 값을 제외하고 나머지 포인팅 되는 부분들을 연결해 주어야 한다.

get_data

void *get_data_in_hash(hash_t *hash, const void *key, int (*compare_key)(const void*, const void *))
{
    unsigned int hash_key = 0;
    entry_t *entry = NULL;

    hash_key = get_hash_key(hash, key);

    entry = hash->table[hash_key];

    while (entry && entry->data && compare_key(entry->data, key) < 0) {
        entry = entry->next;
    }

    if (entry == NULL || entry->data == NULL || compare_key(entry->data, key) != 0) {
        return NULL;
    }

    return entry->data;
}

`key`를 통해 해시 테이블 내에 내가 찾고자 하는 값을 찾는다. 위의 구조체 선언에서 `entry`에 `data`는 다른 구조체 또는 변수를 포인팅 하므로 함수의 반환 값을 통해 `data`에 바로 접근할 수 있다.

hash function

static unsigned int get_hash_key(hash_t *hash, const void *key)
{
    /* Jeckins hash function. 
     * http://en.wikipedia.org/wiki/Jeckins_hash_function
     */
    unsigned int i;
    unsigned int hash_key;
    char *data_key = (char *)key;

    for (hash_key = i = 0; i < strlen(data_key); i++) {
        hash_key += data_key[i], hash_key += (hash_key << 10), hash_key ^= (hash_key >> 6);
    }

    hash_key += (hash_key << 3), hash_key ^= (hash_key >> 11), hash_key += (hash_key << 15);	

    return hash_key % hash->size;
}

`Jeckins hash function`을 그대로 구현하여, 해시 함수로 사용하였다.

전체 코드

#include "common.h"
#include "hash.h"

hash_t *init_hash(unsigned int table_size, int data_size)
{
    unsigned int i;
    hash_t *hash = NULL;

    /* Alloc the hash */
    if ((hash = (hash_t *)malloc(sizeof(hash_t))) == NULL) {
        //error logging
        return NULL;
    }

    /* Alloc pointer to the head nodes. */
    if ((hash->table = malloc((sizeof(entry_t) + data_size) * table_size)) == NULL) {
        //error logging
        return NULL;
    }

    for (i = 0; i < table_size; i++)
        hash->table[i] = NULL;

    hash->size = table_size;

    return hash;
}

static void free_all_entry(hash_t *hash);
void free_hash(hash_t *hash)
{
    free_all_entry(hash);
    free(hash->table);
    free(hash);
}

static unsigned int get_hash_key(hash_t *hash, const void *key);
static entry_t *init_entry(const void *data, int data_size);
void ins_data_in_hash(hash_t *hash, const void *data, const void *key,
        int data_size, int (*compare_key)(const void *, const void *))
{
    unsigned int hash_key = 0;
    entry_t *new = NULL;
    entry_t *next = NULL;
    entry_t *last = NULL;

    hash_key = get_hash_key(hash, key);
    next = hash->table[hash_key];


    while (next && next->data && compare_key(next->data, key) < 0) {
        last = next;
        next = next->next;
    }

    if (next && next->data && compare_key(next->data, key) == 0)
        memcpy(next->data, data, data_size);
    else {
        new = init_entry(data, data_size);

        if (next == hash->table[hash_key]) {
            new->next = next;
            hash->table[hash_key] = new;
        } else if (next == NULL)
            last->next = new;
        else {
           new->next = next;
            last->next = new;
        }
    }
}

void *get_data_in_hash(hash_t *hash, const void *key, int (*compare_key)(const void*, const void *))
{
    unsigned int hash_key = 0;
    entry_t *entry = NULL;

    hash_key = get_hash_key(hash, key);
    entry = hash->table[hash_key];

    while (entry && entry->data && compare_key(entry->data, key) < 0) {
        entry = entry->next;
    }

    if (entry == NULL || entry->data == NULL || compare_key(entry->data, key) != 0) {
        return NULL;
    }

    return entry->data;
}

void del_data_in_hash(hash_t *hash, const void *key, int (*compare_key)(const void *, const void *))
{
    unsigned int  hash_key;
    entry_t *entry = NULL;

    hash_key = get_hash_key(hash, key);

    entry = hash->table[hash_key];

    if (!entry)
        return;

    if (entry->data && compare_key(entry->data, key) == 0) {
        hash->table[hash_key] = NULL;
        free(entry);
        return;
    } else {
        entry_t *next = entry->next;
        entry_t *last = NULL;

        while (next && next->data && compare_key(next->data, key) != 0) {
            last = next;
            next = next->next;
        }

        if (next == NULL)
            return;

        last->next = next->next;
        free(next);
    }
}

static void print_chaining_entry(entry_t *entry, void (*print_data)(const void *));
void print_hash(hash_t *hash, void (*print_data)(const void *))
{
    unsigned int i;
    for (i = 0; i < hash->size; i++) {
        if (hash->table[i] == NULL)
            continue;

        print_chaining_entry(hash->table[i], print_data);
    }
}

/* Private functions */
static unsigned int get_hash_key(hash_t *hash, const void *key)
{
    /* Jeckins hash function. 
     * http://en.wikipedia.org/wiki/Jeckins_hash_function
     */
    unsigned int i;
    unsigned int hash_key;
    char *data_key = (char *)key;

    for (hash_key = i = 0; i < strlen(data_key); i++) {
        hash_key += data_key[i], hash_key += (hash_key << 10), hash_key ^= (hash_key >> 6);
    }

    hash_key += (hash_key << 3), hash_key ^= (hash_key >> 11), hash_key += (hash_key << 15);

    return hash_key % hash->size;
}

static void print_chaining_entry(entry_t *entry, void (*print_data)(const void *))
{
    if (entry->next)
        print_chaining_entry(entry->next, print_data);

    print_data(entry->data);
}

static entry_t *init_entry(const void *data, int data_size)
{
    entry_t *entry = (entry_t *)malloc(sizeof(entry_t) + data_size);

    if (entry == NULL) {
        // error logging
        return NULL;
    }

    entry->next = NULL;
    memcpy(entry->data, data, data_size);

    return entry;
}


static void free_chaining_entry(entry_t *entry)
{
    if (entry->next)
        free_chaining_entry(entry->next);
    free(entry);
}

static void free_all_entry(hash_t *hash)
{
    int i;

    for (i = 0; i < hash->size; i++) {
        if (hash->table[i] == NULL)
            continue;

        free_chaining_entry(hash->table[i]);
    }
}

테스트

#include "common.h"
#include "hash.h"

#define MAX_TABLE_SIZE 10
#define MAX_NAME_LEN 30

typedef struct info {
    char name[MAX_NAME_LEN];
    int age;
} info_t;

void init_info(info_t *temp, const char *name, int age)
{
    memset(temp, 0, sizeof(info_t));
    memcpy(temp->name, name, MAX_NAME_LEN);
    temp->age = age;
}

int compare_name(const void *entry, const void *name)
{
    return strcmp(((info_t *)entry)->name, ((char *)name));
}

void print_info_data(const void *entry)
{
    info_t *info = (info_t *)entry;
    printf("%s, %d\n", info->name, info->age);
}

void ins_info_data(hash_t *hash, info_t *temp)
{
    info_t *info = (info_t *)get_data_in_hash(hash, temp->name, compare_name);
    
    if (!info)
        ins_data_in_hash(hash, temp, temp->name, sizeof(info_t), compare_name);
}

int main()
{
    hash_t *hash = NULL;
    hash = init_hash(MAX_TABLE_SIZE, sizeof(info_t));
    
    info_t temp;
    init_info(&temp, "L", 15);
    ins_info_data(hash, &temp);
    
    init_info(&temp, "B", 18);
    ins_info_data(hash, &temp);

    print_hash(hash, print_info_data);

    free_hash(hash);
}

예제로는 간단하게 테스트 해보았다. 임의로 해시 테이블 하나의 인덱스에 체이닝도 해보고, 여러 경우의 수를 모두 테스트하였는데 이상 없이 동작하였다.

728x90

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

'🏋️‍♀️ 기반 다지기 > 자료구조와 알고리즘' 카테고리의 다른 글

자료구조 : Binary Search Tree (0)	2021.01.17
알고리즘: 정렬 (0)	2020.06.17
알고리즘: DFS와 BFS (0)	2020.06.16
알고리즘: Recursion (0)	2020.06.16
자료구조: Linked List (0)	2020.06.15

글 보관함

최근에 올라온 글

최근에 달린 댓글

CEO

티스토리 뷰