Hash

  • Hash funciton은 데이터를 다른 형태로 변환해주는 함수
  • 자료구조와 연결하면 강력한 성능을 발휘
  • Hash Table (Insert, Delete, Search) -> Average O(1), Worst O(n)
  • key -> hash function -> h(key) 로 테이블에서 삽입/삭제/탐색
  • 같은 함수 값이 나온 경우 충돌(collision)이라하며 충돌 횟수가 작을수록 좋은 해시 함수라 평가
  • Hash Table은 충돌이 날 경우 데이터들을 해당 h(key)값에 연결리스트로 저장
  • 즉, 해시 테이블의 연산은  충돌 횟수만큼 시간이 걸림. 해당 키값에 충돌된 횟수만큼 쭉 저장되므로. 해시 함수가 충분히 좋으면 O(1)로 수렴, 충돌이 많을 경우 연산 한번에 O(n)시간이 걸릴 수도 있음.
  • 즉 성능은 해시 함수에 좌우됨

Hash 함수만 Data type에 따라 이용 할 수 있게 변경

예시문제)

Hash table은 키를 값에 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. Hash table은 Hash 함수를 사용하여 색인(index, Key)을 버킷(bucket)이나 슬롯(slot)의 배열로 계산한다. 주어진 N개의 key, data쌍을 Hash table에 입력한 후, Q개의 key를 입력 받아 key에 해당하는 data를 각 줄에 출력하시오. (1<=N, Q<=4096) * Key : 최대 64개의 문자열 * Data : 최대 128개의 문자열

Input

1 // 테스트 케이스 수 T 
2 // 입력 데이터 수 N 
abc def //key data 
bcdf abcde 
3 // 검색할 데이터 수 Q 
abc
bcd
bcdf 

Output

def
not find
abcde

Code

#include <iostream>
using namespace std;

#define MAX_KEY 64
#define MAX_DATA 128
#define MAX_TABLE 4096

int idx = 0;

unsigned long myhash(const char *str) {
    return 1;

    unsigned long hash = 5381;
    int c;

    while (c = *str++)
    {
        hash = (((hash << 5) + hash) + c) % MAX_TABLE;
    }

    return hash % MAX_TABLE;
}


struct NODE {
    char key[MAX_KEY + 1];
    char data[MAX_DATA + 1];
    NODE* prev;
}a[10000];


NODE* myalloc() {
    return &a[idx++];
}


NODE* hTable[MAX_TABLE];


void mystrcpy(char* a, char* b) {
    while (*b != '\0') {
        *a = *b;
        a++; b++;
    }
    *a = '\0';
}


bool mystrcmp(char* a, char* b) {
    while (*a != '\0' && *b != '\0') {
        if (*a == *b) {
            a++;
            b++;
        }
        else {
            return false;
        }
    }
    return true;
}


void insert(char* key, char* data) {
    int h = (int)myhash(key);
    NODE* newNode = myalloc();
    mystrcpy(newNode->key, key);
    mystrcpy(newNode->data, data);   
    //prev
    newNode->prev = hTable[h];
    hTable[h] = newNode;
}


void search(char* key) {
    int h = (int)myhash(key);
    for (NODE* pp = hTable[h]; pp != NULL; pp = pp->prev) {
        if (mystrcmp(pp->key, key)) {
            cout << pp->data << endl;
            return;
        }
    }
}


void remove(char* key) {
    int h = (int)myhash(key);
    NODE* prev_node = NULL;
    //all keys must be unique unless it makes bug
    for (NODE* pp = hTable[h]; pp != NULL; pp = pp->prev) {
        if (mystrcmp(pp->key, key)) {
            if (prev_node == NULL) {
                cout << "it's first node " << endl;
                hTable[h] = pp->prev;
            }
            else {
                cout << "it isn't first node" << endl;
                prev_node->prev = pp->prev;
            }
            cnt++;
            return;
        }
        prev_node = pp;
    }
}


int main() {
    
    //init
    idx = 0;

    for (int i = 0; i < MAX_TABLE; ++i) hTable[i] = nullptr;

    int N;
    cin >> N;

    //insert
    for (int i = 0; i < N; ++i) {
        char key[MAX_KEY + 1];
        char data[MAX_DATA + 1];
        cin >> key >> data;
        insert(key, data);
    }

    cout << "START Search" << endl;

    //search
    int Q; 
    cin >> Q;
    for (int i = 0; i < Q; ++i) {
        char key[MAX_KEY + 1];
        cin >> key;
        search(key);
    }


    //remove
    int R;
    cin >> R;
    for (int i = 0; i < R; ++i) {
        char key[MAX_KEY + 1];
        cin >> key;
        remove(key);
    }

    cout << "START RE search" << endl;

    //search
    cin >> Q;
    for (int i = 0; i < Q; ++i) {
        char key[MAX_KEY + 1];
        cin >> key;
        search(key);
    }

    return 0;
}

 

You may also like...