[자료구조] 체이닝 (chaining)

체이닝 (chaining)

앞서 충돌이 일어났을 경우 해시 함수를 변형해 다른 버킷에 삽입 하는 방식이었습니다. 그러나 비어있는 곳을 찾기 위해 시간이 더 소요되는 단점이 있었습니다.

 

체이닝은 해시 테이블의 구조를 변경해 각 버킷이 하나 이상의 값을 저장할 수 있도록 하는 것입니다. 즉, 오버플로우 문제를 해결하는 방식을 기존의 각 버킷에 고정된 슬롯을 할당하는 대신 삽입과 삭제가 용이한 연결 리스트로 변경해 해결하는 것입니다.

 

체이닝 구현

해시 함수 설정

충돌이 일어났을 시 새로운 연결 리스트의 노드를 생성해주면 되기 때문에 체이닝에서 해시 함수는 어느 것을 사용해도 상관 없습니다.

int hash_function(int key) {
	return key % TABLE_SIZE;
}

 

연결 리스트 체이닝

키가 버킷으로 들어오면 동적 메모리 할당(malloc)으로 연결 리스트의 노드를 생성한 다음 키를 복사합니다. 이 때, 동일한 키가 발견되지 않으면 연결 리스트의 맨 끝에 새로운 키를 포함하는 새로운 노드를 연결합니다.

void hash_chain_add(element item, struct list *ht[]) {
    int hash_value = hash_function(item.key);
    struct list *ptr;
    struct list *node_before = NULL, *node = ht[hash_value];
    for(; node; node_before = node, node = node->link) {
        if(node->item.key == item.key) {
            fprintf(stderr, "이미 탐색키가 저장되어 있음\n");
            return;
        }
    }
    ptr = (struct list *)malloc(sizeof(struct list));
    ptr->item = item;
    ptr->link = NULL;
    if(node_before) {
        node_before->link = ptr;
    } else {
        ht[hash_value] = ptr;
    }
}

 

체이닝 탐색

해시 테이블을 탐색하는 경우에는 연결 리스트에 해당하는 키 값이 존재할 때까지 버킷에 존재하는 각 노드들을 탐색하면 됩니다.

void hash_chain_search(element item, struct list *ht[]) {
    struct list *node;
    int hash_value = hash_function(item.key);
    for(node = ht[hash_value]; node; node = node->link) {
        if(node->item.key == item.key) {
            fprintf(stderr, "탐색 %d 성공 \n", item.key);
            return;
        }
    }
    printf("키를 찾지 못했음\n");
}

 

체이닝으로 충돌 처리하기

입력할 숫자가 다음과 같이 입력된다고 한다면 체이닝으로 해시테이블의 내용을 그리시오. (단, 해시 테이블의 크기는 7, 해시 함수 $h(k) = k \space mod \space 7$)

$$ 12, 47, 93, 23, 89,60, 78 $$