C 언어 HashTable #02

HashTable #02

자, 이번시간에는 해쉬테이블에 대해 조금만 깊게 들어가보겠습니다.

우리가 저번에 했던 나눗셈 법 은 너무 단순하군요. 아주 이해가 쉽지 않을 수가 없었습니다.

저번시간에 했던 내용을 계속해서 테스트하고 생각을 해보신 분이라면 분명히 이런 생각이 드실 겁니다.

"잠깐만... 해쉬 값이 겹치는데? 서로 다른데이터를 어찌 관리하지?'

맞습니다. 서로 다른 입력 값에 대해 동일한 해시 값, 즉 해시 테이블 내의 동일한 주소를 반환할 경우도 생긴다는 말입니다!.

이것을 우리들은 충돌이라고 부르기도 합니다. 그렇다면 이 충돌을 해결 할 수 있는 방법은 어떤 방법이 있을까요.

사실 모든 문제를 해결 할 수 있는 해시알고리즘은 존재하지 않습니다!. 하지만 이러한 문제점이 일어날 가능성을 줄인 알고리즘은 존재하지요.

그것이 오늘 우리가 함께 알아볼 자리수 접기 입니다.

#자리수 접기

상상의 나라로 가봅시다. 

자 우리는 가로 30cm 세로 5cm 인 도화지를 준비해서 5cm 간격으로 길게 세로줄을 그어 표시를 해줍시다!. 

그렇다면 총 6 칸의 정사각형의 칸이 준비가 되겠지요. 그리고 난 후 정사각형 하나당 임의의 숫자를 하나씩 넣어봅시다. 저는 8, 2, 1, 13, 5, 2 라는 숫자를 집어넣도록 할게요.

모두 작성 하였다면 세로줄을 기준으로 한칸씩 겹쳐서 접어봅시다!. 아래 있는 그림처럼 말이죠.

8 + 2 + 1 + 13 + 5 + 2 = 31

 저 숫자들이 31 이라는 숫자로 접혔습니다.이것을 자리수 접기 라고 부릅니다.

이번엔 문자열을 아스키 코드번호로 바꾸어 적어 보겠습니다.

'H'        'e'        'l'         'l'       'o'

 

72       101      108     108     111

72   +   101   +   108   +   108   +   111   =   500

최종적으로 이 자리수 접기는 문자열을 키로 사용하는 해시 테이블에 아주아주 잘 어울리는 알고리즘 입니다!.

그렇다면 이 간단한 알고리즘을 코드로 작성하도록 해볼게요.

int makeHash( char* key, int keyLength, int tableSize ){
     int hashValue = 0;
     for(int i = 0 ; i < keyLength ; i ++){
          hashValue += key[i];
     }
     return hashValue % tableSize;
}

이렇게 작성해주면 되겠지요?. 아주 간단한 알고리즘 입니다!. 하지만 이 코드에는 문제점이 있었으니..

만약 문자열의 최대 길이를 10으로 제한한다면 10 * 127 = 1270 라는 결과 값이 나옵니다. 그렇다면 우리가 반환할 값은 0 - 1270 까지자리수 밖에 반환을 하지 못한다는 점입니다.

왜 이것이 문제가 되느냐 하면, 예를들어 테이블의 크기가 10000 을 넘어간다고 가정한다면, 나머지 1271 - 10000 까지의 주소는 전혀 활용을 하지 못하게 된다는 것이지요.

결국 0 - 1270 까지 의 주소만 활용이 된단 말입니다. 그렇다면 어찌하면 좋을까요? 테이블의 모든 주소를 모두 활용할 수 있게 해야합니다!.

자 그래서 우리는 이 남은 주소를 모두 활용하기위해 테이블의 크기를 12000 으로 가정합시다.

이 10진수 (12000) 을 2진수로 나타낸다면 10111011100000 라는 값이 나옵니다.

그리고 우리가 문자열의 길이를 10으로 제한한다는 조건을 그대로 받아들여 1270 이라는 숫자를 2진수로 나타낸다면 10011110110 이라는 값이 나옵니다.

10111011100000    -> 14bit

10011110110    -> 11bit

위의 그림처럼 나타낼 수 있겠네요!. 바로 저 비어있는 3칸을 쓸수 있게 밀어주기만 하면됩니다. 바로 비트 연산자로 3칸만 밀어주면 되는거죠!. 

이렇게 말입니다.

int makeHash( char* key, int keyLength, int tableSize ){
     int hashValue = 0;
     for(int i = 0 ; i < keyLength ; i ++){
          hashValue = (hashValue << 3) + key[i];
     }
     return hashValue % tableSize;
}

*물론 이건 정해진 크기에 따른 알고리즘 입니다. 문자열의 제한 길이가 11비트일때만 성립하는 알고리즘 입니다!. *

우리가 이렇게 공부해본 방법에도 아직 원초적인 질문에 대한 대답이 되진 못했습니다. 해시 값이 겹친다는 문제 말입니다.

예를들어 위 조건과 동일하다고 가정하고 "WJLY" 를 입력해도 10871 이라는 해시값이 나오고, "SZSR" 을 입력해도 10871 을 반환하게 됩니다. 

키값은 다른데 값이 겹치는 문제는 여전하다는 말입니다. 그래서 우리는 다음 파트에서 본격적으로 충돌을 해결 하도록 할것입니다. 

바로 체이닝 이라는 방법을 통해서 말이죠.

#체이닝

해시 테이블의 충돌을 해결하는 방법은 크게 두가지가 있습니다.

1. 해시 테이블의 주소 바깥에 새로운 공간을 할당하여 문제를 수습하는 개방 해싱.

2. 반대인 폐쇄 해싱

체이닝은 해시 함수가 서로 다른 키에 대해 같은 해시값이 발생할 때 문제를 해결 할수 있는 방법 입니다. 체이닝은 충돌이 일어나면 리스트에 사슬처럼 엮는다는 의미에서 붙여진 이름이지요.

아래 그림처럼 생각하시면 됩니다!. 감이 오시나요? 값이 겹친다면 또다른 방을 연결하고 또 연결하는 방법론 입니다. 체이닝은 개방 해싱 방법론 이라고 하지요.

0 , 1, 3 은 신경쓰지 마시고 봐주시길바래요!...

자... 본격적으로 코드를 작성해보기 전에 모르시는 분들을 위해 요정도만 짚고 넘어가면 좋을 것 같습니다.

(에디터를 어떤걸 써야 보기 편하실지 모르겠네요 ㅎㅎ..)

typedef struct _Node{

    char* key;

    char* value;

    _Node *next;

} Node;

//

typedef Node * List;

typedef struct _HashTable{

    int tableSize;

    List *table;

} HashTable;

typedef Node * List; 

라는 코드의 의미는 우리가 작성해야할 내용이 리스트로 연결을 했기에, Node 라는 자료형을 List 라고 부르겠다 라는 의미입니다.

#체이닝 코드 구현

Header.h

(빨간줄은 신경쓰지 않으셔도됩니다 ㅜㅜ 다음번엔 좀더 보기편하시게 하는 방법을 찾아볼게요)

typedef struct _Node{ //노드 구조체를 정의 했어요.

    char* key; //그 전에는 address 라는 변수이름을 사용하였어요.

    char* value; //[key] 에 저장된 값을 의미합니다.

    _Node *next; //중복된 값을 연결할 노드입니다.

} Node;

typedef Node * List; //그냥 Node 를 List 라고 별칭을 지어줬다~ 라고 생각하시면 됩니다. 링크드 리스트를 이용한다고 했었죠.

typedef struct _HashTable{ //첫 시간에 알아본 구조체와 같은 구조체입니다.

    int tableSize;

    List *table;

} HashTable;

int makeHash(const char* key, int keyLength, int tableSize){ //해쉬값을 만들어주는 함수입니다.

    int hashValue = 0;

    for(int i = 0 ; i < keyLength ; i++){

        hashValue = (hashValue << 3) + key[i]; //3비트씩 밀어줍니다. (강제로 15비트를 만들어주기 위함이에요.)

    }

    

    hashValue = hashValue % tableSize;

    return hashValue; //변형된 해쉬값.

}

HashTable *createHashTable(int tableSize){ //해쉬테이블을 만들어주는 함수입니다.

    HashTable *hashTable = (HashTable*)malloc(sizeof(HashTable)); //크기만큼 할당해줍니다.

    hashTable->table = (List*)malloc(sizeof(List) * tableSize); //동일하게 * tableSize 만큼 할당해 주었구요.

    memset(hashTable->table, 0, sizeof(Node) * tableSize); //memset -> 메모리를 비워주는 역할을 합니다.

    hashTable->tableSize = tableSize;

    

    return hashTable; //만들어진 해쉬테이블을 반환합니다.

}

Node *createNode(const char* key, const char* value){ //각 테이블마다 존재해야할 노드를 만드는 함수입니다.

    Node * newNode = (Node*)malloc(sizeof(Node)); //메모리 할당해줍니다.

    newNode->key = (char*)malloc(sizeof(char) * (strlen(key) + 1)); //받은 [key(char) * 문자길이] 만큼 공간을 할당합니다.

    strcpy(newNode->key, key); //문자열 카피 함수를 이용하여 넣어주었습니다.

    newNode->value = (char*)malloc(sizeof(char) * (strlen(value) + 1)); //받은 value 만큼 공간을 할당합니다.

    strcpy(newNode->value, value); //문자열 카피 함수이용.

    newNode->next = NULL; //당장은 중복된 값이 없으니 NULL 로 자리를 비워놓습니다.

    

    return newNode; //만들어진 노드를 반환합니다!.

}

void destroyNode(Node *node){ //노드의 메모리를 해제시켜주는 함수.

    free(node->key);

    free(node->value);

    free(node);

}

void valueSet(HashTable *hashTable,const char* key,const char* value){ //값을 set 해주는 함수입니다!

    int keyLen = strlen(key);

    int address = makeHash(key, keyLen, hashTable->tableSize); //해쉬값을 만들어줍니다! 그전에했던 내용과 동일하죠.

    Node* newNode = 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; //그리고 그 자리에 노드를 넣습니다.

    }

}

char* getValue(HashTable * hashTable, const char* key){ //key 값으로 value 를 반환하는 함수입니다!

    int address = makeHash(key, strlen(key), hashTable->tableSize); // 받은 해쉬테이블과 key 값으로 해쉬값을 만들어준 후

    List list = hashTable->table[address]; //따로 변수를 만들어 저장해놓습니다.

    List target = NULL; //key 값이 동일한 Node를 의미합니다. 즉 반환될 녀석입니다.

    if(list == NULL) return NULL; //리스트에 아무것도 없다면 NULL 을 반환합니다.

    

    while(1){ //동일한 key 값을 찾을때까지 반복할겁니다!.

        if(strcmp(list->key, key) == 0){ //동일한 key 값이라면?...

            target = list; //NULL 이었던 target에 list 를 넣어준 후..

            break; //반복문을 빠져나갑니다.

        }

        if(list->next == NULL) return NULL; //만약 위 조건에 걸리지 않는다면 이것부터 검사를 하겠죠?. 연결된 링크가 없다는것을 의미!.

        else{ // 그게아니라면 연결된 다른 리스트를 조사할겁니다!.

            list = list->next;

        }

    }

    

    return target->value; //결국 어찌되엇건, 반복문을 빠져나와 값을 반환할것입니다!.

}

void destroyList(List list){

    if(list == NULL){ //리스트가 이미 비어있거나, 삭제를 모두 완료하였다면 끝나게됩니다.

        return;

    }

    if(list->next != NULL){ //값이 비어있지않다면

        destroyList(list->next); //본인을 다시부릅니다. 재귀함수라고 하지요.

    }

    destroyNode(list); //결국 하나씩 순차적으로 삭제됩니다.

}

void destroyHashTable(HashTable *hash){ // 해쉬테이블을 삭제합니다.

    for(int i = 0 ; i < hash->tableSize ; i ++){ //size 만큼 반복해야하겠죠!...

        List list = hash->table[i];

        destroyList(list); // 0번..부터 tableSize 까지 존재하는 모든 노드를 삭제할겁니다... 설명하기가 힘드네요.

    }

}







소스.cpp

int main(int argc, const char * argv[]) {

    

    HashTable *hashTable = createHashTable(12289); //12289 크기만큼의 해쉬테이블 생성!.

    valueSet(hashTable, "MSFT", "Microsoft Corporation");

    valueSet(hashTable, "JAVA", "Sun Microsystems");

    

    valueSet(hashTable, "APAC", "Apach Org"); // ZYMZZ 와 충돌합니다!

    valueSet(hashTable, "ZYMZZ", "Unisys Ops Check"); // APAC 와 충돌합니다!

    

    cout << getValue(hashTable, "MSFT") << endl;

    cout << getValue(hashTable, "JAVA") << endl;

    

    cout << getValue(hashTable, "APAC") << endl;

    cout << getValue(hashTable, "ZYMZZ") << endl;

    

    return 0;

}

결과