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

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

▶ Hash 구현 (양방향, 더미노드 0개, *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 + SIZE], * head[SIZE];
int bcnt;

구조체는 내부 변수나 함수 이전 게시글과 다르지 않다.

다만 더미노드를 한개 두기 때문에 buf[]를 Hash Table Size 만큼 추가로 두어야 한다.

왜냐하면 Hash Table의 각 항목에 더미노드를 두기 때문이다.

 

각 변수의 역할이나 목적은 아래 글 참고

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

 

초기화

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

head[]에다가 더미노드를 한개씩 할당해준다.

이를 위해서 전역변수로 만들 때 개수를 Hash Table 크기 만큼 추가로 두었습니다.

ex) 생성(추가) 되는 데이터가 10,000개이고, Hash Table 크기를 100 으로 잡았을 때,

    → 더미노드로 100개를 두고, 추가되는 데이터는 Hash Index에 따라 Chaining 방식으로 연결.

        buf[] 개수를 20,000개로 잡으면 복잡하게 계산할 필요 없지만

        구조체 크기나 문제 공간 제약 조건에 따라 설계가 필요할 수 있다.

 

추가 (삽입)

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

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

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

- 더미노드가 기본적으로 한개 있기 때문에 더미노드 뒤로 계속해서 연결한다.

    즉, 더미노드가 head 역할이고, 데이터는 앞쪽에 추가될때마다 연결된다.

 

삭제

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();

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

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

    더미노드 한개가 있기에 노드 한 개만 존재할 때 삭제하는 경우 (삭제 후 연결리스트상 비는 경우)

    head[]에 가르키고 있는 Node 처리 필요하지 않게 된다. 

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

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

- 더미노드를 시작으로 해서 연결리스트가 끝까지 고유 ID 값을 비교하면 탐색

    찾는 노드가 존재한다면 해당 포인터를 반환하고, 제거할 수 있다. (pop 함수는 구조체 함수로 처리)

 

전체 Code

#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 + SIZE], *head[SIZE];
int bcnt;

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

void init() {
    bcnt = 0;
    for (int i = 0; i < SIZE; ++i) {
        head[i] = buf[bcnt++].alloc(0, 0, 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] 연결리스트가 비워지는 경우    
}

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

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

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

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

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

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

 

더미노드 1개를 사용할 때 *head[SIZE] 포인터 변수 

무언가를 가리킬 수 있는 포인트, 초기에는 비어있는 상태이다.

 

buf[]를 통해 더미 Node를 할당해주어 *head[]에 할당되게한다.

따라서 buf[] 개수를 선언할 때 Hash Size를 추가적으로 고려해주어야

ex) 실제 추가 되는 Data가 20개일 때, *head[SIZE]에 더미노드 1개씩 만들기 위해서

    Hash Size (= 10)개를 buf[]에서 사용한다면 적어도 buf[20 + 10] 선언 필요

    ※ 더미노드를 두 개(*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)