Hash 알고리즘

Hash

데이터는 어떻게 찾을까요?

1. 가장 간단한 방법으로 모든 데이터를 비교해서 찾는 방법

2. 데이터를 정렬하고 Binary search 방식으로 찾는 방법 (nlogn)

3. Hash를 이용해서 데이터를 찾는 방식

이번 글에서는 Hash를 알아봅시다.

Hash의 목적은 데이터의 검색을 빠르게 하기 위한 자료 구조입니다. 데이터를 key를 만들고, key가 같은 데이터만 검색하여 내가 원하는 데이터를 찾는 방식입니다.

 

단점은 데이터의 저장 공간이 많이 필요합니다.

 

Hash를 구현하기 위해선

1. Data를 Key로 변환하는 함수를 구현해야 합니다.

2. Data가 존재하는지 확인하는 함수를 구현해야 합니다.

3. Data를 추가하는 함수를 구현해야 합니다.

4. Data를 삭제하는 함수를 구현해야 합니다.

5. Data를 비교하는 함수를 구현해야 합니다.

 

빈번하게 호출하는 함수는 1과 5입니다.

키는 무엇인가요?

어떤 데이터를 언제 변환하여도 항상 같은 값으로 표현되는 값입니다. (필수 조건)

좋은 성능을 내기 위해선 임의의 어떤 데이터들을 key로 변환 할 때, key가 균등하게 배분 되어야 합니다. (선택 조건)

:임의의 데이터들을 가지고 Key를 만들 때, 어떤 특정한 Key의 빈도가 많거나 적으면 hash 성능에 안 좋은 영향을 줄 수 있습니다.

// 데이터를 이용해서 key를 만들어 내는 방식
const int PN = 23; // 소수입니다. 좀 큰 소수
const int HASH_SIZE = 5;

unsigned int get_key(char str[]) {
	unsigned int key = 0, p = 1;
    for (int i = 0; str[i] != 0; ++i) {
    	key += (str[i] * p);
        p *= PN;
    }
    return (key % HASH_SIZE);
}

그런데 Key 변수에 over-flow가 발생한다면?? => 상관이 없습니다. 어차피 같은 위치에서 같은 값으로 over-flow가 발생하기 때문입니다.

Key 변수 타입을 unsigned로 한 이유는?? => over-flow 발생시 signed로 해버리면 음수가 발생할 수 있으니, 그 것을 방지하기 위함입니다.

구현

#include <stdio.h>
#include <map>
#include <algorithm>
#include "Windows.h"
using namespace std;
 
const int PN = 23;
const int HASH_SIZE = 10000;
 
int table[HASH_SIZE][50];
int hash_size = 0;
char hash_raw[30000][100];
 
char input[30000][100];
map<char*, int> test;
 
unsigned int get_key(char str[]) {
    unsigned int key = 0, p = 1;
 
    for (int i = 0; str[i] != 0; ++i) {
        key += (str[i] * p);
        p *= PN;
    }
 
    return (key % HASH_SIZE);
}
 
int my_strcamp(char a[], char b[]) {
    int i = 0, j = 0;
    while (a[i]) {
        if (a[i++] != b[j++]) {
            --i, --j;
            break;
        }
    }
    return (a[i] - b[j]);
}
 
int contain(char str[]) {
    unsigned int key = get_key(str);
    int size = table[key][0];
    for (int i = 1; i <= size; ++i) {
        int pos = table[key][i];
        if (my_strcamp(hash_raw[pos], str) == 0) {
            return pos;
        }
    }
    return -1;
}
 
void add(char str[]) {
    int len = 0;
    for (len = 0; str[len] != 0; ++len) {
        hash_raw[hash_size][len] = str[len];
    }
    hash_raw[hash_size][len] = 0;
 
    unsigned int key = get_key(str);
    int& size = table[key][0];
    table[key][++size] = hash_size;
 
    ++hash_size;
}
 
bool remove(char str[]) {
    unsigned int key = get_key(str);
    int& size = table[key][0];
    for (int i = 1; i <= size; ++i) {
        int pos = table[key][i];
        if (my_strcamp(hash_raw[pos], str) == 0) {
            for (int j = i + 1; j <= size; ++j) {
                table[key][j - 1] = table[key][j];
            }
            --size;
            return true;
        }
    }
    return false;
}
 
int make_int(int min, int max) {
    return (rand() % (max - min)) + min;
}
 
char make_char() {
    int val = rand() % 52;
    if (val < 26) {
        return static_cast<char>('a' + val);
    }
    return static_cast<char>('A' + val - 26);
}
 
int main()
{
    for (int i = 0; i < 30000; ++i) {
        int len = make_int(10, 100);
        for (int j = 0; j < len; ++j) {
            input[i][j] = make_char();
        }
        input[i][len] = 0;
 
        if (contain(input[i]) == -1) {
            add(input[i]);
        }
        test[input[i]] = i;
 
 
        if (i > 20000) {
            int cmd = make_int(0, 5);
            int index = make_int(0, i);
            if (cmd == 0) {
                if (contain(input[index]) != -1) {
                    remove(input[index]);
                }
 
                test.erase(input[index]);
            }
            if (cmd == 1) {
                int my_pos = contain(input[index]);
                map<char*, int>::iterator iter = test.find(input[index]);
                int stl_pos = -1;
                if (iter != test.end()) {
                    stl_pos = iter->second;
                }
 
                if (my_pos != stl_pos) {
                    printf("find error!!!\n");
                }
            }
        }
    }
 
    int my_hash_size = 0;
    for (int i = 0; i < HASH_SIZE; ++i) {
        my_hash_size += table[i][0];
    }
 
    if (my_hash_size != test.size()) {
        printf("remove error!!!\n");
    }
 
    return 0;
}