해쉬 테이블(Hash Table)

Hash Table

저장되는 데이터는 키와 값이 하나의 쌍을 이룬다. 키가 존재하지 않는 값은 저장할 수 없다. 그리고 모든 키는 중복되지 않는다. 가장 쉬운 예로 다세대 주택이나 아파트의 우편함입니다. 우편함의 경우 호수가 키가 되고 우편함에 들어있는 우편물이 값이 됩니다. 자료구조의 테이블은 사전구조라고도 불린다. 더불어 맵이라 불리기도 합니다.

#pragma warning(disable:4996)
 
#include <stdio.h>
 
typedef struct _empInfo
{
    int empNum;    // 직원의 고유번호
    int age;     // 직원의 나이
}EmpInfo;
 
int main(void)
{
    EmpInfo empInfoArr[1000];
    EmpInfo ei;
    int eNum;
 
    printf("사번과 나이 입력: ");
    scanf("%d %d", &(ei.empNum), &(ei.age));
    empInfoArr[ei.empNum] = ei;    // 단번에 저장!
 
    printf("확인하고픈 직원의 사번 입력: ");
    scanf("%d", &eNum);
 
//    ei = empInfoArr[eNum];    // 단번에 탐색!
    printf("사번 %d, 나이 %d \n", ei.empNum, ei.age);
    return 0;
}

범위가 배열의 인덱스 값으로 사용하기에 적당하지 않다. 범위를 수용할 수 있는 매우 큰 배열이 필요하다는 2가지 문제점을 맞이하게 됩니다. 이 2가지 문제를 동ㅅ이 헤갤해 주는 것이 바로 해쉬 함수입니다. 가장 간단한 것은 나머지 연산을 통해서 새로운 값을 만들어 내는 것입니다. 예를 들어 여덟 자리의 수로 이뤄진 직원의 고유번호를 두 자리의 수로 변경합니다. 이러한 해쉬 함수는 넓은 범위의 키를 좁은 범위의 키로 변경하는 역할을 합니다. 직원의 수가 100명을 넘어선다면? 서로 다른 2개의 키가 해쉬 함수를 통과하였는데, 그 결과가 03으로 모두 동일합니다. 이러한 상황을 가리켜 충돌이라고 합니다. 이러한 충돌은 배열의 길이를 늘리는 등의 방법으로 피해야 할 상황이 아닙니다.

좋은 해쉬 함수의 조건

좋은 해쉬 함수는 키의 일부분을 참조하여 해쉬 값을 만들지 않고, 키 전체를 참조하여 해쉬 값을 만들어 낸다. 그에 대한 것은 자릿수 선택 방법과 자릿수 폴딩 방법이 있습니다. 좋은 해쉬 함수의 디자인 방법은 키의 특성에 따라 달라집니다. 때문에 해쉬 함수의 디자인에 있어서 절대적인 방법은 존재하지 않습니다. 키의 특정 위치에서 중복의 비율이 높거나, 아예 공통으로 들어가는 값이 있다면, 이를 제외한 나머지를 가지고 해쉬 값을 생성하는 방법. 자릿수 폴딩은 삼등분 한 것을 접는 것입니다. 이외에도 키를 제곱하여 그 중 일부를 추출하는 방법, 폴딩의 과정에서 덧셈 대신 XOR 연산을 하는 방법 등이 있습니다.

충돌(Collision) 문제의 해결책

충돌이 발생한 그 자리를 대신해서 빈 자리를 찾아야 합니다. 다만 빈자리를 찾는 방법에 따라서 해결책이 구분될 뿐입니다. 선형 조사법과 이차 조사법이 있습니다. 충돌이 발생했을 때 그 옆자리가 비었는지 살펴보고, 비었을 경우 그 자리에 대신 저장하는 것이 바로 선형 조사법입니다. 그런데 이러한 선형 조사법은 충돌의 횟수가 증가함에 따라서 클러스터 현상, 쉬운 표현으로 특정 영역에 데이터가 집중적으로 몰리는 현상이 발생한다는 단점이 있습니다. 단점을 극복하기 위해서 이러한 생각을 근거로 탄생한 것이 이차 조사법입니다.

만약에 그 위치의 슬롯 상태가 EMPTY라면, 데이터가 존재하지 않는다고 판단하여 탐색을 종료하게 됩니다. 반면 DELETED 상태임을 확인한다면 충돌이 발생했음을 의심하여 선형 조사법에 근거한 탐색의 과정을 진행합니다. 선형, 이차 조사법과 같은 충돌의 해결책을 적용하기 위해서는 슬롯의 상태를 DELETED를 포함시켜야 합니다.

이중 해쉬(Double Hash)

해쉬 값이 같으면, 충돌 발생시 빈 슬롯을 찾기 위해서 접근하는 위치가 늘 동일하다. 해쉬 값이 같담면, k가 다르더라도 다음의 순서대로 일정하게 빈 슬롯을 찾게 됩니다. 전형적인 이차 해쉬 함수는 1 + (k%c) 입니다. 먼저 1을 더하는 이유는 2차 해쉬 값이 0이 되는 것을 막기 위해서 입니다. 충돌 발생 이후에 다른 자리를 살피는 상황에서 2차 해쉬 값잉 0이 되면 안되지 않겠는가? 15보다 작은 소수로 c를 결정하는 이유는 가급적 2차 해쉬 값이 1차 해쉬 값을 넘어서지 않게 하기 위함입니다. 소수로 선택했을 때 클러스터 현상의 발생 확률을 현저히 낮춘다는 통계를 근거로 한 것입니다. 1차 해쉬 값이 같아도 2차 해쉬 값은 다릅니다. 그리고 이 2차 해쉬 값을 근거로 2차 해쉬 값의 크기만큼 건너 뛰면서 빈 슬롯을 찾게 되므로, 키가 다르면건너 뛰는 길이도 달라집니다. 실제로 이중 해쉬는 이상적인 충돌 해결책으로 알려져 있습니다.