해시 충돌을 막는 해시 테이블

// 가장 쉬운 독학 알고리즘 첫걸음 C & 자바편
// p.252

#include<stdio.h>
#define LEN 10

int hashTable[LEN];

int hashFunc(int data) // 해시 함수
{
    return data % 10;
}

int main()
{
    int inp; // 입력값
    int hashValue; // 해시값
    int idx; // 저장 위치, 탐색 위치

    for(int i=0; i<10; i++) hashTable[i] = -1; // 초기화

    // 데이터를 입력하여 해시 테이블에 저장
    while(1)
    {
        printf("저장할 데이터 = ");
        scanf("%d", &inp);

        if(inp < 0) break; // 입력값이 음수이면 반복 종료

        hashValue = hashFunc(inp); // 해시 함수를 통해 해시값 구하기

        // 배열의 저장 위치(idx) 구하기
        idx = hashValue;
        while(hashTable[idx] != -1)
        {
            idx++;
            if(idx >= LEN) idx = 0;
            if(idx == hashValue) break;
        }
        if(hashTable[idx] == -1) hashTable[idx] = inp; // 해시 테이블 저장
        else printf("해시 테이블이 가득 찼습니다.\n");
    }

    // 해시 테이블에서 데이터 탐색
    while(1)
    {
        printf("탐색할 데이터 = ");
        scanf("%d", &inp);

        if(inp < 0) break; // 입력값이 음수이면 반복 종료

        hashValue = hashFunc(inp); // 해시 함수를 통해 해시값 구하기

        // 입력값(inp) 검색
        idx = hashValue;
        while(hashTable[idx] != -1 and hashTable[idx] != inp)
        {
            idx = (idx + 1) % LEN;
            if(hashTable[idx] == -1 or idx == hashValue) break;
        }

        if(hashTable[idx] == inp) printf("%d번째에서 발견되었습니다.\n", idx);
        else printf("찾을 수 없습니다.\n");
    }
}