[자료구조] 해시 테이블 충돌 해결 기법 - 코딩밥상

해시 충돌 해결 기법

해시 테이블의 충돌을 해결하는 방법에는 크게 두 가지가 있습니다. 하나는 해시 테이블의 주소 바깥에 새로운 공간을 할당하여 문제를 수습하는 것이고, 또 다른 하나는 처음에 주어진 해시 테이블의 공간 안에서 문제를 해결하는 것입니다.

전자는 개방 해싱(Open Hashing)이라고 하고, 후자는 폐쇄 해싱(Closed Hashing)이라고 합니다.

---

체이닝(Chaining) 이란?

체이닝이란 충돌이 발생하면 각 데이터를 해당 주소에 있는 링크드 리스트에 삽입하여 문제를 해결하는 기법입니다.

체이닝이라는 이름은 충돌이 일어날 때마다 데이터를 링크드 리스트에 사슬처럼 엮는다는 의미에서 붙여진 것입니다.

 

체이닝 기반 해시 테이블은 데이터 대신 링크드 리스트에 대한 포인터를 관리하고 데이터는 해시 테이블의 각 요소가 가리키는 링크드 리스트에 저장됩니다.

삽입 연산은 앞으로 발생할 충돌을 고려해서, 삭제 연산과 탐색 연산은 이미 발생한 충돌을 고려해서 설계되어야 합니다.

 

 

 

 

 

 

 

 

 

-구조체

typedef char* KeyType;
typedef char* ValueType;

typedef struct tagNode{ //노드 구조체
    KeyType Key;    //주소로 사용할 데이터
    ValueType Value;    //저장할 데이터
    
    struct tagNode* Next;
} Node;

typedef Node* List;
typedef struct tagHashTable{    //해시 테이블 구조체
    int TableSize;
    List* Table;
} HashTable;

-탐색 연산

앞으로 '발생할 충돌'을 고려해서 설계되어야 합니다.

1. 찾고자 하는 목표값을 해싱하여 링크드 리스트가 저장된 주소를 찾는다.
2. 이 주소를 이용하여 해시 테이블에 저장된 링크드 리스트에 대한 포인터를 생성한다.
3. 링크드 리스트의 앞에서부터 뒤까지 차례대로 이동하며 목표값이 저장되어 있는지 비교한다. 목표값과 링크드 리스트 내 노드값이 일치하면 해당 노드의 주소를 반환한다.

ValueType CHT_Get(HashTable* HT, KeyType Key){  //탐색 연산
    int Address = CHT_Hash(Key, strlen(Key), HT->TableSize);
    
    List TheList = HT->Table[Address];
    List Target = NULL;
    
    if(TheList == NULL) return NULL;
    
    while(true){	//해당 리스트 찾고 목표 노드 찾기
        if(strcmp(TheList->Key, Key) == 0){	
            Target = TheList;
            break;
        }
        
        if(TheList->Next == NULL) break;
        else TheList = TheList->Next;	
    }
    
    return Target->Value;
}

-삽입 연산

체이닝 기반 해시 테이블의 삽입 연산도 탐색 연산과 비슷한 원리로 작동합니다. 먼저 해시 함수를 이용하여 데이터가 삽입될 링크드 리스트의 주소를 얻고, 링크드 리스트가 비어 있으면 바로 삽입하고 그렇지 않다면 헤드 앞에 삽입합니다.

여기서 궁금할 것은 왜 테일이 아닌 헤드에 삽입을 하냐는 것입니다.

만약, 해시 충돌이 일어나 해당 링크드 리스트의 테일에 삽입한다면, '순차 탐색'을 수행한 후 리스트의 테일을 찾아 그 곳에 데이터를 삽입 할 것입니다. 하지만 테일이 아닌 헤드에 삽입한다면, 순차 탐색의 과정 없이 곧바로 리스트의 가장 앞에 삽입하면 되기때문에 해시 테이블의 성능이 쓸데없이 저하되는 일을 막을 수 있는것입니다.

void CHT_Set(HashTable* HT, KeyType Key, ValueType Value){
    int Address = CHT_Hash(Key, strlen(Key), HT->TableSize);
    Node* NewNode = CHT_CreateNode(Key, Value);
    
    if(HT->Table[Address] == NULL){	//해당 리스트가 비어있다면, 그대로 삽입
        HT-> Table[Address] = NewNode;
    }
    else{	//리스트의 헤드로 삽입
        List L = HT->Table[Address];
        NewNode->Next = L;
        HT->Table[Address] = NewNode;
    }
}

 

체이닝의 성능 향상 

체이닝은 원하는 데이터를 찾기 위해 순차 탐색을 해야 하는 링크드 리스트의 단점을 그대로 갖고 있습니다.

이는 앞서 배운 레드 블렉 트리와 같은 이진 탐색 트리를 사용하면 성능을 향상할 수 있겠네요.

따라서 해시 함수의 성능이 아주 좋아서 충돌이 거의 없다면 모르겠지만, 충돌이 잦다면 해시 테이블과 이진 탐색 트리의 결합은 아주 훌륭한 선택이 됩니다.

---

개방 주소법(Open Addressing)

개방 주소법은(Open Addressing)은 충돌이 일어날 때 해시 함수에 의해 만들어진 주소가 아니더라도 얼마든지 다른 주소를 사용할 수 있도록 허용하는 충돌 알고리즘입니다. 충돌이 일어나면 해시 테이블 내의 새로운 주소를 탐사하여 충돌된 데이터를 입력하는 방식으로 동작합니다.

개방 주소법은 탐사가 전부이며, 따라서 탐사 작업을 어떻게 할 것인가에 관한 내용을 정리해 보겠습니다.

 

-선형 탐사

충돌이 발생한 경우 현재 주소에서 고정 폭으로 주소를 이동합니다. 그 주소에도 다른 데이터가 있어 충돌이 발생하면 또 고정 폭으로 그 다음 주소로 이동하면서 비어 있는 주소를 찾을 떄까지 즉 충돌이 일어나지 않을 때까지 탐사합니다.  

 

선형 탐사를 쓰다 보면 충돌할 뻔한 데이터들이 한 곳에 모이게 되는 클러스터(Cluster)가 발생할 확률이 큽니다. 클러스터 현상이 발생하면 새로운 주소를 찾기 위해 수행하는 선형 탐사 시간이 길어지고 이로 인해 해시 테이블의 성능은 저하됩니다.

이러한 문제를 개선할 알고리즘이 제곱 탐사입니다.

-제곱 탐사

제곱 탐사의 기본적인 개념은 선형탐사와 같습니다. 선형 탐사가 다음 주소를 찾기 위해 고정폭만큼 이동하는 것에 비해 제곱 탐사는 이동폭이 제곱수로 늘어나는 것이 다를 뿐입니다.

충돌이 일어난 횟수의 제곱만큼의 폭으로 다음 주소를 이동하는 방법입니다. 예를들어 첫 충돌에서는 1의 제곱은 1이기에 다음 주소로 이동하고 이동했는데도 충돌이 발생한 경우 2의 제곱인 4만큼의 폭으로 이동하고 또 충돌이 발생한 경우 3의 제곱인 9만큼의 폭으로 이동하는 패턴입니다.

 

선형 탐사와 제곱탐사는 규칙성을 갖습니다. 이 규칙성에 의해 각각 다른 종류의 클러스터가 발생합니다. 그 이유는 하나의 주소에서 충돌이 발생할 때 탐사할 위치가 정해져 있기 때문입니다. 

그렇다면 이러한 문제를 해결하기 위해서는 규칙성을 없애면 됩니다.

-이중 해싱

탐사 주소의 규칙성을 없애는 방법 중 대표적인 방법이 이중 해싱입니다. 이는 이동폭을 또 다른 해시 함수로 계산하는 방법입니다.

즉 2개의 해시 함수를 준비해서 하나는 최초의 주소를 얻을 때, 또 다른 하나는 충돌이 일어날 때 탐사 이동폭을 얻기 위해 사용하는 것입니다. 이렇게 한다면 탐사 이동폭의 규칙성은 없애면서 같은 키에 대해서는 항상 똑같은 결과를 얻을 수 있습니다.

 -재해싱

아무리 성능이 뛰어난 충돌 해결 알고리즘이라도 해시 테이블의 여유 공간이 모두 차버려서 발생하는 성능 저하는 막아낼 방법이 없습니다.재해싱은 이 문제를 해결할 수 있는 방법 중 하나입니다. 

그 방법은 해시 테이블의 크기를 늘리고 늘어난 해시 테이블의 크기에 맞춰 테이블 내의 모든 데이터를 다시 해싱합니다.

 

통계적으로 해시 테이블의 공간 사용률이 70~80%에 이르면 성능 저하가 나타나기 시작합니다. 그러므로 공간 사용률이 이보다 적은 수준일 때 미리 재해싱해둬야 성능 저하를 막을 수 있습니다. 하지만 재해싱 역시 만만치 않은 오버헤드를 수반하기에 재해싱을 수행할 임계치를 너무 낮게 잡으면 빈번하게 재해싱을 유발하고 결국 성능 저하를 일으키므로 임계치를 75% 수준으로 설정하는 것이 일반적입니다.