[Reference] Hash

1. Hash 구성

#define MAX_TABLE 4096

typedef struct {
    char key[5];
    char data[5];
}Hash;

Hash hashTable[MAX_TABLE];

- key값과 data로 구성된 구조체의 배열을 Hash Table이라 하며 Hash Table의 index값을 Hash값이라 한다.

 

 

2.  Hash Function

unsigned long hash(const char *str) {
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
        hash = (((hash << 5) + hash) + c) % MAX_TABLE;

    return hash % MAX_TABLE;
}

- key값을 Hash값(=Hash Table의 index값)으로 바꾸어주는 Hash Function이다.

[key값] → Hash Function → [Hash값]

 

 

3. Hash 삽입

int add(const char *key, char *data) {
    unsigned long h = hash(key);

    while (hashTable[h].key[0] != 0) {
        if (strcmp(hashTable[h].key, key) == 0)
            return 0;

        h = (h + 1) % MAX_TABLE;
    }
    strcpy(hashTable[h].key, key);
    strcpy(hashTable[h].data, data);
    return 1;
}

- 시간 복잡도 : O(1) (hash Function의 효율이 안좋다면 O(n))
- hash값을 구해 Hash Table index에 바로 접근해 삽입한다. 만약 해당 index에 다른 값이 있다면 다음 index로 빈자리를 찾을때까지 반복하다 빈자리를 찾으면 삽입한다.
- 해당 key값이 Table에 없으면서 Table에 빈자리가 없으면 무한 반복에 빠지게 되므로 Table크기는 항상 부족하지 않게 만들어 주어야한다.

 

 

4. Hash 검색

int find(const char *key, char *data) {
    unsigned long h = hash(key);
    int cnt = MAX_TABLE;

    while (hashTable[h].key[0] != 0 && cnt--) {
        if (strcmp(hashTable[h].key, key) == 0) {
            strcpy(data, hashTable[h].data);
            return 1;
        }
        h = (h + 1) % MAX_TABLE;
    }
    return 0;
}

- 시간 복잡도 : O(1) (hash Function의 효율이 안좋다면 O(n))
- hash값을 구해 Hash Table index에 바로 접근한다. 없으면 아래 위치로 Table 크기 만큼 이동하면서 검색한다.

 

 

5. Reference 사용 예시

int main(int argc, char* argv[]) {
    memset(hashTable, 0, sizeof(hashTable));

    add("key1", "d1");
    add("key2", "d2");
    add("key3", "d3");

    char buf[5];
    if (find("key2", buf))
        printf("buf=%s\n", buf);    // buf=d2
    else
        printf("not found\n");

    if (find("key4", buf)) 
        printf("buf=%s\n", buf);
    else 
        printf("not found\n");      // not found

    return 0;
}