배열이용하여 Hash 사용하기(feat. 코딩테스트)

배열을 이용하여 memory 를 잡아준 뒤,
Single Linked List로 hash를 사용하는 코드이다.

#define MAX_TABLE_SIZE 1000

typedef struct Node {
        char data[5];
        struct Node *prev;
} Node;

Node a[MAX_TABLE_SIZE];
Node *hashTable[MAX_TABLE_SIZE];

int arr_idx = 0;

unsigned long myHash(const char *str)
{       
        unsigned long hash = 5381;
        int c;
        
        while (c = *str++)
                hash = (hash * 7 * c) % MAX_TABLE_SIZE;
        
        return hash;
}

Node* myAlloc(void)
{       
        return &a[arr_idx++];
}

void copyStr(char *dest, char *src, int n)
{       
        for(int i = 0; i < n; i++)
                *dest++ = *src++;
}

int compareStr(char *dest, char *src, int n)
{       
        for(int i = 0; i < n; i++)
                if(*dest++ != *src++)
                        return -1;
        
        return 0;
}

int main()
{
        char input[7] = "abcdefg";
        unsigned int key;
        Node *p;

        key = (unsigned int)myHash(input);
        p = myAlloc();

        copyStr(p->data, input, 7);
        p->prev = hashTable[key];
        hashTable[key] = p;

        //...

        //search
        key = myHash(input);
        for (Node *start = hashTable[key]; start != NULL; start = start->prev)
                if(!compareStr(start->data, input, 7))
                        printf("find \n");

        // reset
        arr_idx = 0;
        for (int i = 0; i < MAX_TABLE_SIZE; i++)
                hashTable[i] = 0x0;

        return 0;
}