[c++] 해시 테이블 충돌 해결 방법

08 Dec 2023

1. 개별 연결법 (Separate Chaining)

이 방법은 각 해시 버킷당 연결 리스트를 사용하여 충돌을 해결합니다. 해시 값이 동일한 원소는 같은 버킷에 연결 리스트를 통해 연결됩니다. 삽입 및 검색 시간은 리스트의 길이에 비례하여 증가할 수 있지만, 메모리를 효율적으로 사용할 수 있습니다.

#include <iostream>
#include <list>
#include <vector>

class HashTable {
private:
    int size;
    std::vector<std::list<int>> table;

public:
    HashTable(int size) : size(size), table(size) {}

    void insert(int key) {
        int index = key % size;
        table[index].push_back(key);
    }

    bool search(int key) {
        int index = key % size;
        for (int elem : table[index]) {
            if (elem == key) {
                return true;
            }
        }
        return false;
    }
};

int main() {
    HashTable ht(5);
    ht.insert(5);
    ht.insert(10);
    std::cout << ht.search(5) << std::endl;  // Output: 1
    std::cout << ht.search(8) << std::endl;  // Output: 0
    return 0;
}

2. 오픈 주소법 (Open Addressing)

이 방법은 충돌이 발생한 경우, 다른 버킷에 비어있는 공간을 찾아 데이터를 삽입하는 방식입니다. 선형 탐사, 이차원 탐사, 이중 해싱 등이 사용될 수 있습니다.

#include <iostream>
#include <vector>

class HashTable {
private:
    int size;
    std::vector<int> table;

public:
    HashTable(int size) : size(size), table(size, -1) {}

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

    bool search(int key) {
        int index = key % size;
        int originalIndex = index;
        while (table[index] != -1) {
            if (table[index] == key) {
                return true;
            }
            index = (index + 1) % size;
            if (index == originalIndex) {
                break;
            }
        }
        return false;
    }
};

int main() {
    HashTable ht(5);
    ht.insert(5);
    ht.insert(10);
    std::cout << ht.search(5) << std::endl;  // Output: 1
    std::cout << ht.search(8) << std::endl;  // Output: 0
    return 0;
}

더 많은 정보를 원하시면 해시 테이블 충돌 해결을 참고하세요.