[c언어] 해시 테이블의 충돌 해결 알고리즘

26 Dec 2023

c언어

해시 테이블은 데이터를 저장하고 검색하기 위한 자료구조로, 각 데이터에 대한 고유한 인덱스를 생성하여 빠르게 접근할 수 있습니다. 그러나 해시 함수의 충돌로 인해 동일한 인덱스를 갖는 데이터가 발생할 수 있습니다. 이러한 충돌을 해결하기 위한 다양한 알고리즘이 존재합니다.

선형 조사 (Linear Probing)

개념

선형 조사는 충돌이 발생한 경우, 다음 칸을 확인하고 비어있는 칸을 찾을 때까지 순차적으로 탐색하는 방법입니다.

예시

다음은 선형 조사를 사용한 해시 테이블의 충돌 해결 알고리즘의 간단한 예시 코드입니다.

int hash_function(int key, int size) {
    return key % size;
}

void insert(int key, int value, int table[], int size) {
    int index = hash_function(key, size);
    while (table[index] != 0) {
        index = (index + 1) % size;
    }
    table[index] = value;
}

이차 조사 (Quadratic Probing)

개념

이차 조사는 충돌이 발생한 경우, 이차 함수 f(i) = i^2을 이용하여 새로운 위치를 찾는 방법입니다.

예시

다음은 이차 조사를 사용한 해시 테이블의 충돌 해결 알고리즘의 간단한 예시 코드입니다.

void insert(int key, int value, int table[], int size) {
    int index = hash_function(key, size);
    int i = 1;
    while (table[index] != 0) {
        index = (index + i * i) % size;
        i++;
    }
    table[index] = value;
}

체이닝 (Chaining)

개념

체이닝은 해시 테이블의 각 슬롯에 연결 리스트를 이용하여 데이터를 저장하는 방법입니다. 충돌이 발생하면 해당 슬롯의 연결 리스트에 데이터를 추가합니다.

예시

다음은 체이닝을 사용한 해시 테이블의 충돌 해결 알고리즘의 간단한 예시 코드입니다.

struct Node {
    int key;
    int value;
    struct Node* next;
};

void insert(int key, int value, struct Node* table[], int size) {
    int index = hash_function(key, size);
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->key = key;
    newNode->value = value;
    newNode->next = table[index];
    table[index] = newNode;
}

이와 같은 충돌 해결 알고리즘을 사용하여 해시 테이블을 구현하면, 해시 함수의 충돌로 인해 발생하는 성능 저하를 최소화할 수 있습니다.

참고 문헌:

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms, 3rd Edition. The MIT Press.