해시 테이블의 충돌: 체이닝(Chaining)

코딩 테스트를 위한 자료 구조와 알고리즘 with C++

 

 

체이닝(Chaining)

• 해시 테이블의 특정 키에 값을 저장하는 것이 아니라 값의 리스트를 저장한다.
• 충돌이 발생할 경우 리스트의 마지막에 원소를 추가한다.

 

체이닝을 사용한 해시 테이블의 성능

• 삽입은 O(1) 복잡도를 갖는다.
• 원소 개수에 비해 테이블의 크기가 작으면 리스트가 평균적으로 길어지므로 검색 속도가 저하된다.
• 원소 개수에 비해 테이블이 너무 크면 공간이 낭비된다.

 

체이닝으로 충돌을 해결한 해시 맵

 

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

using namespace std;
using uint = unsigned int;

class hash_map
{
    // 값의 리스트를 벡터로 관리한다.
    vector<list<int>> data;

public:
    hash_map(size_t n)
    {
        data.resize(n);
    }

    void insert(uint value)
    {
        data[hash(value)].emplace_back(value);

        cout << value << "을(를) 삽입했습니다." << endl;
    }

    bool find(uint value)
    {
        list<int>& entries = data[hash(value)];

        return std::find(entries.begin(), entries.end(), value) != entries.end();
    }

    void erase(uint value)
    {
        // data[hash(value)].remove(value);
        list<int>& entries = data[hash(value)];
        list<int>::iterator it = std::find(entries.begin(), entries.end(), value);

        if (it != entries.end())
        {
            entries.erase(it);

            cout << value << "을(를) 삭제했습니다." << endl;
        }
    }

private:
    uint hash(uint value)
    {
        return value % data.size();
    }
};

void main()
{
    hash_map map(7);

    auto print = [&](int value)
    {
        if (map.find(value))
            cout << "해시 맵에서 " << value << "을(를) 찾았습니다." << endl;
        else
            cout << "해시 맵에서 " << value << "을(를) 찾지 못했습니다." << endl;
    };

    map.insert(2);
    map.insert(25);
    map.insert(10);

    // 2와 100의 해시 값은 같다.
    map.insert(100);
    map.insert(55);

    print(100);
    print(2);

    map.erase(2);
}

 

출력

2을(를) 삽입했습니다.
25을(를) 삽입했습니다.
10을(를) 삽입했습니다.
100을(를) 삽입했습니다.
55을(를) 삽입했습니다.
해시 맵에서 100을(를) 찾았습니다.
해시 맵에서 2을(를) 찾았습니다.
2을(를) 삭제했습니다.