*해쉬(hash)의 사전적 의미는 "잘게 자른 고기를 양파나 감자와 같은 다른 재료와 함께 튀겨 한 덩어리로 만든 요리", 여기서는 데이터를 입력받으면 해시함수를 통해 다른 형태로 데이터를 얻는다 정도 생각하자.
*데이터를 담을 테이블을 미리 크게 확보한 후, 입력받은 데이터를 해시하여 테이블 내의 주소를 계산하고 이 주소에 데이터를 담는 것, 이것이 해시 테이블의 기본 개념이다.
여러 해시함수를 살펴보자.
1.나눗셈법
-해시함수 중에서도 가장 간단한 방법이다. 입력값을 테이블 크기로 나누고, 그 나머지를 인덱스로 활용하는 방법이다.
-2의 제곱수 사이에 있는 소수를 테이블 크기로 활용했을때 가장 성능이 좋다.
예제를 보자.
typedef struct tagNode{
KeyType Key;
ValueType Value;
} Node;int Hash(char *key , int keyLength , int tableSize){
int i = 0;
int hashValue = 0;
for(int i = 0 ; i < keyLength ; i ++ ) {
hashValue += key[i];
}
return hashValue % tableSize;
}*그러나 자리수 접기는 문자열의 길이에 따라 테이블에 저장되는 범위가 한정되어버리는 문제가 있다. 문자열의 길이가 10이고 테이블 길이가 10000이라면,
10 * 127(아스키코드) 만큼밖에 못쓰게 되어 나머지 테이블 공간은 낭비되는 것이다.
*2진수로 살펴보면, 안쓰는 상위비트가 존재하는 것인데, 이를 쓰게 하면 된다.
int Hash(char *key , int keyLength , int tableSize){
int i = 0;
int hashValue = 0;
for(int i = 0 ; i < keyLength ; i ++ ) {
hashValue = (hashValue <<3 ) + key[i];
}
return hashValue % tableSize;
}*루프를 돌 때마다 3비트씩 쉬프트하여 이론적으로는 모든 테이블 내 주소를 활용하여 저장할 수 있게 된다.
*어떤 해시 함수도 충돌(collision)을 피할 수 없다. 그럼 충돌을 어떻게 해결할까?
체이닝(Chaining)
해시 함수가 서로 다른 키에 대해 같은 주소값을 반환해서 충돌이 발생하면 각 데이터를 해당 주소에 있는 링크드 리스트에 삽입하여 문제를 해결한다.(링크드리스트에 사슬처럼 주렁주렁 달리기 때문에 체이닝이라는 이름이 붙었다.)
체이닝 기법을 적용했을때 key값으로 어떻게 value값을 가져오는지(탐색하는지) 예제를 보자.
ValueType CHT_Get(HashTable *hashTable , KeyType key){
/* 1.먼저 주소를 해싱한다. */
int address = CHT_Hash(key , strlen(key), hashTable->size); //문자열 해싱
/* 2. 해싱한 주소에 있는 링크드 리스트를 가져온다. */
List theList = hashTable->Table[address];
Node* target = NULL;
if(theList == NULL){
retrun NULL;
}
/* 값을 찾을 때 까지 순차탐색을 한다. */
while (1){
if( strcmp(theList->key , key) == 0 ){
target = theList;
break;
}
if( theList->Next == NULL )
break;
else
theList = theList->Next;
}
return target->value;
}*탐색 예제를 보면 알겠지만 체이닝 기반 해쉬테이블의 삽입 또한 비슷하게 동작한다. 먼저 key값으로 hashing하여 주소값을 얻어낸다. 해당 index가 비어있으면 데이터를 바로 삽입하고, 그렇지 않으면 '헤드 앞에' 삽입한다.(굳이 tail까지 찾아서 넣을 필요가 있는가? 어차피 순차 탐색인데)
*삽입 예제까지만 살펴보자.
void CHT_Set(HashTable* hashTable , KeyType key , ValueType value){
int address = CHT_Hash(key , strlen(key) , hashTable->size);
Node *newNode = CHT_CreateNode(key , value);
/*해당 주소가 비어있다면 */
if(hashTable ->table[address] == NULL ) {
hashTable->table[address] = newNode;
}
else{
List list = hashTable->table[address];
newNode->Next = list;
hashTable->table[address] = newNode;
}
}*체이닝은 필연적으로 링크드리스트의 순차탐색에 의존한다. (충돌이 일어나지 않았다면 해시기법은 O(1), 상수시간의 탐색 성능을 보장하는데..)
*그래서 링크드리스트가 아닌 이진탐색트리와 해시테이블의 조합을 쓰면 성능이 올라간다.(충돌이 더 잘 일어날수록...)
개방주소법
개방주소법은 충돌이 일어날 때 해시함수에 의해 얻어진 주소가 아니더라도, 다른 주소를 사용할 수 있도록 허용하는 충돌 해결 알고리즘이다.
*선형탐사는 간단하다. 데이터를 저장할 위치에 충돌이 발생하면, 비어있는 곳을 발견할 때 까지 계속 +1 하여 찾는것이다.
*다만 매우 높은 확률로 군집(clustering)현상이 일어난다.
*제곱탐사는 선형탐사가 빈 곳을 찾기위해 고정폭만큼 이동한다면, 제곱탐사는 이동폭의 제곱수로 늘어나는것 뿐이다.
*그러나 제곱탐사 역시 '제곱수의 폭'으로 이동한다는 규칙으로 인해 선형탐사만큼은 아니지만 클러스터링이 발생한다.
*그렇다면 이러한 규칙성을 없애버리면 클러스터링이 없어지지 않을까?
이중해싱(Double Hashing)
해시 함수에 키를 입력하여 얻어낸 주소에서 충돌이 일어난다면, 이동폭을 제 2의 해시함수로 계산하는 것이다. 2개의 해시함수를 사용하여 하나는 최초의 index를 얻기 위함이고, 두번째는 충돌이 발생할 경우 이동폭을 얻기 위해 사용하는 것이다.
재해싱(Rehashing)
이중해싱은 뛰어난 충돌해결법을 보이지만, 데이터가 가득 차 버려 여유공간이 얼마 없는 해쉬테이블의 충돌은 당해낼 재간이 없다. 재해싱이란 해시 테이블의 크기를 늘리고, 늘어난 해시 테이블의 크기에 맞추어 테이블 내의 모든 데이터를 다시 해싱한다.
통계적으로는 해시테이블의 공간 사용률이 70~80% 이르면 성능저하가 나타나기 시작한다. 그러나 재해싱 또한 오버헤드가 만만치 않으므로 75%정도 임계치를 잡는게 보통이다.