C++ 해시(Hash)의 의미 그리고 구현

3명의 사람 (김연아, 손흥민, 서장훈) 이 위와 같이 부탁을 했다. 그리고 이러한 기능을 C++ 를 사용해서 구현해달라고 했다. 파이썬과 다르게, 기본적으로 C++ 에서는 이런 기능을 지원하지 않는다. 어떻게 가장 효율적이고, 빠른 자료구조가 될 수 있을까?

 

답은, 각각의 이름(텍스트)에 대해서, 유일한 Key 값을 가지게 하는 것이다. 만들어진 Key 값을 이용해서 자료에 접근한다면 O(1) 시간만에 접근할 수 있다.

해시(Hash)의 동작원리

해시에서 Key를 생성하기 위한 다양한 알고리즘이 존재한다. MD-5나 SHA이 그 유명한 해시 알고리즘 중 하나이다.

우리는 학습을 목표로, 문자열을 통해서 간단한 해시를 만드는 방법을 알아본다.

 

'apple' 이라는 문자열이 주어졌다고 가정하고 Key를 만들기 위해서, 특정한 소수인 '5381' 을 이용해보겠다.

Key는 최대한 중첩되지않고, 고르게 만드는 것이 좋다고 알려져 있다.

그렇게 만들기 위해서 아래와 같은 과정을 거칠 것이다.

 

(1) Hash 값을 왼쪽으로 5번 비트연산시킨다.

(2) 원본 Hash 값을 더한다.

(3) 한 문자의 ASCII 값을 더한다.

(4) 위의 결과를 모든 문자에 대해서 반복한다.

(5) 최종 값이 해시테이블의 범위를 벗어나면, 나머지 연산을 취해준다.

 

Hash의 최대 테이블 크기를 '8191'로 가정해보겠다. 상세한 과정을 보이면 아래와 같다.

이러한 간단하면서도 일반적인 계산은 나름 분포도가 좋은 계산이 나오는 것으로 보여진다.

해시(Hash)의 충돌

위와 같이 Key를 만들었고, 만들어진 Key의 위치에 자료를 삽입할 수 있다.

 

그런데, 엄밀히 말하면 Key라는 것은 최대한 분포도가 넓게 만들긴 하지만, 언젠가는 다른 문자열에 대해서 동일한 Key값이 발생할 수 있다.

예를 들어서, '이승우'와 '손연재'가 동일한 Key값을 가질 수 있다는 것이다. 이렇게 서로 다른 원본에 대해서 동일한 Key 값을 가지게 되는 현상을 해시에서 '충돌'이 발생했다고 한다.

 

충돌을 해결하는 방법은 크게 다음과 같다.

 

(1) 충돌이 일어난 인덱스를 뛰어넘어서, 빈 공간이 있는지 탐색 후 삽입

     → 개방주소법 (Open addressing)

 

(2) 충돌이 일어난 지점을 사용하되, 연결 리스트로 묶는 방법

     → 체이닝 (Chaning)

 

개방주소법의 경우, 인덱스만 증가시켜주면 되므로 안정적인 방법이다.

체이닝의 경우, 정해진 해시테이블 이외의 주소를 추가로 할당해서 확장해서 사용할 수 있다는 장점이 있다.

구현 (C++)

소멸자 및 delete 부분 추가

// CPP program to implement hashing with chaining
#include <iostream>
#include <list>

using namespace std;

class Hash
{
    int BUCKET; // No. of buckets

    // Pointer to an array containing buckets
    list<int>* table;
public:
    Hash(int V); // Constructor

    ~Hash()
    {
        // 메모리 누수 방지
        delete[] table;
    }

    // inserts a key into hash table
    void insertItem(int x);

    // deletes a key from hash table
    void deleteItem(int key);

    // hash function to map values to key
    int hashFunction(int x) {
        return (x % BUCKET);
    }

    void displayHash();
};

Hash::Hash(int b)
{
    this->BUCKET = b;
    table = new list<int>[BUCKET];
}

void Hash::insertItem(int key)
{
    int index = hashFunction(key);
    table[index].push_back(key);
}

void Hash::deleteItem(int key)
{
    // get the hash index of key
    int index = hashFunction(key);

    // find the key in (index)th list
    list <int> ::iterator i;
    for (i = table[index].begin();
        i != table[index].end(); i++) {
        if (*i == key)
            break;
    }

    // if key is found in hash table, remove it
    if (i != table[index].end())
        table[index].erase(i);
}

// function to display hash table
void Hash::displayHash() {
    for (int i = 0; i < BUCKET; i++) {
        cout << i;
        for (auto x : table[i])
            cout << " --> " << x;
        cout << endl;
    }
}

// Driver program
int main()
{
    // array that contains keys to be mapped
    int a[] = { 15, 11, 27, 8, 12 };
    int n = sizeof(a) / sizeof(a[0]);

    // insert the keys into the hash table
    Hash h(7); // 7 is count of buckets in
    // hash table
    for (int i = 0; i < n; i++)
        h.insertItem(a[i]);

    // delete 12 from hash table
    h.deleteItem(12);

    // display the Hash table
    h.displayHash();

    return 0;
}

출처 : C++ program for hashing with chaining - GeeksforGeeks

출처 : [C++] 해시(Hash) 자료구조란? (C++로 구현하기) (tistory.com)