[Data Structure] 해시 테이블(Hash Table)

리스트 기반의 이진 탐색 트리의 경우,  특정 데이터의 검색의 시간복잡도는 O(logn)이다. 매 탐색에서 전체 데이터를 절반으로 나눠서 검색을 행하기 때문이다.

 

하지만 우리는 여기서 아쉬움을 느낀다. 배열의 경우 주소인 이름으로 접근해서 인덱스로 주소를 계산해서 접근하기 때문에, 임의 접근이 가능하면서 상수의 시간복잡도를 가진다. 우리는 이 장점을 활용할 방법이 없을까?

 

답은 바로 해시 테이블에 있다.

 

해시 테이블이 무엇인지 알기 위해 우선 해시에 대한 정의를 알아야 한다.

 

단어의 뜻을 찾아보면 다음과 같은 문장들을 확인할 수 있다.

 

 

• If you make a hash of a job or task, you do it very bably.
• Hash is a dish made from meat cut into small lumps and fried with other ingredients such as onions or potato.
• Hash is hashish.

각각의 해석은 다음과 같다.

 

• 당신이 어떤 일 또는 작업을 해시로 만든다는 것은, 그 일을 망쳐놓는다는 의미이다.
• 잘게 자른 고기를 양파나 감자와 같은 다른 재료와 함께 튀겨 한 덩어리로 만든 요리.
• 해시는 해시시(대마의 잎으로 만든 마약)이다.

 

우리는 두 번째 해석에 주목할 필요가 있다. 원재료인 고기를 다른 재료와 함께 다지고 섞어서 완전히 새로운 형태의 요리로 만드는 것처럼 해시 테이블의 해시는 데이터를 입력 받으면 완전히 다른 모습의 데이터로 바꾸어 놓는 작업이다.

 

또한 해시는 비단 해시 테이블 뿐만 아니라 암호화나 데이터 축약의 부분에서도 사용이 된다.

 

---

1. 공간적 절약을 버리고 시간적 절약을 사다.

 

해시 테이블은 일반적인 자료구조보다 훨씬 더 많은 크기를 차지한다. 정확하게 말하자면 해시 테이블은 주어진 공간이 가득 차서는 안된다.

 

해시 테이블의 성능은 해시 테이블이 할당 받은 공간의 데이터가 가득 차지 않고 일정 부분 비어 있을 때 가장 효율적인 성능을 가진다. 때문에 필요한 용량보다 늘 더 많은 공간을 할당 받아야 한다. 이 때문에 공간적인 효율성은 버리게 되지만 반대로 시간적인 효율성을 얻게 되는 것이다.

 

 

2. 입력 받은 데이터가 바로 주소값으로 변한다.

 

해시 테이블은 해시 함수라고 하는 함수를 통해 입력 받은 데이터를 변화시켜 테이블 내의 주소값으로 전환한다. 이를 통해 데이터를 통해 검색이 가능하고 해당 검색은 배열의 인덱스 번호를 반환하기 때문에 상수 시간 내의 접근이 가능하다.

 

해시 함수의 역할

해시 함수를 통해 123817이라는 데이터는 3819라는 해시값으로 변환되고 이 3819라는 값이 123817이 해시 테이블에 저장될 때의 인덱스 주소가 된다.

 

즉, 검색을 할 때도 123817을 검색하면 자동으로 해시 함수를 통해 3819의 값이 나오고 그 주소로 바로 접근이 되는 것이다. 해시 함수의 장점은 데이터를 입력 받을 때 같은 데이터는 반드시 같은 해시값을 반환한다는 점이다.

 

이 작업을 위해서는 해시 테이블을 구성할 때, 일정한 데이터 공간을 미리 할당 받아야 하며 그 다음 해시 함수를 구현하여 값이 입력이 될 때 해시 함수를 통해 해시 값을 도출한다.

 

---

해시 함수

 

그렇다면 해시 테이블의 핵심을 구성하는 해시 함수는 어떻게 구현되어 있을까? 대표적인 두 가지 방법이 있는데 하나는 나눗셈법이고 나머지 하나는 자릿수 접기이다.

 

 

1. 나눗셈법

 

나눗셈법은 말 그대로 입력되는 데이터를 일정 값(예를 들면 테이블의 크기)으로 나누고, 그 몫을 취하는 형식이다. 예를 들어 418이라는 값이 입력이 되고 이 값을 이 테이블의 전체 크기가 193일 때, 193으로 나누면 2의 몫이 나오고 나머지는 32가 된다. 이때 32가 418의 인덱스 번호가 되는 것이다.

 

구현하는 방법도 아주 간단하다.

 

int Hash(int data, int TableSize)
{
    return data % TableSize;
}

 

이런 식으로 간단한 해시 함수가 탄생했다.

 

나눗셈법으로 해시 함수를 구성할 때, 가장 효율적인 테이블의 크기는 바로 2의 제곱수에서 가장 멀리 떨어진 소수이다. 쉽게 설명하면 각 2의 제곱수 가운데 정도에 있는 소수가 효율적인 크기라는 말이다.

 

나눗셈법은 단순해서 사용하기 편한 알고리즘이다. 하지만 단점이 분명히 존재한다. 서로 다른 값에서도 같은 해시값을 반환할 확률이 높다는 점이다.

 

위에서 예로든 418이라는 값이 193의 크기를 가진 해시 테이블에 입력이 될 때의 주소는 32이다. 하지만 이후에 611이라는 값이 입력이 되면 어떻게 될까?

 

똑같이 나머지를 반환하면 32가 된다. 즉 418의 주소와 겹치게 된다. 이렇게 서로 다른 데이터가 동일한 해시값을 반환하게 되는 것을 충돌이라고 한다.

 

만약 충돌이 일어나지 않더라도 해시값이 테이블 특정 구역이 모이는 현상이 발생할 수도 있는데 이것을 클러스터(Cluster)라고 한다.

 

 

2. 자릿수 접기

 

 

때문에 좀 더 복잡한 알고리즘의 필요성이 생기게 되고 다음으로 많이 사용되는 것이 자릿수 접기이다.

 

자릿수 접기는 쉽게 생각하면 수를 각 자릿수로 나눈 다음 그 숫자를 더하는 것이다. 245873이라는 데이터가 입력이 된다고 가정을 해보면 각 자릿수를 전부 1의 자리로 생각한 다음 더하면 해시값이 나온다.

 

즉, 2 + 4 + 5 + 8 + 7 + 3 = 29가 되므로 245873의 인덱스 번호는 29이다. 좀 더 복잡하게 하고 싶다면 자릿수를 두 자리나 혹은 세 자리로 변경해서 하는 방법도 있다.

 

물론 이 방법 또한 충돌이 쉽게 일어나지만 이 방법의 큰 장점은, 바로 문자열에 대한 해시값 반환이 가능하다는 점이다. 문자는 ASCII 코드 같이 정수형 값이 존재한다. 각 문자를 변환하여 자리를 더하면 쉽게 해시값을 찾을 수 있다.

 

간단하게 코드로 구현하면 다음과 같다.

 

int Hash(const std::string& key, int TableSize)
{
    int HashValue = 0;
    
    for(auto it = key.begin(); it != key.end(); ++it)
    {
        HashValue += (int)(*it);
    }
    
    return HashValue % TableSize;

}

 

하지만 문제가 생기게 되는데 10자리의 문자열을 해시 함수로 돌릴 경우 0에서 1270 사이의 주소만 반환하게 된다. 하지만 문자열의 가짓수를 경우의 수로 나타내면 무려 조를 넘어 경의 단위까지 가게 되는데 심각한 문제가 아닐 수 없다.

 

이 경우를 해결하는 방법을 알기 위해선 테이블의 전체 크기의 비트 수와, 입력되는 문자열의 비트 수 차이를 계속해서 밀어주는 것으로 해결이 된다.

 

---

충돌 해결

 

앞서 이야기했듯, 해시 함수는 완벽하지 않기 때문에 충돌 혹은 클러스터 현상이 발생할 수 있다. 이런 경우를 최대한 줄이기 위한 다양한 방법이 고안되었는데, 그 중 몇 가지를 설명하고자 한다.

 

 

1. 체이닝

 

체이닝은, 이름에서 알 수 있듯이 해시 테이블의 인자로 노드를 사용하여 링크드 리스트를 형성하게 하는 방법이다. 이름 대로 노드 사이의 체인 관계를 형성하여 같은 해시값이어도 데이터를 저장할 수 있게 만드는 방법이다.

 

단순하게 생각하여, 해시값을 획득하고, 해당 주소에 이미 데이터(노드)가 있을 경우, 해당 노드의 앞에 추가하는 노드를 삽입하는 방법이다.

 

뒤에서 삽입하는 방법도 있겠지만, 어차피 탐색에서 순차 탐색을 행하기 때문에 O(N)의 복잡도를 가지는데 삽입에서도 굳이 그런 리스크를 짊어질 필요가 없기 때문에 앞에서 삽입을 하는 것을 추천한다.

 

 

체이닝 해시 테이블

 

해시 함수를 수정할 필요는 없다. 단순히 삽입 데이터를 링크드 리스트의 노드로 받으면 되는 것이다. 이 경우, 삽입 연산은 앞으로 충돌이 발생할 가능성에 대해서, 삭제와 탐색은 이미 충돌이 발생했을 경우를 고려해서 설계해야 한다.

 

하지만 결국엔 체이닝을 사용하게 되면 링크드 리스트의 단점인 순차 탐색을 통한 속도 저하를 고스란히 가져가야 한다. 여기서 더 성능을 올리기 위해선, 각 인덱스에 삽입 되는 링크드 리스트가 이진 탐색 트리를 형성하게 만드는 것이다. 이 경우 해시 함수의 성능이 좋지 않아 충돌이 잦게 발생한다면 더욱 필요하다.

 

 

2. 개방 주소법

 

다음의 방법은 개방 주소법이다. 충돌이 일어날 때, 해시 함수에 의해 얻어진 주소가 아니더라도 얼마든지 다른 주소를 사용할 수 있도록 허용하는 충돌 해결 알고리즘이다. 그 방법은 또 다시 몇 가지로 나뉘는데 다음과 같다.

 

1. 선형 탐사 - 해시 함수로부터 얻어낸 주소에서 충돌이 발생할 경우, 고정 폭(예를 들면 1)으로 주소를 증가시켜서 데이터를 저장한다. 하지만 이 경우 고정 폭을 이루는 주소끼리의 클러스터를 형성할 확률이 매우 높다.
2. 제곱 탐사 - 선형 탐사에서 좀 더 발전한 알고리즘으로, 고정 폭이 아니라 제곱수로 증가하는 것이다. 첫 충돌에는 1, 다음 충돌에는 2, 그 다음 충돌에는 4로 2의 제곱수로 증가한다. 이 경우 서로 다른 해시값을 가지는 데이터에 대해서는 클러스터가 형성되지 않도록 하는 효과가 있지만, 같은 해시값을 가지는 데이터에 대해서는 2차 클러스터가 발생할 확률이 높다.
3. 이중 해싱 - 이름대로 충돌이 발생하였을 경우, 다른 해시 함수를 통해 해싱하여 해시값을 반환하도록 한 다음, 충돌했던 주소에 더해주는 방식을 사용한다.

 

재해싱

 

해시 알고리즘의 효과가 좋다고 하더라도 결국 테이블을 채우면 채울 수록 해시 테이블의 성능은 저하한다. 때문에 일정 비율을 넘어서게 되면 원래 크기보다 더 큰 크기를 할당하여 재해싱하여야 한다.

 

통계적으로는 공간 사용률이 70~80%에 이르면 성능 저하가 나타나기 시작한다고 한다. 때문에 이 전에 재해싱을 통해 공간을 새로 할당해야 하지만 결국 공간을 새롭게 할당하는 작업이기 때문에 만만치 않은 오버헤드를 요구한다.

 

그래서 임계치를 너무 낮게 잡으면 오히려 성능 저하가 더 심하게 날 수 있으므로 재해싱의 임계치는 70과 80의 중간인 75%를 사용하는 것이 보통이다.