해시테이블(HashTable) 구현 해보기

해시 테이블은 데이터를 탐색하는데 탁월한 효과가 있다.

데이터를 key와 해시함수로 얻은 인덱스(index)로 컨테이너에 저장하고, 탐색 시 key를 이용해 바로 접근한다. 

따라서 저장과탐색의 시간복잡도가 O(1)이 된다.

단점은 정해진 크기의 컨테이너가 준비되어 있어야 한다는 것, 충돌이 발생 가능한 점.

 

 

문자열을 해시함수로 인덱스를 얻어내는 예를 들면,

//해시함수
int getKey(string data)
{
    int key = 0;
    for(int i=0; i<data.length(); ++i)
    	key = key * 31 + data[i];
        
    return key % (컨테이너 크기);
}

여기서는 문자열 자체가 key로서 사용되었다.

여기서 "31" 은 인덱스 분포가 골고루 나오게 하는 방법으로 소수를 이용한 것이다.

또한 인덱스는 정해진 컨테이너 범위 내의 숫자여야 하기 때문에 컨테이너 크기로 나눈 나머지를 인덱스로 쓴다.

 

 

해시함수는 결국엔 다른 데이터라도 같은 인덱스를 출력할 수도 있다.

충돌이 나타날 경우 해시테이블은 2가지 방법을 이용한다.

1. 체이닝 : 컨테이너의 노드를 linked list로 확장해서 같은 라인에 저장한다.
2. 개방 주소법 : 충돌한 인덱스 외의 인덱스에 저장한다.

체이닝은 충돌된 데이터 끼리 list로 연결하여 같은 인덱스에 저장한다.

따라서 최악의 경우 한 인덱스에 많은 데이터들이 차례대로 연결되어 탐색시 시간복잡도가 O(N)이 나올 수 있다.

 

개방 주소법은 충돌 발생시 다른 인덱스를 찾는 방법이 또 여러개다.

• 선형 조사법 : 바로 옆자리를 확인하면서 빈자리를 찾는다.
• 이차 조사법 : n^2 만큼 떨어져서 빈자리를 찾는다.

하지만 이것 역시 간격이 일정해서 탐색시 시간복잡도가 O(N)이 나올 수 있다.

그래서 개방 주소법은 이중 해시를 이용한다.

• second_hash(k) = 1+(k%c)

1차 해시함수에서 k가 충돌이 발생하면 2차 해시함수에서 인덱스를 다시 찾는다.

여기서 c는 컨테이너의 크기보다 작은 소수가 좋다.

+1을 한 이유는 c로 나눈 나머지가 0이 나왔을 경우를 피하기 위해서. 왜냐하면 2차 해시함수도 충돌날경우 2차 해시함수의 값만큼 옆으로 이동하면서 빈자리를 찾기 때문이다.

 

*참고로 개방 주소법 방식은 각 노드(슬롯)에 상태값을 표시하는데 [Empty, Deleted, Inuse] 가 있다.

Deleted가 필요한 이유는 데이터를 insert할때 해당 index의 슬롯 상태가 deleted 라면 과거에 충돌이 발생하여 다른 데이터가 들어있다가 빠져나간거라 현재 데이터가 다른 곳에 이미 저장되어 있을지도 모르는 일이다. 때문에 delete상태라면 충돌 가정하에 다음 index를 이어서 찾아봐야한다.

 

 

체이닝방법으로 실제 구현을 해보았다.

문자열을 받아 체이닝 방식 해시테이블 구현

 

먼저 노드의 linked list를 위해 노드 부터 정의 하였다.

struct Node
    {
        string data;
        int cnt =0;     //같은 데이터 갯수
        Node* parent = nullptr;
        Node* child = nullptr;
        Node(string str) : data(str) {}
        ~Node()
        {
            if(child != nullptr)
                delete child;
        }
    };

cnt 같은 경우 문제 풀이에 활용할 수 있다.

 

그 다음 해시테이블 클래스 구현.

Insert 와 Delete 그리고 Display를 구현해 보았다.

class HashTable
{
    struct Node
    {
        string data;
        int cnt =0;     //같은 데이터 갯수
        Node* parent = nullptr;
        Node* child = nullptr;
        Node(string str) : data(str) {}
        ~Node()
        {
            if(child != nullptr)
                delete child;
        }
    };

    Node* array[1000] = { 0, };

    int GetKey(string str)
    {
        int key = 0;
        for (char a : str)
        {
            key = key * 31 + a;
        }
        return key % 1000;
    }

public:
    HashTable() { memset(array, 0, sizeof(array)); }
    ~HashTable()
    {
        for (auto node : array)
        {
            if (node)
                delete node;
        }
    }

    bool Insert(string str)
    {
        int key = GetKey(str);

        if (array[key] == nullptr)          //비어있으면 바로 추가
        {
            array[key] = new Node(str);
            return true;
        }
        else
        {
            Node* cur = array[key];
            while (1)
            {
                if (cur->data.compare(str) == 0)    //있으면 cnt 상승
                {
                    cur->cnt++;
                    return false;
                }
                if (cur->child == nullptr)
                    break;

                cur = cur->child;
            }
            cur->child = new Node(str);             //없으면 마지막 요소로 추가
            cur->child->parent = cur;
            return true;
        }
    }

    bool Delete(string str)
    {
        int key = GetKey(str);
        if (array[key] == nullptr)  //비어있으면 실패
            return false;

        Node* cur = array[key];
        while (1)
        {
            if (cur->data.compare(str) == 0)        // 있으면 cnt 감소하고, 0 이하면 제거.
            {
                if ((--cur->cnt) < 0)
                {
                    if (cur->parent == nullptr)
                        array[key] = cur->child;
                    else
                        cur->parent->child = cur->child;

                    cur->child = nullptr;
                    delete cur;
                }
                return true;
            }
            if (cur->child == nullptr)
                break;

            cur = cur->child;
        }

        return false;   //끝까지 없으면 실패.
    }

    void Display()
    {
        for (int i = 0; i < 1000; ++i)
        {
            if (array[i] != nullptr)
            {
                cout << "array[" << i << "] -> ";
                Node* cur = array[i];
                while (cur)
                {
                    cout << cur->data << "("<<cur->cnt<<")" << ", ";
                    cur = cur->child;
                }
                cout << endl;
            }
        }
    }
};