해싱(hashing) / 해시테이블(hash table) / 해시함수(hash function)

*해싱(hashing)

;키(key) 값을 해시 함수(hash function)라는 수식에 대입시켜 계산한 후 나온 결과를 주소로 사용하여 바로 값(value)에 접근하게 할 수 하는 방법

_

*해시 테이블(hash table)

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

 -해시 테이블의 기본적인 연산은 삽입, 삭제, 탐색.

*버킷(bucket)

;데이터가 저장되는 곳. 하나의 주소를 갖는 파일의 한 구역을 의미. 버킷의 크기는 같은 주소에 포함될 수 있는 레코드 수를 의미함.

*슬롯(slot)

;데이터가 저장되는 곳. 한 개의 레코드를 저장할 수 있는 공간으로 n개의 슬롯이 모여 하나의 버킷을 형성함.

_

*해시함수(hash function)

;데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수.

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

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

 

*해시함수의 종류

 -제산 함수: 나머지 연산자 mod(%)를 사용. 소수를 이용.

 -폴딩 함수: 탐색키를 여러부분으로 나누어 이를 더하거나 XOR(배타적 논리합)한 값을 주소로 삼는 방식.

 -중간 제곱 함수: 탐색키 값을 제곱한 후 그 중간 부분의 값을 주소로 삼는 방식.

 -숫자 분석 방법: 키값의 숫자들 중에서 편중되지 않은 수들을 택하여 주소로 삼는 방식. (예) 학번..2019'12345'

 -탐색키가 문자열인 경우: 각 문자에 정수를 대응시켜 주소로 삼는 방식. 각 문자의 아스키 코드나 유니코드 값을 이용.

_

*해싱의 오버플로우(충돌 Collision) 해결 방법

 -선형 조사법(linear probing): 특정 버킷에서 충돌이 발생하면 해시테이블에서 비어있는 버킷을 찾는 방법.

 -체이닝(chaining): 해시테이블의 구조 변경을 통해 연결리스트로 해결하는 방법.

_

#define TABLE_SIZE 13    // 해싱 테이블의 크기 (예)소수 13을 사용
 
// 문자열로 된 탐색키를 숫자로 변환 : 간단한 덧셈 방식
inline int transform(const char* key)
{
    int number = 0;
    while (*key)
        number += (*key++);
    return number;
}
// 해싱 함수 : 제산 함수 사용(나머지 연산자)
inline int hashFunction(const char* key)
{
    return transform(key) % TABLE_SIZE;
}
 
#include <cstdio>
#include <cstring>
#define KEY_SIZE    64    // 탐색키의 최대 길이
#define VALUE_SIZE    64    // 탐색키와 관련된 정보
 
class Record
{
private:
    char key[KEY_SIZE];    // 키 필드(사전의 경우 "단어")
    char value[VALUE_SIZE];    // 키와 관련된 자료("의미")
public:
    Record(const char* k = "", const char* v = "")
    {
        set(k, v);
    }
    void set(const char* k, const char* v = "")
    {
        strcpy_s(key, KEY_SIZE, k);
        strcpy_s(value, VALUE_SIZE, v);
    }
    void reset()
    {
        set("", "");
    }
    bool isEmpty()
    {
        return key[0] == '\0';
    }
    bool equal(const char* k)
    {
        return strcmp(k, key) == 0;
    }
    void display()
    {
        printf("%20s = %s\n", key, value);
    }
};
 
#include "Record.h"
#include "hashFunctions.h"
 
class HashMap
{
private:
    Record table[TABLE_SIZE];    // 해싱 테이블. 크기 13
public:
    HashMap()
    {
        reset();    // 모든 버킷을 비움
    }
    void reset()
    {
        for (int i = 0; i < TABLE_SIZE; i++)
            table[i].reset();
    }
    // 맵의 전체 내용을 출력
    void display()
    {
        for (int i = 0; i < TABLE_SIZE; i++)
        {
            printf("[%2d] ", i);
            table[i].display();
        }
    }
    // HashMap::addLinearProb(): 선형 조사법을 이용한 삽입
    void addLinearProb(const char* key, const char* value)
    {
        int i, hashValue;
        hashValue = i = hashFunction(key);
        while (table[i].isEmpty() == false)
        {
            if (table[i].equal(key))
            {
                printf("[%s] 탐색키가 중복되었습니다.\n", key);
                return;
            }
            i = (i + 1) % TABLE_SIZE;
            if (i == hashValue)
            {
                printf("[%s] 테이블이 가득찼습니다.\n", key);
                return;
            }
        }
        table[i].set(key, value);
    }
    // HashMap::searchLinearProb(): 선형 조사법을 이용한 탐색
    Record* searchLinearProb(const char* key)
    {
        int i, hashValue;
        hashValue = i = hashFunction(key);
        while (table[i].isEmpty() == false)
        {
            if (table[i].equal(key))
            {
                printf("[%s] 탐색성공[%d]", key, i);
                table[i].display();
                return table + i;;
            }
            i = (i + 1) % TABLE_SIZE;
            if (i == hashValue)
            {
                break;
            }
            printf("[%s] 탐색 실패: 찾는 값이 테이블에 없음\n", key);
            return NULL;
        }
    }
};