Hashing (해싱)

해싱은 임의의 길이의 데이터(키, Key)를 고정된 길이의 데이터(해시값, Hash value)로 변환해 작은 크기의 해시 테이블로 대응(Mapping)시켜 식별하는 하나의 기법입니다. 해시 테이블은 M개의 버킷으로 이루어져 있으며, 이 글에서 다루는 해시값은 해당 키가 저장될 버킷의 번호(해시 테이블의 인덱스)를 나타냅니다.

키에서 해시값을 추출하는 일련의 과정을 해시 함수(Hash function)라고 합니다. 해시 함수는 같은 키에 대해서는 동일한 해시값을, 다른 키에 대해서는 다른 해시값을 추출해야 합니다. 하지만 일반적으로 해싱에서 해시값의 범위(M)는 키의 범위보다 작기 때문에 어떤 이상적인 해시 함수라도 비둘기집의 원리에 의해 서로 다른 두 키가 같은 해시값을 가질 수 있습니다. 이런 경우를 충돌(Collision)이라고 합니다.

비둘기 집의 원리

n+1n+1개의 물건을 nn개의 상자에 넣은 경우, 최소한 한 상자에는 그 물건이 반드시 두 개 이상 들어있다는 원리를 말한다. 보통 비둘기와 비둘기집의 형태로 비유되어 쓰이기 때문에, 비둘기 집의 원리라고 불린다.
더 자세한 내용은 https://brunch.co.kr/@mathian/32 를 참고해 주세요.

해싱이 사용되는 예로 문자열(Key)을 정숫값(Hash value)으로 치환하여 문제를 해결하는 방법이 있습니다. 이에 사용되는 가장 대표적인 해시 함수는 진법을 이용하는 것입니다. "SCPC"이라는 단어가 있다고 하면, 아래와 같이 진법을 이용한 해시 함수를 만들 수 있습니다.

f(key) = ((((key[0]) * 26 + key[1]) * 26 + key[2])) * 26 … key[l – 1])
f("SCPC") = 19 * 26^3 + 3 * 26^2 + 16 * 26^1 + 3 * 26^0 = 336391

해시 함수의 시간 복잡도를 O(H)라고 할 때 해시값의 중복이 없는 이상적인 해싱에서 키의 검색, 삽입, 삭제에는 모두 O(H)의 시간이 걸립니다.
하지만 앞서 말했듯 해시값의 범위가 키의 범위보다 작을 때에는 충돌이 발생할 수밖에 없습니다.
예를 들어 위와 같은 진법 변환을 해시 함수로 사용할 때에는 문자열이 길어지면 해시값이 너무 커지므로 적당히 큰 수로 나머지 연산한 값, 이 글에서는 해시 테이블의 크기 M으로 나머지 연산한 값을 해시값으로 쓸 수 있습니다.
이때 해시값의 M에 대한 나머지가 같은 키끼리는 충돌이 발생합니다.

해시 함수와 마찬가지로 충돌을 제어하는 방법도 다양합니다. 여기에서는 대표적인 충돌 제어 방법 중 하나인 체이닝(Chaining)에 대해서 설명하겠습니다.
체이닝은 충돌한 키들을 보존하기 위해 각 버킷을 리스트 형태로 구현합니다. 최초의 버킷은 모두 원소가 0개인 리스트의 헤더이며, 해당 버킷에 데이터가 추가될 때마다 노드를 추가합니다.
이때 어떤 키가 해시 테이블에 존재하는지 검사하기 위해서는 해당 키의 해시값에 해당하는 버킷이 가진 노드를 모두 순회해야 합니다.
이는 리스트에서 원소를 찾는 연산과 동일하며 이에 기반한 삭제 연산도 같은 선형 시간이 걸립니다.
이때 몇 개의 버킷에만 데이터가 편중되는 최악의 경우 각 연산의 시간 복잡도는 O(H + N)이 됩니다.

이런 상황을 최소한으로 하기 위해서는 해시값의 추출 과정, 즉 해시 함수를 어떻게 구성할 것인지가 핵심이 됩니다.
좋은 해시 함수란 해시값을 추출하는 연산이 빠르되 충돌이 적고 해시 테이블의 영역을 고르게 사용할 수 있어야 합니다.
예를 들어 위에서 다룬 A * pow(B) mod M 형태의 진법 변환을 사용할 때 A의 값을 0이 아닌 1부터 시작하는 것이 좋습니다.
0을 사용하게 되면 "A"와 "AAA"의 해시값이 같아지기 때문입니다. 또한 B와 M이 서로소인 것이 충돌 확률이 낮아 더 좋은 해시 함수가 될 수 있습니다.

글의 첫 부분에서 말했듯 해싱의 핵심은 값의 식별입니다. 그렇기에 원소의 중복을 허용하지 않는 Set이나 Key:Value쌍에서 중복된 Key가 존재하면 안 되는 Map과 같은 자료구조를 구현하는 데에 사용되기도 합니다. 

다음은 C++로 나타낸 코드입니다.

#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;

int main() {
    int n;
    cin >> n;

    unordered_set<string> hash;

    for(int i = 0; i < n; i++) {
        int command;
        string key;
        cin >> command >> key;

        if(command == 1) {
            hash.insert(key);
        } else if(command == 2) {
            hash.erase(key);
        } else {
            if(hash.count(key) == 1) {
                printf("1\n");
            } else {
                printf("0\n");
            }
        }
    }

    return 0;
}

다음은 Java로 나타낸 코드입니다.

import java.util.*;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        HashSet<String> hash = new HashSet<String>();

        for (int i = 0; i < n; i++) {
            int command = sc.nextInt();
            String key = sc.next();

            if (command == 1) {
                hash.add(key);
            }
            else if (command == 2) {
                hash.remove(key);
            }
            else {
                if (hash.contains(key)) {
                    System.out.println("1");
                }
                else {
                    System.out.println("0");
                }
            }
        }
    }
}

다음 시간엔 BFS (너비 우선 탐색) 에 대해 알아보겠습니다.