[알고리즘] 해싱(Hashing) 정리하기

안녕하세요 감자코딩에 감자개발자입니다.

이번에 살펴볼 주제는 해싱에 대한 소개입니다.

간략히 요약하여 공부용으로 작성하였습니다.

---

해싱 개념 설명

데이터 관리/유지 자료구조 

리소스 < 속도

 

해시함수(hash function)란 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수

키(key)란 매핑전 원래 데이터의 값

해시값(hash value)란 매핑후 데이터의 값

매핑하는 과정 자체를 해싱(hashing)이라고 한다.

해싱(hashing) 과정 설명

 

키(KEY) ——> 해시 함수(hash function) ————> 해시값(hash value)

[이름]                  [해싱 과정]                 [index(hash value)  : data ]

 

 

해시 테이블의 장점

 

1. 해시충돌이라는 발생 가능성이 있지만, 적은 리소스로 많은 데이터를 효율적으로 관리 할 수 있음.

2. 하드디스크, 클라우드 존재하는 데이터(키)들은 무한에 가까운데, 이것들을 유한한 개수의 해시값으로 매핑하면서 작은 크기의 캐시메모리로도 프로세스를 관리 할 수 있음.

3. 색인(Index)에 해시값을 사용하므로 모든 데이터를 살피지 않아도 검색과 삽입/삭제를 빠르게 수행할 수 있다

4. 해시 함수는 언제나 동일한 해시값을 리턴하고, 해당 색인만 알면 해시테이블의 크기에 상관없이 데이터에 빠르게 접근 가능

5. 색인은 간단한 함수(상수시간)로 작동하기 때문에 매우 효율적

6. 데이터 액세스(삽입,삭제,탐색)시 시간복잡도 O(1)을 지향한다.

 

해시테이블

1. 해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인(index)혹은 주소 삼아 데이터의 값(value)을 키와 함께 저장하는 자료구조를 해시테이블(hash table)이라고 한다.

2. 데이터가 저장되는곳을 버킷(bucket)또는 슬록이라고 한다. 해시테이블의 기본연산은 삽입,삭제,탐색(search)이다.

Keys ———> hash function ———> buckets

[이름]                  [해싱 과정]                 [index(hash value)  : data ]

 

 

C언어 해싱 코드

//
//  basic_hashing.cpp
//  beakjoon_algorithm
//
//  Created by kgh on 30/06/2019.
//  Copyright © 2019 kgh. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>

struct bucket* hashTable = NULL;
int SIZE = 10;

struct node{
    int key;
    int value;
    node* next; //   체이닝 구현시 다음 값
};

struct bucket {
    struct node* head;
    int count;      // 버켓에 몇개의 값이 있는지
};

// 새로운 메모리를 할당하고 기본값을 세팅해주는 역할
struct node* createNode(int key, int value){
    struct node* newNode;
    newNode = (struct node*)malloc(sizeof(struct node));
    newNode->key = key;     // 유저가 만들고자 하는 키
    newNode->value = value; // 유저가 만들고자 하는 값
    newNode->next = NULL;
    
    return newNode;
}

// 해쉬 Function 구현
int hashFunction(int key){
    // key 값이 들어오면 몇번으로 들어가는지 로직을 설정한다.
    
    return key%SIZE;
}
void insert(int key, int value){
    int hashIndex = hashFunction(key);
    struct node *newNode = createNode(key,value);
    //내가 넣고자 하는 인덱스에 이미 값이 없는 경우
    if(hashTable[hashIndex].count == 0){
        hashTable[hashIndex].head = newNode;
        hashTable[hashIndex].count = 1;
    }
    //내가 넣고자 하는 인덱스에 이미 값이 있는 경우
    else{
        newNode->next = hashTable[hashIndex].head;
        hashTable[hashIndex].head = newNode;
        hashTable[hashIndex].count++;
        
    }
    return;
}
void remove1(int key){
    int hashIndex = hashFunction(key);
    struct node* node;
    struct node* trace = NULL;
    
    node = hashTable[hashIndex].head;
    if(node == NULL){
        printf("\n no key found");
        return;
    }
    // 삭제이후 체이닝된 값들을 다시 재정렬해주는 것이 필요함.
    while(node != NULL){
        //찾은 경우
        if(node->key == key){
            // 지운값이 헤드인 경우(포인터를 바꾸어주는 부분)
            if(node == hashTable[hashIndex].head){
                hashTable[hashIndex].head = node->next;
            // 지운값이 헤드가 아닌경우
            }else{
                trace->next = node->next;
            }
            hashTable[hashIndex].count--;
            free(node);
            break;
        }
        trace = node;
        node = node->next;
    }
    printf("\nno key found");
    return;
    
}
void search(int key){
    // 삭제처럼 trace 노드를 만들필요는 없음.
    
    int hashIndex = hashFunction(key);
    struct node* node = hashTable[hashIndex].head;
    
    if(node == NULL){
        printf("\nno key found");
        return;
    }
    while(node != NULL){
        // 찾았다의 상황
        
        if(node->key == key){
            printf("key found key = [%d] value =[%d]",node->key,node->value);
            break;
        }
        node = node->next;
    }
    printf("\nno key found");
    return;
    
}
void display(){
    struct node* horse;
    for(int i=0; i<SIZE; i++){
        horse = hashTable[i].head;
        printf("Bucket[%d] : ", i);
        while(horse != NULL){
//            printf("key found key = [%d] value =[%d]",horse->key,horse->value);
            printf("(key:%d, val:%d)", horse->key, horse->value);
            horse = horse->next;
        }
        printf("\n");
        
    }
    return;
}

int main(void){
    // Intuialize
    hashTable = (struct bucket*)malloc(SIZE *sizeof(struct bucket));
    
    insert(0,1);
    insert(1,10);
    insert(11,90);
    insert(21,64);
    insert(31,23);
    insert(6,25);
    insert(97,23);
    display();
    remove1(31);
    display();
    
    
}

C언어 해싱 코드를 간략하게 작성해보았습니다. 약간의 에러사항이 있어 곧 수정해서 다시올리도록 하겠습니다.

 

이상 감자코딩에 감자개발자였습니다.