해시 테이블(Hash Table)

---

목차

1. 해시 테이블(Hash Table)이란?

2. 해시 테이블을 이용한 간단한 구현 

3. 해시 테이블 충돌 해결 방법

4. 해시의 장/단점

5. 해시관련 문제

---

1. 해시 테이블(Hash Table)이란?

해시 테이블은 key와 value로 구성된 하나의 테이블을 의미한다.

해시 테이블을 설명하기 전 예를 들어 해시를 일상 생활에 맞춰보자.

인스타그램을 하게되면 우리는 해시 태그라는 '#'를 볼 수 있다.

해시 태그가 적용된 #홍대 #맛집 이라는 키워드를 클릭하면 우리는 키워드에 해당하는 내용들을 볼 수 있게 된다.

사람이 사는 아파트를 비유해보면 각각의 i동 j호에는 어떤 사람이 살고있다.

위의 예시에서 해시 태그 혹은 i동 j호를 key라고 정의하고 #홍대 #맛집 혹은 어떤 사람을 value라고 생각할 수 있다.

(아직 눌러보지 않았다면 위의 #홍대 #맛집을 한번씩 눌러보자. 각 key에 해당하는 value가 나타남을 알 수 있다.)

이제 다시 알고리즘 측면으로 생각을 해보자.

우리는 어떤 값을 찾기위해 선형 탐색O(N), 이진 탐색O(lgN) 등등의 다양한 알고리즘을 익혀왔다.

하지만 O(lgN)보다 더 빨리 문제를 해결할 수 없을까 고민하던 중 해시 테이블이라는 것이라는게 등장하게 되었고

해시 테이블은 O(1)의 시간 복잡도를 가지게 된다. (위의 #홍대 #맛집도 O(1)이었음을 생각해볼 수 있다.)

이러한 해시 테이블은 Cpp에서 unordered_map, unordered_set으로 이용이 가능하다.

대표적인 해싱 종류들은 http://www.crocus.co.kr/990를 참조해보자.

2. 해시 테이블을 이용한 간단한 구현

이제 우리는 해시 테이블이 뭔지 알게되었고 간단한 예제를 통해 간단한 해시 테이블을 구현해보자.

아래 코드는 하나의 key, value를 입력받는데 key의 모든 값을 아스키코드로 변환하여 총합을 hash_key로 정의하였다.

(예를들어 ab면 a :: 97, b :: 98이니 195를 나타낸다.)

#include <iostream>
#include <cstdio>
#include <string>
 
#define HASHMAX 10000
using namespace std;
 
int hash_table[HASHMAX];
 
int _strlen(char *input)
{
    int i = 0;
    while (input[i] != '\0')
        i++;
 
    return i;
}
 
int split(char *str)
{
    int ret = 0;
 
    int len = _strlen(str);
    for (int i = 0; i < len; i++)
        ret += str[i] - '0';
 
    return ret;
}
 
int main()
{
    while (1)
    {
        char key[10];
        int value;
 
        cout << "key :: ";
        cin >> key;
        cout << "value ::";
        cin >> value;
 
        int hashKey = split(key);
 
        if (!hash_table[hashKey])
        {
            hash_table[hashKey] = value;
            cout << "key :: " << key << " -> " << hashKey << " value :: " << value << " 완료 " << endl;
        }
        else
        {
            cout << "이미 hash_table에 입력한 key가 존재합니다." << endl;
            cout << "이미 존재하는 key :: " << hashKey << " value :: " << value << endl;
            break;
        }
        cout << endl;
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

위의 결과화면을 살펴보면 key, value 입력을 잘 받아오다가 bbb에서 해시 테이블에 이미 key가 존재한다고 나오면서 종료가 된다.

이 과정을 충돌(collision)이라고 한다. 충돌이 잦으면 해시의 최대 장점인 key를 통해 O(1)만에 value를 챙겨올 수 없다.

(이때 해시 테이블 내에서 균등하게 분포되지 않고 특정 주소로 뭉치게 되는 현상을 클러스터링(Clustering)이라고 한다.)

따라서 충돌을 최소화 시키기위해 해시 테이블을 효율적으로 구성해야 한다.

3. 해시 테이블 충돌 해결 방법

보통 해시 함수는 다음과 같이 구현한다.

H(x) = (a*x + b) mod p (이 꼴에 대해서는 선형 합동 생성기 :: http://www.crocus.co.kr/1146?category=209527를 찾아보자.)

여기서 p는 해시 테이블의 최대 크기를 의미하고 있고, a와 b는 임의의 수로 나타낼 수 있다.

#include <iostream>
#include <cstdio>
#include <string>
 
#define HASHMAX 13
#define a 1
using namespace std;
 
int hash_table[HASHMAX];
 
int main()
{
    while (1)
    {
        int key, value;
 
        cout << "key :: ";
        cin >> key;
        cout << "value ::";
        cin >> value;
 
        int hashKey = (a * key) % HASHMAX;
 
        if (!hash_table[hashKey])
        {
            hash_table[hashKey] = value;
            cout << "key :: " << key << " -> " << hashKey << " value :: " << value << " 완료 " << endl;
        }
        else
        {
            cout << "이미 hash_table에 입력한 key가 존재합니다." << endl;
            cout << "이미 존재하는 key :: " << hashKey << " value :: " << value << endl;
            break;
        }
        cout << endl;
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

위의 해시 테이블에는 다음과 같이 저장될 것이고 우리가 이제 찾고자 하는 값을 hash_table[찾고자하는 값]을 입력하면 출력이 제대로 될 것이다.

하지만 위의 상태에서도 25라는 key가 인덱스 12에 들어갔지만 또 12라는 key가 들어오면 충돌이 일어나게 된다.

이러한 해시 충돌에 대해 어떠한 key를 넣어도 해시 테이블 내에서 충돌이 나지 않도록 하는 가장 좋은 방법은 테이블 크기를 무한정 늘려 O(1)만에 쉽게 해결 할 수 있지만, 우리가 사용할 수 있는 메모리는 한정적이기에 이를 최대한 활용해서 O(1)만에 나타내야 한다.

따라서 이를 해결하기 위한 다양한 방법들이 나왔고 그중 몇가지를 말해보고자 한다.

1. 체이닝 기법

해시 체이닝은 충돌이 일어나면 그 자리에서 연결리스트를 만들어 그다음 칸으로 넘겨주는 역할을 한다.

이때 key로 받아내어 계산된 hash_key는 충돌되도 유효하고 하나의 hash_key에 연결리스트로 value가 형성이 된다.

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
 
#define HASHMAX 13
#define a 1
using namespace std;
 
typedef pair<int, int> pii;
 
vector<pii> hash_table[HASHMAX];
 
int main()
{
    cout << "해시 테이블에 삽입\n" << endl;
    for(int i = 0; i < 6; i ++)
    {
        int key, value;
 
        cout << "key :: ";
        cin >> key;
        cout << "value ::";
        cin >> value;
 
        int hashKey = (a * key) % HASHMAX;
 
        // 해시 테이블의 해당하는 key에 아무 값이 없을 경우
        if (hash_table[hashKey].size() == 0)
        {
            hash_table[hashKey].push_back({ key, value });
            cout << "key :: " << key << " -> " << hashKey << " value :: " << value << " 완료 " << endl;
        }
 
        // 어떠한 값이 있을 경우 연결리스트로 이어준다.(여기서는 vector를 이용)
        else
        {
            hash_table[hashKey].push_back({ key, value });
            cout << "key :: " << key << " -> " << hashKey << " value :: " << value << " 완료(충돌이 잠시 일어났습니다.) " << endl;
        }
        cout << endl;
    }
 
    cout << "해시 테이블에서 탐색\n" << endl;
    for (int i = 0; i < 6; i++)
    {
        int key;
        cout << "key :: ";
        cin >> key;
 
        int hashKey = key % HASHMAX;
        for (int j = 0; j < hash_table[hashKey].size(); j++)
            if (hash_table[hashKey][j].first == key)
            {
                cout << "value :: " << hash_table[hashKey][j].second << endl;
                break;
            }
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

2. 선형 조사(Linear Probing)

단순하게 충돌이 일어나면 해시 테이블이 빈곳에 넣어주고, 해시 탐색시에는 해당하는 값이 나올때까지 탐색을 해주는 방식을 이용한다.

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
 
#define HASHMAX 13
#define a 1
using namespace std;
 
typedef pair<int, int> pii;
 
pii hash_table[HASHMAX];
 
int main()
{
    cout << "해시 테이블에 삽입\n" << endl;
    for(int i = 0; i < 7; i ++)
    {
        int key, value;
 
        cout << "key :: ";
        cin >> key;
        cout << "value ::";
        cin >> value;
 
        int hashKey = (a * key) % HASHMAX;
 
        // 해시 테이블의 해당하는 key에 아무 값이 없을 경우
        if (!hash_table[hashKey].first)
        {
            hash_table[hashKey] = { key, value };
            cout << "key :: " << key << " -> " << hashKey << " value :: " << value << " 완료 " << endl;
        }
 
        // 어떠한 값이 있을 경우 선형 탐색
        else
        {
            bool inHash = false;
            for (int j = (hashKey + 1) % HASHMAX; j != hashKey; j = (j + 1) % HASHMAX)
            {
                if (!hash_table[j].first)
                {
                    inHash = true;
                    hash_table[j] = { key, value };
                    cout << "key :: " << key << " -> " << hashKey << " value :: " << value << " 완료(충돌이 잠시 일어났습니다.) " << endl;
                    cout << "충돌에 의해 변경된 위치인 hashKey에 저장 :: " << j << endl;
                    break;
                }
            }
 
            if (!inHash)
            {
                cout << "해시가 가득차 key를 넣을 수 없습니다. 프로그램을 종료합니다." << endl;
                return 0;
            }
        }
        cout << endl;
    }
 
    cout << "해시 테이블에서 탐색\n" << endl;
    for (int i = 0; i < 7; i++)
    {
        int key;
        cout << "key :: ";
        cin >> key;
 
        int hashKey = key % HASHMAX;
        for (int j = hashKey; j != (hashKey - 1 + HASHMAX) % HASHMAX; j = (j + 1) % HASHMAX)
            if (hash_table[j].first == key)
            {
                cout << "value :: " << hash_table[j].second << endl;
                break;
            }
    }
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

이 외에 이차원 조사, 이중 해싱이 존재하는데 간단히 개념만 설명하고 넘어가려 한다.

3. 이차원 조사(Quadratic Probing)

H(x) = (a*x + b + i*i) mod p 꼴로 나타낸다.

현재 해당하는 해시 테이블에 key, value가 존재한다면 i^2으로 다음칸을 넘어가서 확인하는 방식이다.

4. 이중 해싱(Double hashing)

H(x) = (a*x + b + i*f(x)) mod p 꼴로 나타낸다.

이때 f(x)또한 c*x + d같은 수식으로 나타낼 수 있다.

현재 해당하는 해시 테이블에 key, value가 존재한다면 i * f(x)로 다음칸을 넘어가서 확인하는 방식이다.

5. 응용 해싱

이 방법은 따로 공식화된 해싱 방식은 아니지만 유용하다.

string이 key이고, 모든 값에 대해 탐색 시 string을 하나씩 현재 input string과 비교 string을 비교해나가야한다.

이때 걸리는 시간은 O(max(inputStr, str))이 될 것이다.

하지만 이때 해시 value를 두개를 만들어 각각의 해시 value에 서로다른 해시함수로 key를 해싱해준다.

이때 hash1에는 a*x + b에서 13*x + 17로 hash2에는 a*x + b에서 47*x + 7로 잡는다고 가정해보자.

하나의 key가 들어왔을때 두 해시 value는 각 해시 함수에 의해 string에서 int로 변하게 되고

해시 충돌률도 1 / (hash1_size * hash2_size)이기에 충돌 확률도 매우 적어진다.

이 내용의 핵심은 strcmp(str, inputStr)을 하여 비교하지 않고 hash1, hash2를 비교하여 시간 복잡도를 줄일 수 있다.

#include <iostream>
 
#define HASH1_MAX 10000
#define HASH2_MAX 9000
#define HASH1(x)(x = (13*x + 17) % HASH1_MAX)
#define HASH2(x)(x = (47*x + 7) % HASH2_MAX)
using namespace std;
 
void _strcpy(char *dest, char *src)
{
    while (*src != '\0')
        *(dest++) = *(src++);
    *(dest) = '\0';
}
 
int _strlen(char *input)
{
    int i = 0;
    while (input[i] != '\0')
        i++;
 
    return i;
}
 
int split(char *str)
{
    int ret = 0;
 
    int len = _strlen(str);
    for (int i = 0; i < len; i++)
        ret += str[i] - '0';
 
    return ret;
}
 
typedef struct _INFO_ {
    char key[30];
    int value;
    int h1;
    int h2;
    bool state;
}INFO;
 
INFO info[10002];
 
int main()
{
    for (int user = 1; user <= 5; user++)
    {
        char key[30];
        int value;
        cout << "user[" << user << "]의 key, value를 입력해주세요." << endl;
        cout << "key :: "; cin >> key;
        cout << "value :: "; cin >> value;
 
        int key_int = split(key);
        if (!info[user].state)
        {
            _strcpy(info[user].key, key);
            info[user].value = value;
            info[user].h1 = HASH1(key_int);
            info[user].h2 = HASH2(key_int);
            info[user].state = true;
        }
        cout << endl;
    }
    cout << endl;
 
    for (int i = 0; i < 5; i++)
    {
        char key[30];
        cout << "특정 user의 profile을 찾기위한 key를 입력해주세요." << endl;
        cout << "key :: "; cin >> key;
 
        int key_int = split(key);
        int h1 = HASH1(key_int);
        int h2 = HASH2(key_int);
 
        for (int user = 1; user <= 10000; user++)
        {
            if (info[user].h1 == h1 && info[user].h2 == h2)
            {
                cout << "user :: " << user << endl;
                cout << "key :: " << info[user].key << endl;
                cout << "value :: " << info[user].value << endl;
                cout << "h1 :: " << info[user].h1 << endl;
                cout << "h2 :: " << info[user].h2 << endl;
                break;
            }
        }
        cout << endl;
    }
    cout << endl;
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

이때 적재율이라는 개념이 존재하는데 적재율은 다음과 같이 식으로 표현 할 수 있다. 

적재율 A = n / m

n은 저장된 원소 수, m은 해시 테이블의 크기이다.

이때 A > 0.5라면 클러스터링(Clustering)이 발생할 확률이 높다.

이때 해결 방법은 해시 테이블의 크기를 두배로 늘리고, 새로운 해시 함수를 이용하여 해시 테이블을 재작성 해야한다.

4. 해시의 장/단점

해쉬의 장점은 O(1)에 사용자가 찾고자 하는 value를 삽입 / 검색/ 삭제 할 수 있기에 매우 유용하다.

단점으로는 연속적인 데이터 검색에 있어서는 우리에게는 O(1)의 시간을 나타내지만,

reference of locality에 의해 캐시 미싱이 잦아지기에 불리한점도 있다.

또한 연속적인 데이터 검색에는 비효율적이고 만약 해시 테이블을 재구성해야한다면 새로이 모든것을 만들어야하기에 비효율적인 부분도 있다.

5. 해시관련 문제

[1764번] 듣보잡 :: http://www.crocus.co.kr/605

[12791번] Starman :: http://www.crocus.co.kr/798

[14670번] 병악한 영정 :: http://www.crocus.co.kr/981

[11652번] 카드 :: http://www.crocus.co.kr/1099

[3022번] 식사 예절 :: http://www.crocus.co.kr/1063

[7785번] 회사에 있는 사람 :: http://www.crocus.co.kr/1046

(이외 여러 문제는 아래 링크 참조)

http://www.crocus.co.kr/search/map

http://www.crocus.co.kr/search/맵