Hash (단방향, 더미노드 0개, *head)

해당 게시글은 Chaining 기법을 Memory Pool 방식으로 구현한 내용입니다.

▶ Hash 구현 (양방향, 더미노드 0개, *head) 구현방식과 비교하면 좋습니다.

양방향이지 않기 때문에 이전 노드(prev)에 대한 구현 차이가 있습니다.

삭제될 때, 이전 노드(prev)에 해당하는 노드의 연결처리가 필요합니다.

Hash 구현에 있어서 중요한 것은 Hash Function을 통해서

key → Hash Index로 변환되는 결과에서 중복 Hash Index가 적게 발생하는 것이다.

즉, 충돌을 적게 발생시키는 것이 효율적인 Hash Function 이다.

 

Hash Function을 잘 만든다면 충돌 처리를 할 필요는 없지만,

보장할 수 없는 경우라면 크게 Chaining 기법과 Open Address 기법으로 해결할 수 있다.

▶ [해시] Hash란?  

▶ [해시] Hash Chaining 기법 구현  

 

구조체 정보

struct Node {
    int id;
    Node* next;
    Node* alloc(int _id, Node* _next) {
        id = _id, next = _next;
        return this;
    }
}buf[MAX_N], * head[SIZE];
int bcnt;

bcnt : 현재 사용된 buffer 개수

          처음 정적 할당받은 buf[MAX_N]에서 가져다 사용한다.

*head[size] : 각 Hash Index 연결리스트의 첫번째 위치

                      key값이 존재하는지 확인할 때는 해당 연결리스트를 탐색한다.

 

초기화

void init() {
    bcnt = 0;
    for (int i = 0; i < SIZE; ++i) {
        head[i] = 0;
    }
}

- Test Case가 1개라면 필요없지만, 여러 Test Case가 존재하는 경우에는

  Hash Table을 Clear 해주어야 한다.

- 지금까지 할당해준 buf[]의 개수를  「0」 으로 해준다.

- 각 연결리스트 첫번째를 가리키는 head[]를 NULL(0) 처리

 

추가 (삽입)

- 비어있는 연결리스트에 추가하는 경우

- 원소가 이미 존재하는 연결리스트에 새로운 원소 추가하는 경우

for (int i = 0; i < N; ++i) {
    int key = hash(id[i]);
    head[key] = buf[bcnt++].alloc(id[i], head[key]);
}

stack 처럼 Hash Table 연결리스트에서 앞쪽에 추가된다.

 

삭제

void remove(int id) {
    int key = hash(id);
    Node* prev = 0;
    Node* cur = head[key];
    for (; cur; cur = cur->next) {
        if (cur->id == id) {
            // 첫번째 노드인 경우
            if (cur == head[key]) {
                head[key] = cur->next;
                return;
            }
            // 첫번째 노드 이후에 위치한 경우
            prev->next = cur->next;
        }
        // prev가 cur을 뒤따른다.
        prev = cur;
    }
}

- 중간에 위치한 원소를  삭제하는 경우

- 첫번째 원소를 삭제하는 경우 (삭제 후 다른 원소가 존재)

- 마지막 위치한 원소를 삭제하는 경우

- 삭제 후 연결리스트가 비워지는 경우

 

전체 Code

- key 충돌을 Open Addressing이 아닌 Chaining 기법으로 처리

- id 값을 가지는 Node 객체는 20개로 제한 (여유로운 크기를 위해 + 5)

- Stack처럼 새로운 Node가 앞쪽에 push (head 위치)

- key 값은 return id % 10;으로 처리

#include <stdio.h>
const int MAX_N = 20 + 5;
const int SIZE = 10;
struct Node {
    int id;
    Node* next;
    Node* alloc(int _id, Node* _next) {
        id = _id, next = _next;
        return this;
    }
}buf[MAX_N], *head[SIZE];
int bcnt;

int hash(int id) {
    return id % 10;
}

void init() {
    bcnt = 0;
    for (int i = 0; i < SIZE; ++i) {
        head[i] = 0;
    }
}

void print() {
    for (int i = 0; i < SIZE; ++i) {
        Node* p = head[i];
        // 연결리스트에 원소가 존재하는 경우
        if (p) {
            printf("[%2d]: ", i);
            for (; p; p = p->next) {
                printf("%d - ", p->id);
            }
            printf("\n");
        }
    }
    printf("\n\n");
}

Node* probing(int id) {
    int key = hash(id);
    Node* p = head[key];
    for (; p; p = p->next) {
        if (p->id == id)
            return p;
    }
    return 0;
}

void remove(int id) {
    int key = hash(id);
    Node* prev = 0;
    Node* cur = head[key];
    for (; cur; cur = cur->next) {
        if (cur->id == id) {
            // 첫번째 노드인 경우
            if (cur == head[key]) {
                head[key] = cur->next;
                return;
            }
            // 첫번째 노드 이후에 위치한 경우
            prev->next = cur->next;
        }
        // prev가 cur을 뒤따른다.
        prev = cur;
    }
}

int main() {
    int N = 20;
    int id[] = {
           10, 110, 1010, 22, 12,
           52, 777, 93, 19, 90,
           63, 5, 4242, 42, 555,
           333, 88, 878, 123, 789,
    };

    init();

    for (int i = 0; i < N; ++i) {
        int key = hash(id[i]);
        head[key] = buf[bcnt++].alloc(id[i], head[key]);
    }

    print();
    remove(1010); print(); // 중간 원소
    remove(90); print(); // 첫번째 원소
    remove(10); print(); // 마지막 원소
    remove(110); print(); // head[0] 연결리스트가 비워지는 경우
}

- 단방향이기 때문에 Node 삭제 시 앞에 위치한 "prev Node"를 처리하기 위해서

  Node 탐색 시 두 개의 포인트 구현 (*prev, *cur)

- 첫번째 노드가 삭제되는 경우에는 *head[key]가 다음 Node를 가르키도록 처리

  (다음 Node가 없을 수도 있다.)

 

Reference

- Hash 구현 (양방향, 더미노드 0개, *head) 

- Hash (양방향, 더미노드 1개, *head)  

- Hash (양방향, 더미노드 1개, head) 

- Hash (양방향, 더미노드 2개, *head, *tail) 

- Hash (양방향, 더미노드 2개, head, tail)