[포프 tv 복습] C 자료구조 기초

자료구조 기초

---

자료구조란?

- 컴퓨터에서 여러 자료들을 조직적, 체계적으로 저장하는 방법
- 보통 동일한 자료형을 여럿 저장하는 ㅜㄱ조를 의미
- 자료구조에 따라 요소들 사이의 관계를 정의하는 규칙이 있음
- 다음 요인에 따라 상황마다 보다 효율적인 자료구조가 존재
    - 데이터에 접근하는 빈도
    - 데이터에 접근하는 방법(ex. 삽입, 검색, 읽기, 지우기 등)

자료구조의 효율성

- 효율성은 주로 시간 복잡도를 말함
- 공간 복잡도를 포함하는 경우도 있음
- 따라서 주로 Big-O 표기법을 사용
- 보통 효율성을 논할 때는 하드웨어 최적화를 고려 안 한 이론이 전부
    - 적은 용량의 데이터는 그렇지 않을 수 있음

---

배열

• 메모리 한 덩어리로 표현 가능한 가장 간단한 자료구조
• 여러 자료들을 그 메모리 덩어리 안에 줄줄이 세워놓은 구조
• 각 자료는 색인으로 접근
  • 연속된 메모리나 각 요소의 실제 메모리 상의 위치를 쉽게 찾을 수 있음

배열의 삽입 살펴보기 - O(n)

enum{MAX_NUMS = 8};
int s_nums[MAX_NUMS];
size_t s_num_count = 0;

void insert_at(size_t index, int n)
{
    size_t i;

    assert(index <= s_num_count);
    assert(s_num_count <= MAX_NUMS);

    for(i = s_num_count; i>index; --i){
        s_nums[i] = s_nums[i-1];
    }

    s_nums[index] = n;
    ++s_num_count;
}

배열의 삽입

• 배열 제일 뒤에 넣으면 간단히 삽입하고 끝
• 그 외의 경우는 삽입하려는 위치의 요소부터 마지막 요소를 모두 뒤로 한 칸씩 민 뒤에 삽입
• 시간 복잡도는 O(n)

배열의 삭제 예

enum{MAX_NUMS = 8};
int s_nums[MAX_NUMS];
size_t s_num_count = 0;

void remove_at(size_t index)
{
    size_t i;

    assert(index < s_num_count);

    --s_num_count;

    for(i = index; i<s_num_count; ++i){
        s_nums[i] = s_nums[i+1];
    }
}

배열의 삭제

• 삭제하는 색인을 개준으로 그 뒤의 값들을 한 칸씩 앞으로 땡김
• 시간 복잡도 : O(n)

배열의 검색 예

enum{MAX_NUMS = 8};
enum{INVALID_INDEX = -1};

int s_nums[MAX_NUMS];
size_t s_num_count = 0;

size_t find_index(int n)
{
    size_t i;

    for(i = 0; i<s_num_count; ++i){
        if(s_nums[i] == n){
            return i;
        }
    }
    return INVALID_IDNEX;
}

배열의 검색

• 배열 속 요소들을 처음부터 차례대로 방문하며 찾고자 하는 값이 있는지 확인
  • 있으면, 해당 색인을 반환
  • 없으면, -1을 반환
• 시간 복잡도 : O(n)

배열의 접근

• 이미 색인을 알고 있다면 곧바로 접근 가능
• 시간 복잡도 : O(1)

---

스택

• 자료의 삽입과 삭제에 대한 규칙이 있는 자료구조 중 하나
• 가장 먼저 자료구조에 삽입된 데이터가 제일 마지막에 삭제됨
• 선입후출(FILO) or 후입선출(LIFO)

스택의 구현

• 배열로 쉽게 가능
• 그냥 배열의 앞에서부터 데이터를 추가
• 마지막 요소의 위치를 스택의 젤 위라 생각하면 됨

스택의 삽입 예

enum {MAX_NUMS = 8};

int s_nums[MAX_NUMS];
size_t s_num_count = 0;

void push(int n)
{
    assert(s_num_count < MAX_NUMS);
    s_nums[s_num_count++] = n;
}

스택의 삽입

• 보통 push 라고 표현
• 시간 복잡도 : O(1)

스택의 제거 예

enum {TRUE = 1, FALSE = 0};
enum {MAX_NUMS = 8};

int s_nums[MAX_NUMS];
size_t s_num_count = 0;

int is_empty(void)
{
    return (s_num_count == 0);
}

void pop(void)
{
    assert(is_empty() == FALSE);
    return s_nums[--s_num_count];
}

스택의 제거

• pop 이라고 함
• 시간 복잡도 : O(1)

스택의 검색

• 시간 복잡도 : O(n)
• 젤 위부터 찾을 때까지 뒤져야 함
• 보통 push와 pop만 허용하므로 임의의 요소에 접근할 방법이 없음
• 모든 요소를 다 제거했다가 다시 원상복구해야 함
• 제거에 O(n) + 복구에 O(n)이 필요
• 따라서 O(2n)이지만 이건 그냥 O(n)이라고 말함

스택의 용도

• 일련의 자료들의 순서를 뒤집는데 유용
• 왜 뒤집지?
  • 현재 데이터 순서대로 연산하는 것이 컴퓨터에 적합하지 않은 경우

---

큐

• 가장 먼저 자료구조에 삽입(enque)된 데이터가 제일 처음에 삭제(dequeue)됨
• 선입선출(FIFO)이라고 함
• 스택과는 삭제 방향이 다름에 주목!
• 언제나 젤 처음에 있는 자료만 접근 가능

큐의 비효율적인 구현

• 그냥 배열을 사용하면 큐를 구현할 수는 있다
• enqueue하면 그냥 제일 뒤에 추가 O(1)
• dequeue하면 그냥 제일 앞에서 삭제 O(n)
• 하지만, 앞에서 큐의 삭제도 O(1)이라 했는데?

큐의 삭제를 O(1)으로 만드려면...

• 내부적으로 배열을 사용하되 원형 버퍼의 개념을 이용하면 가능
  • 어디든 시작과 끝이 될 수 있음

큐의 삽입 예

enum {MAX_NUMS = 8};

int s_nums[MAX_NUMS];
size_t s_front = 0;
size_t s_back = 0;
size_t s_num_count = 0;

void enque(int n)
{
    assert(s_num_count < MAX_NUMS);

    s_nums[s_back] = n;

    s_back = (s_back + 1) % MAX_NUMS;

    ++s_num_count;
}

큐의 삽입

• 보통 enqueue라고 표현
• 시간 복잡도 : O(1)

큐의 삭제 예

int is_empty(void)
{
    return (s_num_count == 0);
}

int dequeue(void)
{
    int ret;

    assert(is_empty() == FALSE);

    ret = s_nums[s_front];

    --s_num_count;
    s_front = (s_front + 1) % MAX_NUMS;

    return ret;
}

큐의 제거

• dequeue라고 표현
• 시간 복잡도 : O(1)

큐의 검색

• 시간 복잡도 : O(n)

큐의 용도

• 현실 세계에서 대기줄이 필요한 경우 다 적용 가능
• 데이터 유입 속도가 데이터 소모 속도보다 빠른 경우
• 데이터 제공자의 수가 데이터 소비자의 수와 다른 경우
  • ex. multi threading
• 입출력 스트림 버퍼도 같은 개념

---

연결 리스트

• 여태까지 본 자료구조들은 메모리에서 연속된 저장 방법에 기초
• 연결 리스트는 그런 제약을 깸
• 자료들이 메모리에 산재해 있음
  • 연결 리스트의 각 자료를 노드라고 부름
  • 동적 메모리 할당으로 필요에 따라 각 노드를 할당
• 노드 사이의 선후 관계를 별도로 지정
  • 어떻게? 다음에 오는 노드의 메모리 주소를 기억
  • 어디에? 노드에 오는 포인터 벼수에
  • 제일 마지막 노드는 다음에 올 노드가 없으니 널 포인터

연결 리스트는 어려울 수 있는 자료구조

• 연결 리스트는 매우 훌륭한 면접 문제
  • 메모리 관리 능력
  • 이중 포인터 사용 능력

연결 리스트의 삽입

• 이미 삽입할 위치를 알면 O(1)

연결 리스트의 제거

• 이미 제거할 위치를 알면 O(1)

연결 리스트의 검색

• O(n)
• 젤 첫 노드부터 찾을 때까지 뒤져야 함
  • 보통, 이 노드를 헤드라고 부름
• 색인으로 접근 불가능
• 이렇게 찾은 뒤에 삽입을 하면 O(1)이 되는 것

연결 리스트 전체를 출력하는 코드 예

typedef struct node {
    int value;
    node_t* next;
} node_t;

void print_node(const node_t* head)
{
    node_t* p;

    p = head;
    while(p != NULL){
        // 출력
        p = p->next;
    }
}

헤드 노드

• 연결 리스트의 첫 번째 노드를 가리키는 포인터
• 처음 시작할 때 값은 NULL
  • 여기다 새로운 노드를 동적 할당해서 대입해줄 것임

    node_t* head = NULL;

해제코드

void destroy(node_t* head)
{
    node_t* p = head;

    whlie(p != NULL){
        node_t* next = p->next;
        free(p);
        p = next;
    }
}

node_t* head = NULL;
// 생략
destroy(head);
head = NULL;

삽입코드

맨 앞에 삽입하는 코드 살펴보기

void insert_front(node_t** phead, int n)
{
    node_t* new_node;

    new_node = malloc(sizeof(node_t));
    new_node->value = n;

    new_node->next = *phead;
    *phead = new_node;    
}


node_t* head = NULL;

insert_front(&head, 3);
insert_front(&head, 5);
insert_front(&head, 2);
insert_front(&head, 0);

destroy(head);
head = NULL;

오름차순으로 삽입하는 코드

void insert_front(node_t** phead, int n)
{
    node_t** pp;
    node_t* new_node;

    new_node = malloc(sizeof(node_t));
    new_node->value = n;

    pp = phead;
    while(*pp != NULL){
        if((*pp)->value >= n){
            break;
        }

        pp = &(*pp)->next;
    }
    new_node->next = *pp;
    *pp = new_node;
}


node_t* head = NULL;

insert_front(&head, 3);
insert_front(&head, 5);
insert_front(&head, 2);
insert_front(&head, 0);

destroy(head);
head = NULL;

노드 삭제

void remove(node_t** phead, int n)
{
    node_t** pp;

    pp = phead;
    while(*pp != NULL){
        if((*pp)->value == n){
            node_t* tmp = *pp;
            *pp = (*pp)->next;
            free(tmp);
            break;
        }

        pp = &(*pp)->next;
    }    
}

int main(void)
{
    node_t* head = NULL;

    // 리스트 순서 : 2 -> 3 -> 5 

    remove(&head, 2);
    remove(&head, 5);

    destroy(head);
    head = NULL;
}

연결 리스트의 용도

• 스택/큐와 같은 특성(삽입/삭제 방향) 때문에 쓰는 자료구조는 아님

• 오히려 길이를 자유롭게 늘리거나 줄일 수 있기에 배열의 한계를 넘으려고 사용하던 자료구조

• 즉, 최대 길이를 미리 특정할 수 없고 삽입/삭제가 빈번할 경우 사용

• 오늘날 어플맄이션 프로그램에서 사용 빈도는 많이 줄음

• 기본적으로 동적 할당 배열을 더 흔히 사용

  • C#에서 list도 연결 리스트가 아니라 동적 할당 배열임
  • 최신 하드웨어의 특징 상 배열이 보장하는 훌륭한 메모리 지역성(인접한 메모리 사용)이 성능에 유리한 경우가 많기 때문

• 하지만 커널 모드 프로그래밍(예: 드라이버)에서는 여전히 많이 사용

  • 메모리의 지역성을 해치지 않으면서도 충분히 큰 메모리(예: 4KB)를 미리 할당
  • 필요에 따라 그 메모리를 쪼개 연결 리스트의 노드로 사용(예: 메모리 풀)

• 참고로 배열 다음으로 많이 사용하는 자료형은 해시 맵

  참고하면 좋은 것들
  • 단일 연결 리스트
    • 살펴본 연결 리스트의 형태
    • 다음 노드를 가리키는 포인터만 저장

• 그 전의 노드를 가리키는 포인터도 저장하는 이중 연결 리스트도 있음

• 이중 연결 리스트는 보통 head 외에 tail 포인터 변수도 가지고 있음

---

해시 테이블

• 검색, 삽입, 삭제의 평균 시간 복잡도가 O(1)
• O(1)이 가능하려면 어떤 메모리 주소에 어떤 데이터가 저장되어 있는지 한 방에 알 수 있어야 함

무작위로 뽑은 수 10개를 저장해보자

방법 1. 입력 값의 최댓값을 배열의 크기로
- 입력 값은 총 10개 뿐
- 입력 값이 꽤 클 수 있음

• 우리가 만들어야 하는 것
  • 입력: 10개의 중복이 없는 수
  • 출력: 범위가 0~9인 배열의 색인
• 즉, 자료(입력)->색인(출력)으로 바꾸는 함수
• 단, 출력 값을 찾을 때, 반복문 없이 O(1)이어야 함

방법 2. 입력값 % 10으로 색인 만들기
- 동일한 색인 위치에 들어가는 애들이 생긴다
방법 3. 배열의 크기를 두 배로
- 겹치는 색인이 아까볻다는 덜 생기나 여전히 존재
방법 3의 보완. 가장 좋은 방법 -> 소수도 사용
- 흔히 다음과 같이 하는 게 좋다고 말함
1. 배열의 크기는 최소 2배
2. 크기에는 소수를 사용
- 소수로 나눠야 동일한 색인이 안 나올 가능성이 제일 높음
- 그래도 중복이 없을 순 없다!

중복 색인 문제의 해결

• 나머지 연산으로 구한 색인 위치 이후에 빈 공간을 찾아 저장
• 즉, 색인을 1씩 증가해가며 빈 색인 위치를 찾아 거기에 저장
• 따라서, 더 이상 불 값(1,0)이 아니라 실제 값을 저장해야 함
• 따라서, 배열에서 비어있는 위치를 알 수 있어야 함
  • 방법 1: 불 배열을 만들어서 사용 여부를 나타냄
  • 방법 2: 어떤 특정한 값을 저장해서 비어있다는 사실을 표시
    • 보통 유효하지 않은 값(ex. INT_MIN)을 사용
  • 우리는 방법 2를 사용

배열을 사용하는 해시 테이블 예

#include <limits.h>

#define TRUE (1)
#define FALSE (0)
#define BUCKET_SIZE (23)
int s_numbers[BUCKET_SIZE];

void init_hashtable(void)
{
    size_t i;

    for(i=0; i<BUCKET_SIZE; ++i){
        s_sumbers[i] = INT_MIN;
    }
}

int has_value(int value)
{
    int i;
    int start_index;

    start_index = value % BUCKET_SIZE;
    if(start_index < 0){
        start_index += BUCKET_SIZE;
    }    

    i = start_index;
    do{
        if(s_numbers[i] == value){
            return TRUE;
        }
        else if(s_numbers[i] == INT_MIN){
            return FALSE;
        }

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

    return FALSE;
}

int add(int value)
{
    int i;
    int start_index;

    start_index = value % BUCKET_SIZE;
    if(start_index < 0){
        start_index += BUCKET_SIZE;
    }    

    i = start_index;
    do{
        if(s_numbers[i] == value || s_numbers[i] == INT_MIN){
            s_numbers[i] = value;
            return TRUE;
        }

        i = (i+1) % BUCKET_SIZE;

    } while(i != start_index);

    return FALSE;
}

이게 바로 해시 테이블

• 색인 중복이 없으면, 읽는 것도 쓰는 것도 다 O(1)
• 색인 중복이 있으면, 최악의 경우 O(N)

또 다른 방법 : 연결 리스트를 사용

• 배열 안의 각 요소에 연결 리스트를 저장
• 여전히 색인이 겹치는 경우는 있음
  • 그래도 O(N)이 되는 경우가 앞의 방법보다 적음
  • O 표기상 여전히 O(N)

해시 값

• 어떤 데이터를 해시 함수에 넣어서 나온 결과

해시 함수

• 임의의 크기를 가진 데이터를 '고정 크기'의 값에 대응하게 하는 함수
• 함수니까 입력 값이 같으면 출력 값은 언제나 같다
• 입력 값이 달라도 출력 값이 같을 수 있다

해시 충돌(hash collision)

• 입력 값이 다른데 출력 값이 같은 경우
• 물론, 이런 일은 없을 수록 좋음
• 따라서, 출력 값으로부터 입력 값을 찾을 수 있다는 보장이 없다

좀 더 자세히 설명하는 해시 값

• 어떤 데이터를 대표하는 값 하나를 내놓으라고 함
• 이렇게 해서 받은 값이 해시 값
  • 그래서 영어에서는 ID라고 함
• 앞의 예에선 입력 값 그 자체를 해시 값이라 볼 수도 있음
• 그 해시 값을 정해진 배열 안에 꾸겨 넣으려고 % 연산을 한 것일 뿐

해시 테이블에 문자열 저장하기

• 우리가 할 일 : 문자열을 배열 색인으로 변환
• 아까 사용한 연산자 % 는 문자열에 사용 불가
• 문자열을 정수형으로 변환하는 해시 함수가 있어야 함
• 문자열의 각 요소는 어짜피 아스키 코드 = 정수 값
• 정수 값들이 줄줄이 서 있는 걸 잘 합치면 될 것 같음

잘 쓰이지 않는 해시 함수 예

static int hash_function(const char* str)
{
    int code = 0;
    const char* c = str;
    while(*c != '\0'){
        code += *c++;
    }

    return code;
}

색인을 구하면 테이블에 저장이 가능

int add(const char* value, int (*hash_func)(const char*));

add("Teemo", hash_function);
add("Hana", hash_function);

하지만 O(문자열 길이)

• O(1)이 아님
• 해시 함수가 문자열 길이만큼 반복문을 도니 O(문자열 길이)

정말 O(1)으로 만들고 싶다면?

• 해시 함수를 한 번만 호출하고 그 결과를 기억해둠

  int hash_id = hash_function(문자열);

• 필요할 때마다 이 변수로 해시 테이블 함수를 호출

  add(hash_id, data);

• 이제 hash_id로부터 저장할 위치의 색인을 O(1)로 구할 수 있다!

  // add() 함수 내부
  //...
  int start_index = hash_id % 23;
  //...

지금까지 본 건 엄밀히 말하면 해시 세트

• 즉, 집합 내 어떤 데이터를 중복 없이 저장한 게 전부
• 저장할 위치를 찾으려고 해시 함수를 썼을 뿐

일반적인 해시 테이블의 형태

• 어떤 키에 대응하는 어떤 값을 같이 저장
• 이런 형태를 보통 해시 테이블(엄밀히 말하면 해시 맵)이라 함
  • C# 등의 언어에서 dictionaty가 바로 이것
• key : 데이터의 위치를 의미하는 데이터
  • 꼭 정수가 아니어도 됨. 문자열도 가능. 구조체도 가능
• value : 실제 저장하는 데이터
• 키를 가지고 그 위치에 가서 자물쇠를 열면 데이터가 나온다는 의미

해시 테이블에서도 충돌이 발생

• 두 가지 문제
  1. 해시 충돌 : 키가 다른데 같은 해시 값이 나옴
  2. 색인 충돌 : 해시 값이 다른데 같은 색인이 나옴
• 두 번째 문제는 이미 해결한 문제

해시 충돌 문제를 해결해야 하나요?

• 해시 충돌 문제는 사실 해결 안 해도 되긴 함
• 그냥 색인 충돌 문제의 해법으로 같이 풀림

만약 해시 충돌을 방지할 수 있다면?

• char*를 복사해서 키로 저장할 이유가 없음
• 해시 값인 정수형(int)만 저장해도 됨
• char* 저장하려고 동적 메모리 할당 안 해도 됨
  • 동적 메모리 할당은 느림. 안 할 수 있다면 이득
• 훌륭한 해시 함수가 있다면 가능

훌륭한 해시 함수란?

• 필수 : 어떤 경우에도 고정된 크기의 값으로 변환 가능
  1. 어떤 자료형이든
  2. 데이터의 길이와 상관 없이
• 해시 충돌이 거의 없음
• 따라서, 충돌이 덜 나는 해시 함수가 좋음

간단하고 나쁘지 않은 해시 함수 : 65599

size_t hash_65599(const char* string, size_t len)
{
    size_t i;
    size_t hash;

    hash = 0;
    for(i = 0; i < len; ++i){
        hash = 65599 * hash + string[i];
    }

    return hash ^ (hash >> 16);
}

완전히 충돌을 없앨 수 있을까?

• 기술적으로는 안 됨
• 허나 특정 조건 하에서는 해시 충돌을 확실히 방지 가능
• 그런 조건이 생각보다 많음
• 이게 가능하면 키 배열에 문자열 대신 정수만 저장해도 됨
  • char* 동적 메모리 할당이 사라짐
  • 해시 테이블에 추가하는 함수를 호출할 때 키 대신 해시 값을 바로 사용

    add(hash_key, value);

해시 충돌을 완벽히 방지할 수 있는 조건이란?

• 고성능을 요하는 업계에서 많이 쓰는 방법

1. 실행 중에 해시 테이블에 저장될 수 있는 데이터를 모두 알고 잇음
   • 예 : 미리 만들어 놓은 데이터 파일 읽기
   • 유저로부터 받는 입력이 아니라는 이야기
2. 개발 도중에 해시 충돌이 없다는 걸 확인하고 보장할 수 있음
   • 키 저장 단계를 없애도 됨

충돌까지 고려한 해시 맵 예

int add(const char* key, int value, size_t (*hash_func)(const char*, size_t))
{
    size_t i;
    size_t start_index;
    size_t hash_id;

    hash_id = hash_func(key, strlen(key));
    start_index = hash_id % BUCKET_SIZE;
    i = start_index;

    do{
        if(s_keys[i] == NULL){
            // 새 키-값을 삽입
            return TRUE;
        }

        if(strcmp(s_keys[i], key) == 0){
            return TRUE;
        }
        i = (i + 1) % BUCKET_SIZE;
    }while(i != start_index);
    return FALSE;
}

충돌이 없을 때 해시 맵 예

int add_fast(size_t hash_key, const char* value)
{
    size_t i;
    size_t start_index;

    start_index = hash_key % BUCKET_SIZE;
    i = start_index;

    do{
        if(s_keys[i] == INT_MIN){
            // 새 키-값을 삽입
            return TRUE;
        }

        if(s_keys[i] == hash_key){
            return TRUE;
        }

        i = (i + 1) % BUCKET_SIZE;

    }while(i != start_index);

    return FALSE;
}

다른 자료형은?

• 그냥 거저 먹으면 됨
• 문자열은 char*
• 어떤 데이터도 char 배열로 표현 가능
  • 즉, 가장 범용적인 데이터
• 아래와 같은 함수 하나만 있으면 끝

  size_t hash_function(const char* bytes, size_t length)

• 단, 저장하려는 데이터에 걸맞는 해시 함수를 찾아 사용할 것

베스트 프랙티스 : 언제 어떤 자료구조를 쓸까

• 기본적으로 배열
  • 가장 간단함
  • 캐시 메모리 덕분에 O 표기법에 상관 없이 성능이 가장 빠른 경우가 많음
• 빈번한 데이터 삽입 또는 삭제를 해야 한다면?
  • 연결 리스트
• 다음과 같은 경우는 해시 기반 자료 구조들
  • 데이터 양이 많은데 검색을 자주 해야 함
  • 배열에 넣기 힘든 데이터(ex. 연속적, 규칙적인 색인이 나올 수 없는 경우)

여러 데이터형과 해시 함수

hash_function.c

#include <stddef.h>
#include "hash_function.h"

size_t hash_int(int value)
{
    return value;
}

size_t hash_float(float value)
{
    return *((size_t*)&value);
}

size_t hash_data(const void* data, size_t length)
{
    const char* p;
    size_t i;
    size_t hash;

    p = data;
    hash = 0;
    for(i = 0; i<length; ++i){
        hash = 65599 * hash + *p++;
    }

    return hash ^ (hash >> 16);
}

main.c

#include <stdio.h>
#include <string.h>

#include "hash_function.h"

typedef struct{
    unsigned char age;
    unsigned int id;
    char name[64];
} employee_t;

int main(void)
{
    employee_t person;
    size_t hash;
    float fvalue;

    hash = hash_int(10);
    printf("int        %u\n", hash);

    hash = hash_int(-10);
    printf("int        %u\n", hash);

    hash = hash_int('A');
    printf("char    %u\n", hash);

    hash = hash_float(3.2f);
    printf("flaot    %u\n", hash);

    hash = hash_data("Pope Kim", strlen("Pope Kim"));
    printf("string    %u\n", hash);

    fvalue = 3.2f;
    hash = hash_data(&fvalue, sizeof(float));
    printf("float    %u\n", hash);

    memset(&person, 0, sizeof(employee_t));
    person.age = 23;
    person.id = 183213;
    strcpy(person.name, "Pope Kim");

    hash = hash_data(&person, sizeof(employee_t));
    printf("struct    %u\n", hash);

    return 0;
}