해시테이블 구현 / 이중 해싱

// 이 코드는 해시 테이블을 이중 해싱(Double Hashing)을 사용하여 구현한 프로그램입니다.
// 이중 해싱은 충돌이 발생했을 때 보조 해시 함수(hh)를 사용하여 새로운 위치를 계산합니다.
// 주요 기능:
// 1. 'i': 원소 삽입 - 기본 해시 함수와 보조 해시 함수를 사용하여 데이터를 삽입합니다.
//    - 충돌이 발생하면 보조 해시를 활용해 새로운 위치를 탐색하며, 충돌 횟수를 출력합니다.
// 2. 's': 원소 검색 - 기본 해시 값을 기준으로 값을 탐색하고, 해당 값이 저장된 인덱스를 반환합니다.
// 3. 'p': 해시 테이블 출력 - 해시 테이블의 모든 슬롯 값을 출력합니다.
// 4. 'e': 프로그램 종료 - 해시 테이블을 출력하고 종료합니다.
// 기본 해시 함수(h)는 `x % M`, 보조 해시 함수(hh)는 `q - (x % q)`를 사용합니다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>

// 이 코드는 해시 테이블을 이중 해싱(Double Hashing)을 사용하여 구현한 프로그램입니다.
// 이중 해싱은 충돌이 발생했을 때 보조 해시 함수(hh)를 사용하여 새로운 위치를 계산합니다.
// 주요 기능:
// 1. 'i': 원소 삽입 - 기본 해시 함수와 보조 해시 함수를 사용하여 데이터를 삽입합니다.
//    - 충돌이 발생하면 보조 해시를 활용해 새로운 위치를 탐색하며, 충돌 횟수를 출력합니다.
// 2. 's': 원소 검색 - 기본 해시 값을 기준으로 값을 탐색하고, 해당 값이 저장된 인덱스를 반환합니다.
// 3. 'p': 해시 테이블 출력 - 해시 테이블의 모든 슬롯 값을 출력합니다.
// 4. 'e': 프로그램 종료 - 해시 테이블을 출력하고 종료합니다.
// 기본 해시 함수(h)는 `x % M`, 보조 해시 함수(hh)는 `q - (x % q)`를 사용합니다.


// 해시 테이블의 크기, 삽입할 요소 수, 보조 해시값을 전역 변수로 선언
int M, n;

// 함수 선언
int h(int x);                      // 기본 해시 함수
int hh(int x, int q);              // 보조 해시 함수 (이중 해싱용)
int insertitem(int* A, int x, int q);  // 요소 삽입 함수
void printHashTable(int* A);       // 해시 테이블 출력 함수
int searchitem(int* A, int x);     // 요소 검색 함수

int main()
{
    int x, q;                      // 입력받을 값과 보조 해싱에 사용할 값
    char c = 0;                    // 명령어 입력용 변수

    // 해시 테이블 크기 M, 삽입할 요소 수 n, 보조 해싱 값 q 입력
    scanf("%d %d %d", &M, &n, &q);

    // 해시 테이블 초기화: 크기 M의 배열 할당 후 0으로 초기화
    int* A = (int*)malloc(sizeof(int) * M);
    for (int i = 0; i < M; i++)
        A[i] = 0;

    // 명령어 'e'가 입력될 때까지 반복 실행
    while (c != 'e')
    {
        scanf(" %c", &c); // 명령어 입력

        if (c == 'e') {   // 종료 명령어
            printHashTable(A); // 해시 테이블 출력 후 종료
            break;
        }
        if (c == 'i') {   // 삽입 명령어
            scanf("%d", &x);
            printf("%d\n", insertitem(A, x, q)); // 삽입 후 인덱스 출력
        }
        else if (c == 's') { // 검색 명령어
            scanf("%d", &x);
            int result = searchitem(A, x);
            printf("%d", result); // 검색 결과 인덱스 출력
            if (result != -1)
                printf(" %d\n", A[result]);
            else
                printf("\n");
        }
        else if (c == 'p') { // 출력 명령어
            printHashTable(A);
        }
    }

    return 0;
}

// 기본 해시 함수: 입력값을 M으로 나눈 나머지를 반환
int h(int x) {
    return x % M;
}

// 보조 해시 함수: 보조 해싱을 통해 충돌 해결
int hh(int x, int q) {
    return q - (x % q);
}

// 해시 테이블에 원소를 삽입하는 함수
int insertitem(int* A, int x, int q) {
    int index = h(x);  // 기본 해시 인덱스 계산
    int cnt = 0;       // 충돌 횟수 초기화

    // 비어 있는 자리가 나올 때까지 반복
    while (A[index] != 0) {
        printf("C");   // 충돌 발생 시 'C' 출력
        cnt++;         // 충돌 횟수 증가
        // 이중 해싱을 통해 새로운 위치 계산
        index = (h(x) + cnt * hh(x, q)) % M;
    }

    A[index] = x;      // 비어 있는 위치에 값 삽입
    return index;      // 삽입된 인덱스 반환
}

// 해시 테이블의 내용을 출력하는 함수
void printHashTable(int* A) {
    for (int i = 0; i < M; i++) {
        printf(" %d", A[i]); // 테이블의 각 위치 출력
    }
    printf("\n");           // 줄바꿈
}

// 해시 테이블에서 값을 검색하는 함수
int searchitem(int* A, int x) {
    int index = h(x);       // 기본 해시 인덱스 계산
    int s = -1;             // 검색 결과 위치 초기화 (찾지 못하면 -1 반환)
    
    // 해시 테이블 전체를 탐색하여 값 찾기
    for (int i = 0; i < M; i++) {
        if (A[i] == x) {    // 값이 일치하는 경우 인덱스 저장
            s = i;
            break;
        }
    }
    return s; // 발견한 인덱스 반환 (없으면 -1 반환)
}