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

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

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], tail[SIZE];
int bcnt;

더미노드 2개로 head[]와 tail[]이 존재하므로 

if (prev)와 if (next)는 항상 참이므로 작성할 필요 없습니다.

더미노드 head[]와 tail[]도 포인터가 아닌 Node 자체이므로

문제 풀이시 buf[] 추가 개수를 고려하지 않아도 된다.

 

초기화

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

- head[SIZE]와 tail[SIZE]로 각 Hash Index별로 더미노드를 개씩 정적할당 합니다.

(head[i]->prev와 tail[i]->next 은 항상 NULL 입니다.)

 

추가 (삽입)

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

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

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

 

Data를 추가할 때는 tail[] 앞에 추가하는 방식으로 구현 가능

buf[bcnt++].alloc(id[i], tail[key].prev, &tail[key]);

ex) 10, 110, 1010 순으로 push 했을 때, head[0] ↔ 10 ↔ 110 ↔ 1010 ↔ tail[0]로 배치.

 

head[] 뒤쪽에 순서대로 push 하는 경우 아래와 같이 작성

buf[bcnt++].alloc(id[i], &head[key], head[key].next);

이때, 결과는 head[0] ↔ 1010 ↔ 110 ↔ 10 ↔ tail[0]

 

삭제

Node* probing(int id) {
    int key = hash(id);
    Node* p = head[key].next;
    for (; p != &tail[key]; 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 위치)

  tail[key]이 존재하므로 앞/뒤로 자유롭게 구현 가능

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

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

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

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

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

void print() {
    for (int i = 0; i < SIZE; ++i) {
        Node* p = head[i].next;
        if (p != &tail[i]) {
            printf("[%2d]: ", i);
            for (; p != &tail[i]; 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 != &tail[key]; 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);
        // buf[bcnt++].alloc(id[i], tail[key].prev, &tail[key]);
    }

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

 

Reference

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

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

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

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

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