선형 조사법(Linear Probing)

선형 조사법(Linear Probing)은 해시 테이블에서 충돌이 발생했을 때 해결하는 방법 중 하나이다. 해싱 함수에서 동일한 인덱스가 생성되면, 해당 인덱스에 데이터를 삽입할 수 없으므로 선형적으로 다음 인덱스를 조사하며 빈 자리를 찾는 방식이다.

해싱 함수와 mod 연산

주어진 코드에서 해싱 함수는 mod7 연산을 통해 7을 나눈 나머지를 사용해 인덱스를 생성한다. 이 과정은 데이터가 해시 테이블의 인덱스 범위를 넘지 않도록 제한하는 역할을 한다.

int hash(int key) {
    return key % 7;
}

위 함수는 key 값을 해시 테이블 크기(7)로 나눈 나머지 값을 반환하여 배열에 저장될 인덱스를 생성한다.

충돌(Collision)과 오버플로우

해싱을 사용할 때, 서로 다른 두 키가 동일한 인덱스로 해싱되는 상황을 충돌(Collision)이라고 한다. 선형 조사법은 충돌이 발생하면, 다음 인덱스를 순차적으로 검사하며 빈 자리를 찾는다.

예를 들어, key=15를 해싱하면 hash(15) = 15 % 7 = 1이 된다. 만약 index=1에 이미 값이 있다면, 선형 조사법은 index=2로 이동하여 빈 자리를 찾는다. 만약 충돌을 해결하지 않으면 데이터가 덮어써질 수 있다.

또한, 해시 테이블이 꽉 차서 더 이상 빈 공간이 없을 경우 오버플로우가 발생할 수 있다.

#include <stdio.h>
int i, k, n = 8;

// 해싱 함수 정의 (7로 나눈 나머지를 사용)
int hash(int key) {
    return key % n;
}

int main() {
    int key;
    int list[8] = {0, 0, 10, 3, 2, 5, 0, 0};  // 초기 해시 테이블
    
    scanf("%d", &key);  // 입력값을 키로 설정
    int index = hash(key);  // 해싱하여 첫 인덱스 계산

    while (1) {
        // 빈 자리를 찾으면 값을 삽입하고 종료
        if (list[index] == 0) {
            list[index] = key;
            break;
        } else {
            // 충돌 시 k 값을 증가시키며 다음 인덱스 탐색
            k++;
            index = (hash(key) + k) % n;
        }
    }
    printf("%d", index);  // 최종 인덱스 출력
    return 0;
}

요약

• 선형 조사법은 충돌이 발생할 때 빈 자리를 찾기 위해 다음 인덱스를 선형적으로 탐색한다.
• 충돌은 동일한 인덱스로 해싱되는 상황에서 발생하며, 선형 조사법으로 해결할 수 있다.
• 오버플로우는 해시 테이블에 빈 공간이 없을 때 발생할 수 있다.