해시 테이블과 블룸 필터 (1) - 해시 테이블이란

 

해시 테이블과 블룸 필터를 알면 좋은 이유

 

• 대용량 데이터를 다루는 응용 프로그램에서 발생할 수 있는 룩업 관련 문제에 대해 이해할 수 있다.
• 주어진 문제에 대해 결정적 룩업 솔루션이 적합한지,
  또는 비결정적 룩업 솔루션이 적합한지를 구분할 수 있다.
• 시나리오에 근거한 효율적인 룩업 솔루션을 구현할 수 있다.
• C++ STL에서 제공되는 일반적인 솔루션을 구현할 수 있다.

 

룩업은 특정 원소가 컨테이너에 있는지 확인하거나

또는 컨테이너에서 특정 키에 해당하는 값을 찾는 작업을 의미한다.

데이터 베이스 시스템이나 병원 관리 시스템에 저장된 방대한 자료 중에서

원하는 자료를 찾아 가져오는 작업과 같은 사례에

훨씬 빠르게 수행할 수 있는 효과적인 알고리즘이 필요할 때가 있는데,

해시 테이블과 블룸 필터라는 두 가지 효과적인 구조가 이에 적합하다.

 

 

해시 테이블

 해시 테이블의 핵심은 해싱이다.

해싱은 각각의 데이터를 가급적 고유한 숫자 값으로 표현하고,

나중에 같은 숫자 값을 사용하여 데이터의 유무를 확인하거나

또는 해당 숫자에 대응하는 원본 데이터를 추출하는 작업이다.

주어진 데이터로부터 고유한 숫자 값을 계산하는 함수를 해시 함수라고 한다.

 

가장 간단한 방법은 부울 타입의 배열을 하나 만들고,

입력 정수를 이 배열 원소의 인덱스로 취급하는 것이다.

만약 새 원소를 삽인한다면 해당 인덱스의 배열 값을 1로 설정한다.

즉, 새 원소 x를 삽입할 경우 data[x] = true로 설정한다.

특정 정수 x가 있는지를 알고 싶다면 단순히 data[x] 값이 true인지를 확인하면 된다.

이런 방식을 사용할 경우, 원소 삽입, 삭제, 검색의 시간 복잡도는 O(1)이다.

0부터 9 사이의정수를 저장하는 용도의 해시 테이블은

다음과 같은 경우에 문제가 발생할 수 있다.

 

• 데이터가 실수인 경우
• 데이터가 숫자가 아닌 경우
• 데이터 범위가 너무 큰 경우,
  예를 들어 10억 개의 숫자를 사용한다면
  10억 크기의 부울 타입 배열이 필요한데, 이는 좋은 방법이 아니다.

 

 이 문제를 해결하기 위해 어떤 데이터 타입의 값이든

원하는 범위의 정수로 매핑하는 함수를 만들어 사용할 수 있다.

이 경우 원하는 정수 범위를 적절히 설정하면 부울 타입 배열을 만드는 것이 전혀 부단되지 않을 것이다.

이러한 역할을 하는 함수가 바로 앞에서 언급했던 해시 함수이다.

이 함수는 데이터 원소를 인자로 받고 정해진 범위의 정수를 반환한다.

 

가장 간단한 해시 함수는 큰 범위의 정수를 인자로 받아

정해진 정수(n)로 나눈 나머지를 반환하는 모듈로 함수(modulo function)이며, 보통 % 기호로 표시한다.

이 경우 크기가 n인 배열을 사용할 수 있다.

 

만약 이 함수에 숫자 x를 입력으로 주면 (x % n) 연산 결과가 반환되고,

이 값은 0부터 (n - 1) 사이의 정수이다.

예를 들어 ( 9 % 7 )과 (16 % 7 )은 모두 해시 값으로 2를 반환한다.

그러므로 해시 값 2에 해당하는 위치가 true (또는 1)로 채워져 있을 경우,

여기에 들어 있는 데이터가 9인지 혹은 16인지를 알 수 없다.

이러한 문제를 충도링라고 한다.

즉, 충돌이란 해시 함수가 서로 다른 키에 대한 같은 해시 값을 반환함으로써,

다수의 키가 같은 값을 갖게 되는 현산을 말한다.

 

해시 테이블에 부울 값 대신 실제 데이터를 저장하면

해당 키에 어떤 데이터가 저장되어 있는지를 알 수 있지만

여전히 여러 데이터를 저장할 수는 없다.

이는 해시 테이블에서 충돌을 의미한다.

 

 

해시 테이블 연습문제 : 정수 값을 저장하는 간단한 사전

 

 

 

이번 연습 문제에서는 부호 없는 정수를 사용하는 기본적인 해시 맵을 구현하는 것을 목표로 한다.

 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>


// unsigned int 타입 이름 대신 짧게 uint로 사용하기 위해 지정해준다.
using uint = unsigned int;


// hash_map 클래스를 추가한다.
class hash_map
{
    std::vector<int> data;

    // hash_map 클래스의 생성자를 추가한다.
    // 이 생성자는 해시 맵에서 사용할 데이터 크기를 인자로 받는다.
public:
    hash_map(size_t n)
    {
        data = std::vector<int>(n, -1);
    }

    // 삽입 함수 추가
    void insert(uint value)
    {
        int n = data.size();
        data[value % n] = value;
        std::cout << value << "을(를) 삽입했습니다" << std::endl;
    }
    // 위 코드를 보면 계산된 해시 값 위치에 이미 다른 값이 존재하는지를 확인하지 않는다.
    // 즉, 특정 위치에 이미 다른 값이 존재하더라도 단순히 덮어쓰게 된다.
    // 결국 해시 값이 중복될 경우 나중에 삽입한 값만 저장하게된다.

    // 특정 원소가 맵에 잇는지 확인하는 룩업 함수를 추가한다.
    bool find(uint value)
    {
        int n = data.size();
        return (data[value % n] == value);
        // 해시 값 위치에 저장된 값이 value와 같은지를 검사한다.
    }
    
    // 삭제 함수를 구현한다.
    void erase(uint value)
    {
        int n = data.size();
        if (data[value % n] == value)
        {
            data[value % n] = -1;
            std::cout << value << "을(를) 삭제했습니다." << std::endl;
        }
    }
};


// main() 함수 내부에 룩업 결과를 출력하는 람다 함수를 정의하여 사용하겠다.
int main()
{
    hash_map map(7);

    auto print = [&](int value) {
        if (map.find(value))
            std::cout << "해시 맵에서" << value << "을(를) 찾았습니다.";

        else
            std::cout << "해시 맵에서 " << value << "을(를) 찾지 못했습니다.";

        std::cout << std::endl;
    };

    // insert와 erase의 사용 예시
    map.insert(2);
    map.insert(25);
    map.insert(10);
    print(25);

    // 100 % 7 의 값은 2와 중복으로 2는 삭제 100은 2를 덮어쓴다.
    map.insert(100);
    print(100);
    print(2);

    map.erase(25);
    

    return 0;

}

 

 

연습 문제에서 봤듯이 해시 값을 갖는 두 원소를 한꺼번에 저장할 수 없고,

하나를 포기해야 했다.

 

앞서 언급했듯이 해시 테이블을 사용할 때

단순히 해당 키가 있는지를 확인하는 거싱 아니라

해당 키에 대응하는 값이 있는지를 확인해야 한다.

이를 위해 해시 테이블에 키만 저장하는 거싱 아니라 키와 값을 함꼐 저장하는 방식을 사용해야 한다.

그러므로 삽입, 삭제, 룩업 함수에서 키를 기반으로 해시 값을 계산하여 배열에서의 위치를 알아낸 후,

함게 저장된 값을 이용할 수 있어야한다.