C++ HashMap 구현해보기 (unorder_map)

key - > hashfunc -> hash value

hash value가 같을때 충돌 회피법

개방주소법 : 다른 주소로 보냄

선형 탐색(Linear Probing) : 해시충돌 시 다음 버켓, 혹은 몇 개를 건너뛰어 데이터를 삽입한다.

제곱 탐색(Quadratic Probing) : 해시충돌 시 제곱만큼 건너뛴 버켓에 데이터를 삽입(1,4,9,16..)

이중 해시(Double Hashing) : 해시충돌 시 다른 해시함수를 한 번 더 적용한 결과를 이용함.

체이닝 : 배열 안에 리스트 std::list[]

최선 : O(1)

최악 : O(n)

외, 내부 단편화 가능성 모두 존재

◎ 체이닝(Chaining)의 장점  

 → 연결 리스트만 사용하면 된다. 즉, 복잡한 계산식을 사용할 필요가 개방주소법에 비해 적다.

 → 해시테이블이 채워질수록, Lookup 성능저하가 Linear하게 발생한다. 

◎ 개방주소법(Open Addressing)의 장점 

 → 체이닝처럼 포인터가 필요없고, 지정한 메모리 외 추가적인 저장공간도 필요없다. 

 → 삽입,삭제시 오버헤드가 적다.

 → 저장할 데이터가 적을 때 더 유리하다.

소스 코드 (체이닝)

#pragma once
#include <iostream>
#include <list>
 
template<typename TKey, typename TValue>
class MyHashMap {
private:
    template<typename TKey, typename TValue>
    struct Data
    {
        TKey key;
        TValue value;
    };
    static int const MAX_COUNT = 5;
    std::list<Data<TKey, TValue>*> bucket[MAX_COUNT];
    int CalcHashFunc(TKey key);
public:
    MyHashMap();
    void Insert(TKey key, TValue value);
    void Delete(TKey key);
    void Print();
};
 
template<typename TKey, typename TValue>
MyHashMap<TKey, TValue>::MyHashMap() {
}
template<typename TKey, typename TValue>
int MyHashMap<TKey, TValue>::CalcHashFunc(TKey key) {
    return key % MAX_COUNT;
}
template<typename TKey, typename TValue>
void MyHashMap<TKey, TValue>::Insert(TKey key, TValue value) {
    std::list<Data<TKey, TValue>*> &list = bucket[CalcHashFunc(key)];
    if (list.size() > 0) {
        for (Data<TKey, TValue> *it : list) {
            if (it->key == key) {
                it->value = value;
                return;
            }
        }
    }
    Data<TKey, TValue>* data = new Data<TKey, TValue>();
    data->key = key;
    data->value = value;
    list.push_back(data);
}
template<typename TKey, typename TValue>
void MyHashMap<TKey, TValue>::Print() {
    for (int i = 0; i < MAX_COUNT; i++) {
        std::list<Data<TKey, TValue>*> list = bucket[i];
        if (list.size() > 0) {
            for (Data<TKey, TValue> *it : list) {
                std::cout << "key : " << it->key << " value : " << it->value << "\t";
            }
        }
        std::cout << std::endl;
    }
}
template<typename TKey, typename TValue>
void MyHashMap<TKey, TValue>::Delete(TKey key) {
    std::list<Data<TKey, TValue>*> &list = bucket[CalcHashFunc(key)];
    if (list.size() > 0) {
        for (Data<TKey, TValue> *it : list) {
            if (it->key == key) {
                list.remove(it);
                return;
            }
        }
    }
}