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

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

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

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

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

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

 

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

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

▶ [해시] Hash란? 

▶ [해시] Hash Chaining 기법 구현  

 

구조체 정보

struct Node {
    int id;
    Node* prev, * next;
    Node* alloc(int _id, Node* _prev, Node* _next) {
        id = _id, prev = _prev, next = _next;
        if (prev) prev->next = this;
        if (next) next->prev = this;
        return this;
    }
    void pop() {
        if (prev) prev->next = next;
        if (next) next->prev = prev;
    }
}buf[MAX_N], head[SIZE];
int bcnt;

 

초기화

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

 

추가 (삽입)

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

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

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

 

삭제

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

Node* tg = probing(1010);
if (tg) tg->pop();

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

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

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

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

 

전체 Code

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

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

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

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

- *prev, *next로 양방향 연결

- 원소 삭제를 쉽게 하기 위해 더미노드 1개 사용

#include <stdio.h>
const int MAX_N = 20 + 5;
const int SIZE = 10;

struct Node {
    int id;
    Node* prev, * next;
    Node* alloc(int _id, Node* _prev, Node* _next) {
        id = _id, prev = _prev, next = _next;
        if (prev) prev->next = this;
        if (next) next->prev = this;
        return this;
    }
    void pop() {
        if (prev) prev->next = next;
        if (next) next->prev = prev;
    }
}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].next = 0;
    }
}

void print() {
    for (int i = 0; i < SIZE; ++i) {
        Node* p = head[i].next;
        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].next;
    for (; p; p = p->next) {
        if (p->id == id)
            return p;
    }
    return 0;
}

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]);
        buf[bcnt++].alloc(id[i], &head[key], head[key].next);
    }

    print();
    Node* tg = probing(1010);
    if (tg) tg->pop(); print(); // 중간 원소
    probing(90)->pop(); print(); // 첫번째 원소
    probing(10)->pop(); print(); // 마지막 원소
    probing(110)->pop(); print(); // head[0] 연결리스트가 비워지는 경우    
}

더미 노드를 1개를 사용하는데 전역으로 head[SIZE] 사용하면서

객체가 만들어진 상태로 buf[]에서 더미 Node를 할당해주지 않아도 된다.

init() 할 때, next 연결만 해제하면 된다.

 

*head[SIZE] 구현과의 차이는 buf[]에서 Node를 할당처리 해야하고,

그에 따른 buf[] 개수를 SIZE 만큼 추가로 고려해야 한다.

※ 더미노드를 두 개(*head[], *tail[]) 사용하는 경우에는 2 × SIZE 만큼 고려한다.

더미노드가 1개 있는 상태에서 if (next) 처리는 필수이다.

구현하지 않는 경우 Test Case에 따라 RTE 발생

※ if (prev)는 더미노드가 1개 존재하므로 없어도 RTE가 발생하지 않는다. 

    즉, if문 결과는 항상 True

 

Reference

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

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

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

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

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