해시

해시(Hash)

- 데이터를 최대한 빠른 속도로 관리하도록 도와주는 자료 구조

- 해시를 사용하면 메모리 공간이 많이 소모되지만 매우 빠른 속도로 데이터를 처리할 수 있음

- 빠르게 데이터에 접근할 수 있다는 점에서 데이터베이스 등의 소프트웨어에서 활용

 

해시 함수 동작 과정

- 특정한 값을 찾고자 할 때는 그 값의 키로 접근할 수 있음

- 일반적으로 해시 함수는 모듈로 연산 등의 수학적 연산으로 이루어져 있으므로 O(1)만에 값에 접근할 수 있음

 

* 특정한 값이 들어왔을 때 그 값에 10을 나눈 나머지 값이 키가 될 수 있도록 했다고 가정

입력 데이터 >  해시 함수(n mod 10)  > 키(Key) | 값(Value)

78 / khon                                              2           | khon01

12 / khon01                                          4           | khon03

55 / khon02                                         5           | khon02

64 / khon03                                         8           | khon

 

해시의 충돌

- 해시 함수의 입력 값으로는 어떠한 값이나 모두 들어갈 수 있지만 해시 함수를 거쳐 생성되는 키의 경우의 수는 한정적이기 때문에 키 중복이 발생할 수 있음

- 해시 테이블에서 키가 중복되는 경우 충돌(Collision)이 발생했다고 표현

- 동일한 데이터 값이 들어갈 경우 충돌

 

생일의 역설

- 무작위의 사람 57명을 한 곳에 모아 놓으면, 2명의 생일이 같을 확률이 99%

- 이를 해싱 과정과 비교하자면 '365로 나눈 나머지'를 키로 이용하는 해시 함수의 경우 입력 데이터가 57개만 되어도 사실상 충돌이 무조건 발생한다고 판단해야 하는 것

 

해싱(Hashing)

- 해싱 알고리즘은 나눗셈 법이 가장 많이 활용됨

- 입력 값을 테이블의 크기로 나눈 나머지를 키로 이용하는 방식

- 테이블의 크기는 소수로 설정하는 것이 효율성이 높음

 

충돌을 처리하는 방법

- 아무리 잘 만들어진 해시 함수라고 해도 충돌이 발생할 수밖에 없음

- 충돌을 처리하는 방법은 다음과 같이 두 가지 유형으로 분류할 수 있음

1. 충돌을 발생시키는 항목을 해시 테이블의 다른 위치에 저장 : 선형 조사법, 이차 조사법 등

2. 해시 테이블의 하나의 버킷에 여러 개의 항목을 저장 : 체이닝 등

 

선형 조사법

- 데이터가 충돌할 경우 그다음 데이터 비어있다면 그곳에 데이터를 넣음

// 선형 조사법 구조체 정의
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define TABLE_SIZE 10007
#define INPUT_SIZE 5000

typedef struct {
    int id;
    char name[20];
} Student;

// 해시 테이블 초기화
void init(Student** hashTable) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        hashTable[i] = NULL;
    }
}

// 해시 테이블 메모리 반환
void destructor(Student** hashTable) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        if (hashTable[i] != NULL) {
            free(hashTable[i]);
        }
    }
}

// 해시 테이블 내 빈 공간을 선형 탐색으로 찾음
int findEmpty(Student** hashTable, int id) {
    int i = id % TABLE_SIZE;
    while (1) {
        if (hashTable[i % TABLE_SIZE] == NULL) {
            return i % TABLE_SIZE;
        }
        i++;
    }
}

// 특정한 ID 값에 매칭되는 데이터를 해시 테이블 내에서 찾음
int searh(Student** hashTable, int id) {
    int i = id % TABLE_SIZE;
    while (1) {
        if (hashTable[i % TABLE_SIZE] == NULL) return -1;
        else if (hashTable[i % TABLE_SIZE]->id == id) return i;
        i++;
    }
}

// 특정한 키 인덱스에 데이터를 삽입
void add(Student** hashTable, Student* input, int key) {
    hashTable[key] = input;
}

// 해시 테이블에서 특정한 키의 데이터를 반환
Student* getValue(Student** hashTable, int key) {
    return hashTable[key];
}

// 선형 조사법 데이터 출력 함수
// 해시 테이블에 존재하는 모든 데이터를 출력
void show(Student** hashTable) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        if (hashTable[i] != NULL) {
            printf("키: [%d] 이름: [%s]\n", i, hashTable[i]->name);
        }
    }
}

int main(void) {
    Student **hashTable;
    hashTable = (Student**)malloc(sizeof(Student) * TABLE_SIZE);
    init(hashTable);
    
    for (int i = 0; i < INPUT_SIZE; i++) {
        Student* student = (Student*)malloc(sizeof(Student));
        student->id = rand() % 1000000;
        sprintf(student->name, "사람%d", student->id);
        if (searh(hashTable, student->id) == -1) { // 중복되는 ID는 존재하지 않도록 함
            int index = findEmpty(hashTable, student->id);
            add(hashTable, student, index);
        }
    }
    
    show(hashTable);
    destructor(hashTable);
    system("pause");
    return 0;
}

 

선형 조사법의 단점

- 충돌이 발생하기 시작하면 유사한 값을 가지는 데이터끼리 서로 밀집되는 집중 결함 문제가 존재

- 메모리를 많이 소모한다면 충돌이 적게 발생하므로 매우 바른 데이터 접근 속도를 가질 수 있음

- 일반적인 경우 해시 테이블의 크기는 한정적이므로 충돌이 최대한 적게 발생하도록 해야 함

 

이차 조사법

- 선형 조사법을 약간 변형한 형태로 키 값을 선택할 때 완전 제곱수를 더해 나가는 방식

- 데이터를 입력하다가 충돌이 발생할 경우 1만큼 떨어진 공간에서 확인을 하고 그 자리에 숫자가 차 있다면 2의 제곱만큼 넘어서 자리를 확인 

- 기존에 발생했던 데이터가 밀집되는 현상이 줄어들기 때문에 해시 충돌이 적게 발생한다는 특징이 있음

 

조사법의 테이블 크기 재설정

- 일반적으로 선형 조사법, 이차 조사법 등의 조사법에서 테이블이 가득 차게 되면 테이블의 크기를 확장하여 계속해서 해시 테이블을 유지할 수 있도록 함

 

체이닝(Chaining)

- 연결 리스트를 활용해 특정한 키를 가지는 항목들을 연결하여 저장함

- 연결 리스트를 사용한다는 점에서 삽입과 삭제가 용이함

- 테이블 크기 재설정 문제는 동적 할당을 통해 해결할 수 있음

- 동적 할당을 위한 추가적인 메모리 공간이 소모된다는 단점이 있음

- 충돌이 발생하더라도 무시하고 키 값에 해당하는 연결 리스트에 계속해서 데이터를 넣음

// 체이닝 구조체 정의
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define TABLE_SIZE 10007
#define INPUT_SIZE 5000

typedef struct {
    int id;
    char name[20];
} Student;


typedef struct {
    Student* data;
    struct Bucket* next;
} Bucket;


// 해시 테이블 초기화
void init(Bucket** hashTable) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        hashTable[i] = NULL;
    }
}

// 해시 테이블 메모리 반환
void destructor(Bucket** hashTable) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        if (hashTable[i] != NULL) {
            free(hashTable[i]);
        }
    }
}

// 체이닝 데이터 탐색 함수
int isExist(Bucket** hashTable, int id) {
    int i = id % TABLE_SIZE;
    if (hashTable[i] == NULL) return 0;
    else {
        Bucket *cur = hashTable[i];
        while (cur != NULL) {
            if (cur->data->id == id) return 1;
            cur = cur->next;
        }
    }
    return 0;
}

// 체이닝 데이터 삽입 함수
// 특정한 키 인덱스에 데이터를 삽입
void add(Bucket** hashTable, Student* input) {
    int i = input->id % TABLE_SIZE;
    if (hashTable[i] == NULL) {
        hashTable[i] = (Bucket*)malloc(sizeof(Bucket));
        hashTable[i]->data = input;
        hashTable[i]->next = NULL;
    }
    else {
        Bucket *cur = (Bucket*)malloc(sizeof(Bucket));
        cur->data = input;
        cur->next = hashTable[i];
        hashTable[i] = cur;
    }
}

// 체이닝 데이터 출력 함수
// 해시 테이블에 존재하는 모든 데이터를 출력
void show(Bucket** hashTable) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        if (hashTable[i] != NULL) {
            Bucket *cur = hashTable[i];
            while (cur != NULL) {
                printf("키: [%d] 이름: [%s]\n", i, cur->data->name);
                cur = cur->next;
            }
        }
    }
}

int main(void) {
    Bucket **hashTable;
    hashTable = (Bucket**)malloc(sizeof(Bucket) * TABLE_SIZE);
    init(hashTable);
    
    for (int i = 0; i < INPUT_SIZE; i++) {
        Student* student = (Student*)malloc(sizeof(Student));
        student->id = rand() % 1000000;
        sprintf(student->name, "사람%d", student->id);
        if (!isExist(hashTable, student->id)) { // 중복되는 ID는 존재하지 않도록 함
            add(hashTable, student);
        }
    }
    show(hashTable);
    destructor(hashTable);
    system("pause");
    return 0;
}