[C++] 체이닝(Chaining)을 이용한 해시 테이블(Hash Table) 구현

체이닝(Chaining)을 이용한 해시 테이블(Hash Table) 구현

체이닝(Chaining)

• 해시 테이블에 두 값을 모두 저장할 수 있는 여러 방법 중 하나
• 해시 테이블의 특정 위치에서 하나의 키 를 저장하는 것이 아니라 하나의 연결 리스트 를 저장함.
  • 새로 삽입된 키에 의해 충돌이 발생하면 리스트의 맨 뒤에 새로운 키를 추가함.
    • 따라서 다수의 원소를 원하는 만큼 저장할 수 있음.
  • 벡터 대신 연결 리스트를 사용하는 이유?
    • 특정 위치의 원소를 빠르게 삭제하기 위함.

 

 

코드

#include <iostream>
#include <vector>
#include <list>
#include <algorithm>
 
using uint = unsigned int;
 
class hash_map {
    std::vector<std::list<int>> data;
 
public:
    hash_map(size_t n) {
        data.resize(n);
    }
 
    void insert(uint value) {
        int n = data.size();
        data[value % n].push_back(value);
        std::cout << value << "을(를) 삽입했습니다." << std::endl;
    }
 
    bool find(uint value) {
        int n = data.size();
        auto& entries = data[value % n];
        return std::find(entries.begin(), entries.end(), value) != entries.end();
    }
 
    void erase(uint value) {
        int n = data.size();
        auto& entries = data[value % n];
        auto iter = std::find(entries.begin(), entries.end(), value);
 
        if (iter != entries.end()) {
            entries.erase(iter);
            std::cout << value << "을(를) 삭제했습니다." << std::endl;
        }
    }
};
 
int main() {
    hash_map map(7);
 
    auto print = [&](int value) {
        if (map.find(value)) {
            std::cout <<"해시 맵에서 " << value << "을(를) 찾았습니다.";
        }
        else {
            std::cout << "해시 맵에서 " << value << "을(를) 찾지 못했습니다."; 
        }
        std::cout << std::endl;
    };
 
    map.insert(2);
    map.insert(25);
    map.insert(10);
    print(25);
 
    map.insert(100);
    map.insert(55);
 
    print(100);
    print(2);
 
    map.erase(2);
 
    return 0;
}

 

결과

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