[알고리즘] ep4++) 개방주소법 구현(선형 조사, 이중 해싱)

문제1) 크기 M인 해시테이블에 n개의 키 값을 입력받아 저장하고, 개방주소법 중 선형조사법을 이용하여 충돌을 처리하는 해시테이블 프로그램을 작성하시오.

 

[구현 조건]

- 해시테이블은 크기가 M인 배열로 동적 할당한다.
- n은 M보다 작은 자연수로 최대 삽입 개수다.
- 입력 키는 중복이 없는 6자리 또는 8자리의 임의의 자연수(학번)다.

- 키 x에 대한 해시함수 h(x) = x % M 을 사용한다.
- 저장된 키 값이 없는 빈 버켓은 0으로 처리한다.

 

[입력]

- 해시테이블의 크기 M과 입력 데이터의 크기 n을 입력받는다.

- 삽입(i), 탐색(s) 명령어를 순서에 상관없이 반복하여 입력받는다.

i <x> : 키 x를 해시테이블에 삽입

s <x> : 키 x가 해시테이블에 존재하는지 탐색

e : 프로그램 종료

 

[출력]

- 키를 삽입하였을 때, 저장된 주소(배열 인덱스)를 인쇄한다.

- 삽입할 때 충돌이 일어나면 선형조사법에 의해 다음 셀로 이동하여 충돌 검사를 계속한다. 충돌 횟수만큼 C를 인쇄한 후, 삽입에 성공한 주소를 인쇄한다.

- 탐색한 키가 테이블에 존재할 경우, 키가 저장된 주소와 값을 인쇄한다(없을 경우 –1을 인쇄한다).

 

test case

 

 

 

(전체코드)

// 개방주소법 - 선형 조사
#include <stdio.h>
#include <stdlib.h>

int* g_hashtable;
int g_M;
int g_n; // 최대 삽입 키 개수

void initHashtable();
int hashFunction(int key);
void insertKey(int key);
void searchKey(int key);

int main() {
    char cmd;
    int key; // 중복이 없는 6자리 or 8자리 학번

    scanf("%d %d", &g_M, &g_n);
    initHashtable();
    while (1) {
        scanf(" %c", &cmd);
        if (cmd == 'i') {
            scanf("%d", &key);
            insertKey(key);
        } 
        else if (cmd == 's') {
            scanf("%d", &key);
            searchKey(key);
        } 
        else if (cmd == 'e') {
            free(g_hashtable);
            return 0;
        }
    }
}

void initHashtable() {
    g_hashtable = (int*)malloc(g_M * sizeof(int));
    for (int i = 0; i < g_M; i++) {
        g_hashtable[i] = 0; // 빈 버켓은 0으로 초기화
    }
}

int hashFunction(int key) {
    return key % g_M;
}

void insertKey(int key) {
    int idx = hashFunction(key); // 해시값을 계산
    int originalIdx = idx;
    int collisionCnt = 0;
    while (g_hashtable[idx] != 0) { // 충돌이 발생하는 동안 반복
        idx = (idx + 1) % g_M;
        collisionCnt++;
        if (idx == originalIdx) { // 한 바퀴를 다 돌았을 경우
            printf("Hash table is full\n");
            return;
        }
    }
    g_hashtable[idx] = key;

    for (int i = 0; i < collisionCnt; i++) {
        printf("C");
    }
    printf("%d\n", idx);
}

void searchKey(int key) {
    int idx = hashFunction(key); // 해시값을 계산
    int originalIdx = idx;
    while (g_hashtable[idx] != 0) { // 충돌이 발생하는 동안 반복
        if (g_hashtable[idx] == key) {
            printf("%d %d\n", idx, key);
            return;
        }
        
        idx = (idx + 1) % g_M;
        if (idx == originalIdx) { // 한 바퀴를 다 돌았을 경우
            printf("-1\n"); // 탐색 결과 없음
            return;
        }
    }
    printf("-1\n");
}

/*
7 3
i 17011112
i 17012345
i 17012687
s 17011111
e

13 10
i 16110243
i 17011111
i 17012331
i 17012354
i 17013672
i 16012342
s 17012354
i 15013986
i 102067
i 113478
i 14012322
s 16110243
e
*/

 

 

 

 

 

문제2) 문제1 에서의 충돌처리 방법을 이중해싱으로 변경하시오.

 

[구현 조건]

- 해시테이블은 크기가 M인 배열로 동적 할당한다(종료 시 해제).

- n은 M보다 작은 자연수로 최대 삽입 개수다.

- 입력 키는 중복이 없는 2자리 이상의 자연수다.

- 키 x에 대한 첫 번째 해시함수 h(x) = x % M, 두 번째 해시함수 h‘(x) = q – (x % q) 를 사용한다. q는 M보다 조금 작은 소수로 입력으로 주어진다.

- 저장된 키가 없는 빈 버켓은 0으로 처리한다.

 

[입력]

- M, n, q를 입력받는다.

- 삽입(i), 탐색(s), 출력(p) 명령어를 순서에 상관없이 반복하여 입력받는다.

i <x> : 키 x를 입력받아 해시테이블에 삽입

s <x> : 키 x가 해시테이블에 존재하는지 탐색

p : 현재의 해시테이블 인쇄

e : 해시테이블 인쇄 후 프로그램 종료

 

[출력]

- 키를 삽입하였을 때, 저장된 주소(배열 인덱스)를 인쇄한다.

- 삽입할 때 충돌이 일어나면 두 번째 해시함수로부터 얻은 셀로 이동하여 충돌 검사를 계속한다. 충돌 횟수만큼 C를 인쇄한 후, 삽입에 성공한 주소를 인쇄한다.

- 탐색한 키가 테이블에 존재할 경우, 키가 저장된 주소와 값을 인쇄한다(없을 경우 –1을 인쇄한다).

 

test case

 

 

 

(전체코드)

// 개방주소법 - 이중 해싱
#include <stdio.h>
#include <stdlib.h>

int* g_hashtable;
int g_M;
int g_n; // 최대 삽입 키 개수
int g_q; // 두 번째 해시함수 h‘(x) = g_q – (x % g_q)

void initHashtable();
int hashFunction(int key);
int doubleHashFunction(int key);
void insertKey(int key);
void searchKey(int key);
void printHashtable();

int main() {
    char cmd;
    int key; // 중복이 없는 2자리 이상의 자연수

    scanf("%d %d %d", &g_M, &g_n, &g_q);
    initHashtable();
    while (1) {
        scanf(" %c", &cmd);
        if (cmd == 'i') {
            scanf("%d", &key);
            insertKey(key);
        } 
        else if (cmd == 's') {
            scanf("%d", &key);
            searchKey(key);
        }
        else if (cmd == 'p') {
            printHashtable();
        } 
        else if (cmd == 'e') {
            printHashtable();
            free(g_hashtable);
            return 0;
        }
    }
}

void initHashtable() {
    g_hashtable = (int*)malloc(g_M * sizeof(int));
    for (int i = 0; i < g_M; i++) {
        g_hashtable[i] = 0; // 빈 버켓은 0으로 초기화
    }
}

int hashFunction(int key) {
    return key % g_M;
}

int doubleHashFunction(int key) {
    return g_q - (key % g_q);
}

void insertKey(int key) {
    int idx = hashFunction(key); // 해시값을 계산
    int originalIdx = idx;
    int step = doubleHashFunction(key);
    int collisionCnt = 0;
    while (g_hashtable[idx] != 0) { // 충돌이 발생하는 동안 반복
        idx = (idx + step) % g_M;
        collisionCnt++;
        if (idx == originalIdx) { // 해시테이블이 가득 찬 경우
            printf("Hash table is full\n");
            return;
        }
    }
    g_hashtable[idx] = key;

    for (int i = 0; i < collisionCnt; i++) {
        printf("C");
    }
    printf("%d\n", idx);
}

void searchKey(int key) {
    int idx = hashFunction(key); // 해시값을 계산
    int originalIdx = idx;
    int step = doubleHashFunction(key);
    while (g_hashtable[idx] != 0) { // 충돌이 발생하는 동안 반복
        if (g_hashtable[idx] == key) {
            printf("%d %d\n", idx, key);
            return;
        }

        idx = (idx + step) % g_M;
        if (idx == originalIdx) { // 한 바퀴를 다 돌았을 경우
            printf("-1\n"); // 탐색 결과 없음
            return;
        }
    }
    printf("-1\n");
}

void printHashtable() {
    for (int i = 0; i < g_M; i++) {
        printf(" %d", g_hashtable[i]);
    }
    printf("\n");
}

/*
13 10 11
i 25
i 13
i 16
i 15
i 70
p
i 28
i 31
i 20
i 14
s 20
s 27
i 38
e
*/

 

 

 

 

 

 

 

 

 

 

출처 및 참고: 알고리즘-원리와 응용(국형준교수님), Algorithm Design(Jon Kleinberg, Eva Tardos), Foundations of Algorithms using C++(Richard Neapolitan)