43. 해싱 오버플로우 처리 기법

오버플로우를 처리하기 위해서는 다양한 방법이 존재한다.

 

체인법

체인법은 충돌이 발생한 버킷에 연결리스트를 사용하여 데이터를 저장하는 방법이다.

void insertData(HashTable* ht, int key) {
    int index = hashFunction(key, ht->size);

    // 새로운 노드 생성
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->next = NULL;

    // 버킷에 노드 추가
    if (ht->table[index] == NULL) {
        ht->table[index] = newNode;
    } else {
        Node* curr = ht->table[index];
        while (curr->next != NULL) {
            curr = curr->next;
        }
        curr->next = newNode;
    }
}

위처럼 버킷이 비어있다면 삽입, 충돌이라면 연결리스트를 통해 데이터를 저장하게 된다.

---

선형탐사법

충돌이 발생했을 때 다음 버킷으로 이동하면서 빈 버킷을 찾는 방법이다.

선형탐사법은 간단하고 구현하기 쉽지만 데이터의 군집 문제가 발생할 수 있다.

void insertData(HashTable* ht, int key, int value) {
    int index = hashFunction(key);
    int i = index;

    while (ht->used[i]) { // 빈 버킷이 아닐 경우 다음 순차적인 버킷으로 이동
        i = (i + 1) % SIZE; // 해시 테이블의 끝에 도달하면 다시 처음으로 돌아감
        if (i == index) { // 해시 테이블이 모두 채워진 경우
            printf("해시 테이블이 가득 찼습니다.\n");
            return;
        }
    }

    // 데이터 삽입
    ht->keys[i] = key;
    ht->values[i] = value;
    ht->used[i] = 1;
}

---

이차조사법

충돌이 발생했을 때 일정한 간격으로 다음 버킷을 탐색하여 빈 버킷을 찾는 방법이다.

충돌을 해결하기 위한 간격은 제곱 수를 이용하여 다음 버킷을 탐색하며 이를 통해 선형탐사법의 군집 문제를 완화할 수 있다..

void insertData(HashTable* ht, int key, int value) {
    int index = hashFunction(key);
    int i = index;
    int count = 1;

    while (ht->used[i]) { // 빈 버킷이 아닐 경우 다음 버킷을 탐색
        i = (index + count * count) % SIZE; // 다음 버킷은 현재 위치에서 제곱 수의 간격으로 이동
        count++;

        if (count > SIZE) { // 해시 테이블이 모두 채워진 경우
            printf("해시 테이블이 가득 찼습니다.\n");
            return;
        }
    }

    // 데이터 삽입
    ht->keys[i] = key;
    ht->values[i] = value;
    ht->used[i] = 1;
}

---

이중해싱법

충돌이 발생했을 때에 두 개의 해시함수를 사용하여 다음 버킷을 탐색한다.

void insertData(HashTable* ht, int key, int value) {
    int index = hashFunction1(key);
    int i = index;
    int step = hashFunction2(key);

    while (ht->used[i]) { // 빈 버킷이 아닐 경우 다음 버킷을 탐색
        i = (i + step) % SIZE; // 두 번째 해시 함수로 다음 버킷 결정

        if (i == index) { // 모든 버킷을 확인한 경우
            printf("해시 테이블이 가득 찼습니다.\n");
            return;
        }
    }

    // 데이터 삽입
    ht->keys[i] = key;
    ht->values[i] = value;
    ht->used[i] = 1;
}