C언어 HashTable #03

HashTable #03

우리는 리스트를 이용한 체이닝을 구현 하였습니다. 보기에 큰 문제점은 없어 보이지만 해시의 장점 중 하나를 놓치게 되지요.

바로 해시의 탐색 장점을 활용하지 못하는 부분이 있다는 말입니다.

키를 이용해 값을 찾는 행위를 반복 중일 때, 키에 따른 해시값이 리스트에 의해 줄줄이 이어져 있다면 우리는 여전히 몇개가 될지 모르는 리스트들을 하나씩 차례로 확인해야하는 상황이 발생합니다.

키를 이용해 바로 접근이 용이한 해시 테이블에서는 아주 효율적 이지 못하다고 볼 수 있지요.

우리는 이제 이중 해싱 에 대하여 알아볼 겁니다.

#이중 해싱

해시 알고리즘을 이용해 주소 값을 낼 때 그 자리에 어떤 값이 이미 존재한다면, 어찌해야할까요? 저번 시간에 했던 것 처럼 리스트로 줄줄이 이어야할까요? 어찌 이어 가든지 해시 테이블은 한계를 가질 수 밖에 없습니다.

정말 단순하게 처음으로 돌아가 봅시다. 해시테이블을 처음배운 첫시간으로 말입니다.

우리는 나눗셈 법을 기억합니다. 그리고 자리 수 접기도 기억합니다. 그리고 비트를 밀어주기 까지 했습니다.

int makeHash( int value, int tableSize ){ //나눗셈법
     return value % tableSize;
}dddd

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

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;
}

우리가 배웠던 위와 같은 해시 알고리즘은 모두, 계속 해서 같은 문제를 발생 시켰지요. 

여전히 이런 문제점을 해결할 수 있는 해시 알고리즘은 없습니다. 

우리는 또 다시 더 나은 방법을 연구하고 제시 할 뿐입니다!

잠시 주제에서 멀어진 느낌이네요. 

우리는 이렇게 한번의 해시 방법론 만을 제시해 왔습니다.

"그럼 두번하면 되죠"

방금 말한 학생?... 누구죠? 손들어봐요!

맞습니다. 바로 이중해싱 입니다.

만약 해시 함수를 이용하여 나온 주소값이 겹친다면, 그 주소값을 기준으로 또 다른 해시 함수를 이용하여 나온 결과 값을 이동폭으로 사용하면 됩니다.

무슨말인지 어렵다면 그림을 참고해보도록합시다.

103 이라는 값이 [2]번 주소로 들어가야 하는 상황입니다. 어떤 알고리즘을 이용 했는지는 모르겠지만, 첫번째 해시 함수를 거쳐 나온 데이터가 [2] 입니다.

하지만 이미 34라는 값이 존재하여 들어갈 수 없는 상황이죠. 그런 상황에서 우리는 103을 또 다른 해시 함수를 거쳐 13 이라는 이동폭을 가지게 합니다.

만약 이동폭이 해시 테이블의 크기를 초과한다면 맨 처음 방으로 부터 이동폭을 가지게 합니다. 아래 그림처럼 말입니다.

이 방법을 활용하면 해시 테이블의 장점을 잘 활용 할 수 있겠지요.

"해시 테이블의 크기가 고정되어 있다면 언젠가 충돌이 일어날 수 밖에 없지 않나요?"

맞습니다! 계속 말했지만, 우리는 더 나은 방법을 제시 할 것입니다.

바로 재해싱 을 통해서 말이죠.

#재해싱

그리 어려운 개념은 아닙니다. 크기가 고정되어있다면  일정 조건을 통해서 해시 테이블의 크기를 늘리면 됩니다. 

통계적으로 해시 테이블의 공간 사용률이 70% 에 이르면 성능 저하가 나타난다고 합니다. 그러니 70% 에 가까워 지기 전에 재해싱을 하여 성능저하를 방지하는 것이 좋습니다.

이렇게 이중해싱과 재해싱에 대해서도 알아 보았으니, 이 두가지를 활용하여 전시간에 했던 예제를 조금 손보도록 하겠습니다.

해시 테이블이 직접 데이터를 담도록 하고, 충돌이 일어날 시 다른 해시 함수를 이용하여 이동폭으로 삼을 겁니다. 그리고 임계치가 60% 를 넘는다면 크기를 2배 늘리는 재해싱 작업을 할겁니다.

#코드구현 

Header.h

이렇게 쓰는게 보기 편하실까요? 어떤 스타일로 보여드려야 편하실지 잘 모르겠네요 ㅎㅎ...

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
typedef char* KeyType;
typedef char* ValueType;

enum ElementStatus{ //값이 있고 없고를 의미합니다.
EMPTY = 0, OCCUPIED = 1 
}

typedef struct _ElementType{  //그 주소값 안의 공간이라고 생각하시면 됩니다.
KeyType key;
ValueType value;

ElementStatus status;
} ElementType;

typedef struct _HashTable{ //해시 테이블 구조체 정의
int occupiedCount;
int tableSize;

ElementType* table;
} HashTable;

HashTable* OAHT_CreateHashTable( int tableSize ); //해시 테이블을 만들어주는 함수입니다.
void       OAHT_DestroyHashTable( HashTable* hashTable ); //해시 테이블을 삭제하는 함수입니다.
void       OAHT_ClearElement( ElementType* element ); //해시 테이블 안의 데이터들을 삭제하는 함수입니다.
void       OAHT_Set( HashTable** hashTable, const KeyType key, const ValueType value );//값을 넣는 함수
ValueType  OAHT_Get( HashTable* hashTable, const KeyType key ); //값을 얻는 함수
int        OAHT_Hash ( const KeyType key, int keyLength, int tableSize ); // 첫번째 해시함수
int        OAHT_Hash2( const KeyType key, int keyLength, int tableSize ); // 두번째 해시함수 (이중해시)

void       OAHT_Rehash( HashTable** hashTable ); //재해시 함수

HashTable* OAHT_CreateHashTable( int tableSize ){
    HashTable* hashTable = (HashTable*)malloc( sizeof(HashTable) );
    hashTable->table     = (ElementType*)malloc( sizeof(ElementType) * tableSize);
    memset(hashTable->table, 0, sizeof(ElementType) * tableSize );
    hashTable->tableSize = tableSize;
    hashTable->occupiedCount = 0;
    return hashTable;
}

void OAHT_Set( HashTable** hashTable, const KeyType key, const ValueType value ){
    int    keyLen, address, stepSize; //길이, 주소, 이동폭
    double usage; //점유율
    
    usage = (double)(*hashTable)->occupiedCount / (*hashTable)->tableSize; //점유율을 얻습니다.
    
    if ( usage > 0.6 ){ //60%를 의미
        OAHT_Rehash( hashTable );
    }
    
    keyLen    = strlen(key);
    address   = OAHT_Hash( key, keyLen, (*hashTable)->tableSize ); //
    stepSize  = OAHT_Hash2( key, keyLen, (*hashTable)->tableSize ); //이중해싱 방법이죠?
    
    while ( (*hashTable)->table[address].status != EMPTY && 
           strcmp((*hashTable)->table[address].key, key) != 0 ){ //비어있으며, 값이 같지않을때까지 반복
        address = (address + stepSize) % (*hashTable)->tableSize;
    }
    
    (*hashTable)->table[address].key = (char*)malloc( sizeof(char) * (keyLen + 1) );
    strcpy( (*hashTable)->table[address].key, key );
    (*hashTable)->table[address].value = (char*)malloc( sizeof(char) * (strlen(value) + 1) );
    strcpy( (*hashTable)->table[address].value, value );
    
    (*hashTable)->table[address].status = OCCUPIED;
    (*hashTable)->occupiedCount++;
}

ValueType OAHT_Get( HashTable* hashTable, const KeyType key ){
    int keyLen    = strlen(key);
    int address   = OAHT_Hash( key, keyLen, hashTable->tableSize );
    int stepSize  = OAHT_Hash2( key, keyLen, hashTable->tableSize );
    
    while ( hashTable->table[address].status != EMPTY &&
           strcmp(hashTable->table[address].key, key) != 0 ){
        address = (address + stepSize) % hashTable->tableSize;
    }
    
    return hashTable->table[address].value;
}

void OAHT_ClearElement( ElementType* element ){
    if ( element->status == EMPTY)return;
    free(element->key);
    free(element->value);
}

void OAHT_DestroyHashTable( HashTable* hashTable){
    int i = 0;
    for ( i=0; i < hashTable->tableSize; i++ ){
        OAHT_ClearElement( &(hashTable->table[i]) );
    }
    free ( hashTable->table );
    free ( hashTable );
}

int OAHT_Hash( const KeyType key, int keyLength, int tableSize ){
    int i=0;
    int hashValue = 0;
    for ( i=0; i<keyLength; i++ ){
        hashValue = (hashValue << 3) + key[i];
    }
    hashValue = hashValue % tableSize;
    return hashValue;
}

int OAHT_Hash2( KeyType key, int keyLength, int tableSize ){
    int i=0;
    int hashValue = 0;
    for ( i=0; i<keyLength; i++ ){
        hashValue = (hashValue << 2) + key[i];
    }
    hashValue = hashValue % ( tableSize - 3 );
    return hashValue + 1;
}

void OAHT_Rehash( HashTable** hashTable ){
    int i = 0;
    ElementType* oldTable = (*hashTable)->table;
    HashTable* newHashTable = OAHT_CreateHashTable( (*hashTable)->tableSize * 2 );
    for ( i=0; i<(*hashTable)->tableSize; i++ ){
        if ( oldTable[i].status == OCCUPIED ){
            OAHT_Set( &newHashTable, oldTable[i].key, oldTable[i].value );
        }
    }
    OAHT_DestroyHashTable( (*hashTable) );
    (*hashTable) = newHashTable;
    cout << newHashTable->tableSize << endl;
}

메인.cpp

#include "Header.h"

using namespace std;
int main(int argc, const char * argv[]) {
   
    HashTable* HT = OAHT_CreateHashTable( 11 );
    
    OAHT_Set( &HT, "MSFT",   "Microsoft Corporation");
    OAHT_Set( &HT, "JAVA",   "Sun Microsystems");
    OAHT_Set( &HT, "REDH",   "Red Hat Linux");
    OAHT_Set( &HT, "APAC",   "Apache Org");
    OAHT_Set( &HT, "ZYMZZ",  "Unisys Ops Check"); /*  APACøÕ √ʵπ */
    OAHT_Set( &HT, "IBM",    "IBM Ltd.");
    OAHT_Set( &HT, "ORCL",   "Oracle Corporation");
    OAHT_Set( &HT, "CSCO",   "Cisco Systems, Inc.");
    OAHT_Set( &HT, "GOOG",   "Google Inc.");
    OAHT_Set( &HT, "YHOO",   "Yahoo! Inc.");
    OAHT_Set( &HT, "NOVL",   "Novell, Inc.");
    
    printf("\n");
    printf("Key:%s, Value:%s\n", "MSFT",   OAHT_Get( HT, "MSFT" ) );
    printf("Key:%s, Value:%s\n", "REDH",   OAHT_Get( HT, "REDH" ) );
    printf("Key:%s, Value:%s\n", "APAC",   OAHT_Get( HT, "APAC" ) );
    printf("Key:%s, Value:%s\n", "ZYMZZ",  OAHT_Get( HT, "ZYMZZ" ) );
    printf("Key:%s, Value:%s\n", "JAVA",   OAHT_Get( HT, "JAVA" ) );
    printf("Key:%s, Value:%s\n", "IBM",    OAHT_Get( HT, "IBM" ) );
    printf("Key:%s, Value:%s\n", "ORCL",   OAHT_Get( HT, "ORCL" ) );
    printf("Key:%s, Value:%s\n", "CSCO",   OAHT_Get( HT, "CSCO" ) );
    printf("Key:%s, Value:%s\n", "GOOG",   OAHT_Get( HT, "GOOG" ) );
    printf("Key:%s, Value:%s\n", "YHOO",   OAHT_Get( HT, "YHOO" ) );
    printf("Key:%s, Value:%s\n", "NOVL",   OAHT_Get( HT, "NOVL" ) );
    
    OAHT_DestroyHashTable( HT );
    
    return 0;
}

이렇게 세번째 노트도 작성이 끝이 났네요!

편집창을 어찌 보여드려야 좋을지 아직도 고민입니다. 색이 있어야하는지 아니면 심플해야하는지.. 여러가지로 올려보고 제일 가독성이 있어보이는 스타일로 바꾸어 갈 예정입니다. 궁금하신점 댓글다셔도 좋습니다~ 제가 알고있는 안에서 답해드리도록 하지요.