hash(char[] key) c++ 코드

외부 라이브러리가 제한된 경우를 가정하여 strcmp와 strcpy가 포함되어 있습니다.

• c++ 코드로 보는 - 문자열 비교(strcmp), 문자열 카피(strcpy)

#include <stdio.h>

#define MAX_KEY 1000
#define MAX_TABLE 2000

int strcmp(const char *str1, const char *str2) {
        
        while (*str1) {

                if (*str1 != *str2) break;

                ++str1;
                ++str2;
        }

        return *(const unsigned char*)str1 - *(const unsigned char*)str2;
}


void strcpy(char *dest, const char *source){
        
        while (*source) {
                *dest = *source;

                ++dest;
                ++source;
        }
}



struct Node {
        int idx;
};

struct Hash
{
        //hash를 만들고자 하는 key
        char key[MAX_KEY + 1];
        //key에 할당 되는 data
        Node* data;
};

Hash htb[MAX_TABLE];

//djb2 algorithm 
unsigned long hash(const char *str)
{
        // hash값을 잘 분산 시키기 위해 실험적으로 증명된 상수 값
        unsigned long hash = 5381;
        
        int c;

        //문자열이 한 개씩 들어올 때 마다
        //아래와 같은 연산을 한 후 MAX_TABLE 값으로 modular연산을 한다
        while (c = *str++)
        {
                hash = (((hash << 5) + hash) + c) % MAX_TABLE; /* hash * 33 + c */
        }

        return hash % MAX_TABLE;
}

//주어진 key와 data를 테이블에 삽입하는 함수
int add(const char *key, Node *data)
{
        //key값을 hash값으로 변환
        unsigned long h = hash(key);

        //해당하는 hash값이 이미 사용되었다면(충돌이 일어난 경우)
        while (htb[h].key[0] != 0)
        {
                //같은 key값이라면 0을 return한다. 즉 같은 key가 존재하므로 add 하지 않는다
                if (strcmp(htb[h].key, key) == 0)
                {
                        return 0;
                }

                //open addressing 기법
                //같은 hash값이지만 다른 key라면 다음 hash값을 확인한다
                h = (h + 1) % MAX_TABLE;
        }

        //비어있는 해당 hash값에 key와 data를 저장한다 
        strcpy(htb[h].key, key);
        htb[h].data = data;
        return 1;
}

//key가 주어졌을 때, hash table내에 있는 data를 비어있는 주소값에 넣어 리턴하는 함수
int find(const char *key, Node *data)
{
        //key값을 hash값으로 바꾼다
        unsigned long h = hash(key);

        //테이블이 모두 차있을 경우를 대비하는 index
        int cnt = MAX_TABLE;

        //충돌이 일어나지 않거나, 모든 테이블을 검사할 때까지 탐색
        while (htb[h].key[0] != 0 && cnt--)
        {

                //찾고자 하는 key를 찾았으면 해당 데이터를 비어있는 주소값에 넣어 리턴
                if (strcmp(htb[h].key, key) == 0)
                {
                        data = htb[h].data;
                        return 1;
                }

                //open addressing
                h = (h + 1) % MAX_TABLE;
        }
        return 0;
}


int main() {

        char str1[] = "abcjoijdsafjioc";
        char str2[] = "dkjvoiadjsf";

        // output : 122
        printf("%d\n", hash(str1));
        
        // output : 1172
        printf("%d\n", hash(str2));

}