C++로 구현하는 자료구조 (3) - HashMap

C++로 구현하는 자료구조

세 번째 C++ 세 번째 포스팅은 해시맵이다. 해시맵은 실무에서도 다양하게 응용되는 친숙한 자료구조이다. 어떤 내부구조를 갖고 있는지 함께 알아보자!

 

---

1. Hashmap (해시 맵, 해시 테이블)

해시맵은 키를 통해 어떤 값을 찾기 위한 자료구조이다. 다양한 형태로 응용할 수 있고, 알고리즘 문제 뿐만 아니라 실무에서도 유용하게 사용한다. 해시맵은 읽기, 쓰기, 삭제 모두 평균적으로 O(1)에 수행할 수 있다. 어떻게 이런 시간복잡도가 가능할까?

 

2. Hasing

해시맵을 이해하기 위해선 먼저 해싱을 알아야한다. 해싱은 해쉬함수를 이용해서 키를 숫자로 변환하는 과정이다. 이렇게 생성된 키는 해쉬맵 내부에 있는 자료구조 방 번호가 된다. 얻어진 방 번호를 통해 값을 저장하고, 찾고, 삭제하면 되는 것이다.

 

출처: https://www.geeksforgeeks.org/implementing-our-own-hash-table-with-separate-chaining-in-java/

 

3. Hash collision

그런데 서로 다른 키 값에 대해 같은 방 번호가 나온다면 어떻게 될까? 키를 통해 얻으려고 하는 값을 얻지 못하거나, 엉뚱한 키가 삭제되거나 하는 문제가 발생하게 된다. 이런 경우를 "해시 충돌"이라 하며, 해시 충돌을 최대한으로 줄이는 해시 함수의 설계가 해시 테이블의 핵심이라고 볼 수 있다.

충돌이 일어나도 해결할 수 있는 방법은 두 가지가 있다. 가장 많이 쓰이는 방법은 체이닝이다. 해시 함수를 통해 얻어지는 방 번호에 해당하는 연결 리스트 등의 자료구조 만들어 놓고, 충돌이 일어나면 키 값을 통해 연결리스트를 순회하는 방법이다. 두 번째 방법은 개방 번지화이다. 이 방법은 비어있는 공간을 찾아서 할당하는 방법이다. 이번 포스팅에서는 이 방법으로 해시맵을 구현했다.

 

 

4. 소스코드

// KeyLinkedList.h
// key값을 갖을 수 있는 연결 리스트 자료구조

#pragma once

#include <iostream>
using namespace std;

template <typename T, typename V>
class Node {
public:
    T key;
    V value;
    Node<T, V>* next;
    Node(T key, V value) : key(key), value(value) {}
};

template <typename T, typename V>
class KeyLinkedList {
private:
    int size = 0;
public:
    Node<T, V>* head;

    void add(T key, V value) {
        if (this->head) {
            Node<T, V>* cursor = this->head;
            while (cursor->next) {
                cursor = cursor->next;
            }
            cursor->next = new Node<T, V>(key, value);
        }
        else {
            this->head = new Node<T, V>(key, value);
        }
        this->size++;
    }

    V get(const T& index) {
        Node<T, V>* cursor = this->head;
        while (cursor->key != index) {
            cursor = cursor->next;
        }
        return cursor->value;
    }

    int length() {
        return this->size;
    }
};

// HashMap.h

#pragma once
#include "KeyLinkedList.h"
#include <string>
#include <stdexcept>

using namespace std;

template <typename T, typename V>
class HashMap {
private:
    KeyLinkedList<T, V>* container[3];

    int hash(T key) {
        int hashValue = -1;
        int tmp = 0;
        
        for (char c : key) {
            tmp += (int)c;
        }
        hashValue = tmp % 3;

        return hashValue;
    }

    Node<T, V>* _findNodeByKey(T key, Node<T, V>* nowCursor) {
        Node<T, V>* cursor = nowCursor;
        while (cursor != nullptr) {
            if (cursor->key == key) {
                break;
            }
            cursor = cursor->next;
        }
        return cursor;
    }

public:
    HashMap() {
        for (int i = 0; i < 3; i++) {
            container[i] = new KeyLinkedList<T, V>();
        }
    }

    void put(T key, V value) {
        int hashcode = this->hash(key);
        
        Node<T, V>* cursor = this->container[hashcode]->head;
        cursor = this->_findNodeByKey(key, cursor);

        // 해쉬코드 컨테이너에 키가 있다면
        if (cursor != nullptr) {
            // 덮어쓰기
            cursor->value = value;
        }
        // 없다면
        else {
            // 컨테이너에 노드추가
            this->container[hashcode]->add(key, value);
        }
    }

    V get(T key) {
        V value;
        int hashcode = this->hash(key);

        Node<T, V>* cursor = this->container[hashcode]->head;
        cursor = this->_findNodeByKey(key, cursor);

        // 해쉬코드 컨테이너에 키가 있다면
        if (cursor != nullptr) {
            // 값 리턴
            return cursor->value;
        }
        // 없다면
        else {
            cout << "키를 찾을 수 없습니다." << endl;
            return -1;
        }
    }

    void remove(T key) {
        int hashcode = this->hash(key);

        Node<T, V>* head = this->container[hashcode]->head;
        Node<T, V>* cursor = this->_findNodeByKey(key, head);
        
        if (cursor == nullptr) {
            cout << "키를 찾을 수 없습니다." << endl;
            return;
        }
        else if (head == cursor) {
            head = head->next;
            this->container[hashcode]->head = head;
        }
        else {
            while (head->next != cursor) {
                head = head->next;
            }

            cout << head->key << endl;

            if (head->next->next == nullptr) {
                head->next = nullptr;
            }
            else {
                head->next->next = head->next;
            }

            delete cursor;
        }
    }

    ~HashMap() {
        delete[] this->container;
    }
};

#include <iostream>
#include "datastructure/HashMap.h"

using namespace std;

int main() {

    HashMap<string, int>* hashmap = new HashMap<string, int>() ;

    hashmap->put("abc", 213);
    hashmap->put("bcd", 1234345);

    cout << hashmap->get("abc") << endl;
    cout << hashmap->get("bcd") << endl;

    hashmap->put("abc", 41235);
    hashmap->put("bcd", 12323455);

    cout << hashmap->get("abc") << endl;
    cout << hashmap->get("bcd") << endl;

    cout << endl;
    hashmap->remove("abc");
    cout << hashmap->get("abc") << endl; // 키를 찾을 수 없습니다.
    
    cout << endl;
    hashmap->put("abcc", 123);
    hashmap->put("abcd", 123);
    hashmap->put("abcf", 156);
    hashmap->put("abcg", 1243);
    hashmap->put("abcq", 123);
    hashmap->remove("abcd");
    cout << hashmap->get("abcd") << endl; // 키를 찾을 수 없습니다.
    cout << hashmap->get("abcg") << endl;

    return 0;
}

 

처음 해시맵의 내부구조를 공부할 때 어렵게 느껴지고, 어떻게 이런 생각을 했을까 감탄했었다. 천천히 해시맵을 구현하다 보면 한층 더 실력이 상승하는 느낌을 가져갈 있을 것이다.