[c++] 충돌 해결을 위한 체이닝 기법

08 Dec 2023

해시 테이블을 사용할 때 충돌은 피할 수 없는 문제입니다. 충돌은 서로 다른 키가 동일한 해시값을 갖는 경우에 발생합니다. 이때 체이닝은 충돌을 해결하는 많은 방법 중 하나로, 이 기법은 충돌이 발생할 때 동일한 해시값을 갖는 요소들을 연결 리스트로 연결하여 저장합니다.

체이닝 기법 이해

체이닝은 링크드 리스트(연결 리스트)를 사용하여 동일한 해시값을 가진 요소들을 해시 테이블의 한 슬롯에 저장합니다. 이렇게 하면 충돌이 발생하여 같은 해시 버킷에 여러 개의 요소가 저장되더라도, 해당 슬롯에 연결 리스트로 요소를 추가할 수 있습니다.

체이닝의 장점은 해시 테이블의 슬롯마다 여러 개의 요소를 저장할 수 있다는 것입니다. 그러나 단점으로는 추가적인 연결 리스트 관리가 필요하며, 해시 테이블에 비어 있는 슬롯을 찾는 오버헤드가 발생할 수 있습니다.

C++에서의 체이닝 구현

다음은 C++에서 체이닝 기법을 사용하여 간단한 해시 테이블을 구현하는 예제입니다.

#include <iostream>
#include <list>
using namespace std;

class HashTable {
    int capacity;
    list<int> *table;

public:
    HashTable(int V);
    void insertItem(int key, int data);
    void deleteItem(int key);
    int hashFunction(int key) {
        return (key % capacity);
    }
    void displayHash();
};

HashTable::HashTable(int c) {
    this->capacity = c;
    table = new list<int>[capacity];
}

void HashTable::insertItem(int key, int data) {
    int index = hashFunction(key);
    table[index].push_back(data);
}

void HashTable::deleteItem(int key) {
    int index = hashFunction(key);
    list<int>::iterator i;
    for (i = table[index].begin(); i != table[index].end(); i++) {
        if (*i == key)
            break;
    }

    if (i != table[index].end())
        table[index].erase(i);
}

void HashTable::displayHash() {
    for (int i = 0; i < capacity; i++) {
        cout << i;
        for (auto x : table[i])
            cout << " --> " << x;
        cout << endl;
    }
}

int main() {
    int capacity = 6;
    HashTable ht(capacity);
    ht.insertItem(1, 10);
    ht.insertItem(2, 20);
    ht.insertItem(8, 80);
    ht.insertItem(9, 90);
    ht.insertItem(10, 100);
    ht.deleteItem(2);
    ht.displayHash();
    return 0;
}

결론

체이닝은 충돌을 효과적으로 해결하는 데 사용되는 효율적인 해시 테이블 기법입니다. 체이닝을 통해 충돌을 줄일 수 있으며, 이를 통해 해시 테이블의 검색, 삽입 및 삭제 연산에 대한 성능을 향상시킬 수 있습니다.

출처

Keywords: 충돌, 해시 테이블, 체이닝, C++