해싱과 해시 함수

∙ 해싱 (hashing)

- hash 잘게 썰은 것, 긁어모은 것, 아무렇게나 뒤섞다.

- 각각의 데이터를 (가급적) 고유한 숫자 값으로 표현하고, 이를 이용하여 특정 데이터의 존재 여부를 확인하거나 또는 원본 데이터를 추출하는 작업 

- 응용 분야 : 빠른 자료 탐색(O(1), 변조 탐지 및 에러 검출 (MD5, SHA)

 

∙ 해싱이 필요한 경우

- 요구사항 : 정수를 저장하고 있는 컨테이너가 있고, 이 컨테이너에 특정 정수가 들어 있는지를 빠르게 판단하고 싶음

- 해결 방법 : 적절한 크기의 bool 타입 배열을 하나 만들고, 이 배열에서 입력 정수에 해당하는 인덱스의 원소 값을 true로 설정

- 문제점 : 정수 범위가 너무 크다면? 데이터가 실수라면? 데이터가 숫자가 아니라면?

-> 어떠한 데이터 타입의 값이든 원하는 범위의 정수로 매핑하는 함수를 만들어 사용

 

class hash_set
{
private:
	int sz;
    std::vector<int> data;
    
public:
	hash_set(int n) : sz(n), data(sz, -1) {}
    
    int hash(int key) { return key % sz; }
    
    void insert(int value) { data[hash(value)] = value; }
    bool find(int value) { return (data[hash(value)] == value); }
    void erase(int value) { data[hash(value)] = -1; }
};

 

- 전체 소스 코드

#include <iostream>
#include <vector>

using namespace std;

class hash_set
{
private:
    int sz;
    
    vector<int> data;
    
public:
    hash_set(int n) : sz(n), data(sz, -1) {}
    
    // hash 함수
    int hash(int key)
    {
        return key % sz;
    }
    
    void insert(int value)
    {
        data[hash(value)] = value;
    }
    
    bool find(int value)
    {
        return (data[hash(value)] == value);
    }
    
    void erase(int value)
    {
        data[hash(value)] = -1;
    }
    
    void print()
    {
        for (auto n : data)
            cout << n << ", ";
        cout << endl;
    }
};

int main()
{
    hash_set num_set(7);
    
    num_set.insert(10); // 7로 나눴을 때 나머지가 3 이기때문에 3번째 인덱스
    num_set.insert(15); // 1번째 인덱스
    num_set.insert(20); // 6번째 인덱스
    num_set.insert(100); // 2번째 인덱스
    
    num_set.print(); // -1, 15, 100, 10, -1, -1, 20
    
    // 10 값을 찾기
    int value = 10;
    if (num_set.find(value))
        cout << value << " is found!" << endl;
    else
        cout << value << " is not found!" << endl;
    
}

 

∙ 해시 함수 (hash funtion)

- 주어진 데이터로부터 (가급적) 고유한 숫자 값을 계산하는 함수

- 보통 함수의 출력은 고정된 범위의 정수로 매칭됨

- ex) h(k) = k % n 함수는 입력  k를 [0, n-1] 범위의 정수로 매핑

 

∙ 키(key)

- 해시 함수의 입력으로, 입력 데이터 자체이거나 또는 데이터를 구분하는 값

 

∙ 해시 값 (hash value)

- 해시 함수의 출력으로 보통 해시 테이블의 인덱스로 사용됨

- 해시 코드 또는 단순히 해시라고도 부름

 

∙ 해시 테이블 (hash table)

- 입력 데이터가 저장되는 배열로서, 해시 함수에 의해 계산된 인덱스 데이터가 저장됨

- 해시 맵 (hash map)

 

∙ 버킷 (bucket)

- 해시 테이블에서 하나의 데이터가 저장된 공간

- 슬롯 (slot)

 

∙ 충돌 (collision)

- 해시 함수가 서로 다른 키에 대해 같은 해시 값을 반환함으로써, 해시 테이블에서 두 개 이상의 데이터가 같은 위치에 저장되려는 현상

- 해시 테이블의 크기가 저장할 데이터의 개수보다 작으면 반드시 충돌이 발생

- 해시 테이블의 크기가 저장할 데이터의 개수보다 크더라도 해시 함수의 동작에 따라 충돌이 발생할 수 있음

- 체이닝, 오픈 어드레싱, 뻐꾸기 해싱 등의 방법으로 해결

 

∙ 체이닝 (chaining)

- 해시 테이블의 특정 위치에서 하나의 키를 저장하는 것이 아니라 하나의 연결 리스트를 저장하는 기법. 개별 체이닝(separate chaining)

- 새로 삽입된 키에 의해 충돌이 발생하면 리스트에 새로운 키를 추가

 

∙ 체이닝 특징

- 삽입 연산은 O(1)의 시간 복잡도로 동작

- (최악의 경우) 모든 데이터가 같은 해시 값을 가질 경우, 탐색 연산은 O(n)의 시간 복잡도로 동작

- 삭제 연산의 경우, 먼저 탐색을 수행하므로 최악의 경우 O(n)의 시간 복잡도로 동작

 

- 체이닝을 구현한 해싱 클래스

class hash_set
{
private:
	int sz;
    // 만약 <key, value> 쌍으로 구성된 데이터를 저장하는 hash_map을 구성하려면 std::pair를 사용!
    // vector<list<pair<string,int>>> data;
    std::vector<std::list<int>> data;
    
public:
	hash_set(int n) : sz(n), data(sz) {}
    
    int hash(int key) { return key % sz; }
    
    void insert(int value) 
    { 
    	data[hash(value)].push_back(value); 
    }
    bool find(int value) 
    { 
    	auto& entries = data[hash(value)];
        return std::find(entries.begin(), entries.end(), value) != entries.end();
    }
    void erase(int value) 
    { 
    	auto& entries = data[hash(value)];
        auto it = std::find(entries.begin(), entries.end(), value);
        
        if (it != entries.end())
        	entries.erase(it);
    }
};

 

- 체이닝 기법을 적용한 전체 소스 코드

#include <iostream>
#include <vector>
#include <list>

class hash_set
{
private:
    int sz;
    // 만약 <key, value> 쌍으로 구성된 데이터를 저장하는 hash_map을 구성하려면 std::pair를 사용!
    // vector<list<pair<string,int>>> data;
    std::vector<std::list<int>> data;
    
public:
    hash_set(int n) : sz(n), data(sz) {}
    
    int hash(int key) { return key % sz; }
    
    void insert(int value)
    {
        data[hash(value)].push_back(value);
    }
    bool find(int value)
    {
        auto& entries = data[hash(value)];
        return std::find(entries.begin(), entries.end(), value) != entries.end();
    }
    void erase(int value)
    {
        auto& entries = data[hash(value)];
        auto it = std::find(entries.begin(), entries.end(), value);
        
        if (it != entries.end())
            entries.erase(it);
    }
    
    void print()
    {
        for (int i = 0; i < sz; i++){
            std::cout << i << ": ";
            for (auto n : data[i]){
                std::cout << n << ", ";
            }
            std::cout << std::endl;
        }
    }
};


using namespace std;

int main()
{
    hash_set num_set(7);
    
    num_set.insert(10); // 7로 나눴을 때 나머지가 3 이기때문에 3번째 인덱스
    num_set.insert(15); // 1번째 인덱스
    num_set.insert(20); // 6번째 인덱스
    num_set.insert(100); // 2번째 인덱스
    
    
    
    // 10 값을 찾기
    int value = 10;
    if (num_set.find(value))
        cout << value << " is found!" << endl;
    else
        cout << value << " is not found!" << endl;
    
    // 저장된 형태 100, 2 로 저장되어 있음
    num_set.insert(2); // 100이라는 값과 원래는 충돌이 일어나지만, 지금은 체이닝 기법을 사용했기에 연결 리스트 형태로 저장되어있다.
    
    value = 100;
    if (num_set.find(value))
        cout << value << " is found!" << endl;
    else
        cout << value << " is not found!" << endl;
    
    num_set.print();
}

 

∙ 오픈 어드레싱 (open addressing)

- 해시 충돌이 발생할 경우, 해시 테이블에서 다른 비어 있는 버킷을 찾아 데이터를 저장하는 방식. 열린 주소 지정

- 해시 테이블의 크기가 데이터 개수보다 커야 함

- 새로운 위치 탐사(probing) 방식

> 선형 탐사

선형 탐사

    - 특정 해시 갑에서 충돌이 발생하면 해당 위치에서 하나씩 다음 위치로 이동하면서 비어 있는 위치에 원소를 삽입

    - 즉, h(key)가 사용 중이면 h(key) + 1, h(key) + 2...순서로 빈 위치를 찾음

    - 데이터가 특정 위치에 군집화 되는 경우, 해싱 효율이 떨어질 수 있음

> 제곱 탐사

제곱 탐사

    - 고정 크기로 이동하는 선형 탐사와 달리 제곱수 크기로 이동하면서 비어 있는 위치를 찾는 방식

    - 즉, h(key)가 사용중이면 h(key)+1^2, h(key)+2^2,... 순서로 빈 위치를 찾음

    - 군집화를 피하기 위해 간격을 두고 데이터를 삽입하는 방식

 

∙ 실수 해시 함수

- 주어진 실수를 조작하거나 또는 실수의 각 숫자를 조합하여 해시 값 생성

ex) 실수 키 x가 주어질 경우, 0에서 1 사이의 임의의 실수 A를 곱한 결과의 소수점 아래 부분을 s로 설정, 이후 s에 정수 m을 곱한 후, 소수점 아래를 버림으로써 [0, m-1] 사이의 정수를 얻을 수 있음

 

∙ 문자열 해시 함수

-  문자열의 각 문자를 ASCII코드로 변환하고, 이 값을 조합하여 해시 값 생성

ex) "cat" 문자열을 정수 형태로 변환할 경우 'c' = 99, 'a' = 97, 't' = 116이므로 이후 해시 테이블 크기에 맞게 나머지 연산을 수행

 

∙ 좋은 해시 함수의 조건

- 빠르고 효율적인 연산

- 해시 값이 균일하게 분포

> 충돌 최소화

> 해시 테이블 사용 효율이 높을 것

> 사용할 키의 모든 정보를 이용