[자료구조] 해시 테이블(1)

해시 테이블

• lookup(룩업, 조회)는 특정 원소가 컨테이너에 있는지 확인하거나 또는 컨테이너에서 특정 키(key)에 해당하는 값(value)를 찾는 작업을 의미한다
  • DB에서 원하는 자료를 찾거나, 사전에서 단어의 뜻을 찾는 문제들이 이에 해당
• 모든 원소를 선형으로 검토하여 원하는 값을 찾는 작업은 일반적으로 매우 많은 시간이 소요된다
  • O(N) 시간 복잡도를 가짐
• 이 작업을 훨씬 빠르게 수행할 수 있는 효과적인 알고리즘이 필요하다.
  • 해시 테이블과 블룸 필터라는 효과적인 구조에 대해 살펴본다.

해시 테이블

• O(N)을 갖는 선형 검색보다 더 나은 검색 방법은 BST와 같은 속성을 갖도록 높이 균형 트리에 데이터를 저장하는 것이다.
  • 시간 복잡도가 O(log N)이므로 선형 검색보다 훨씬 빨라진다
  • 검색 횟수가 증가하면 이 정도 연산 속도도 만족스럽지 않을 수 있다.
• 해시 테이블(hash table) 이 괜찮은 효율적인 방법 중 하나이다
• 해시 테이블의 핵심은 해싱(hashing)이다.
  • 해싱(hashing) : 각각의 데이터를 가급적 고유한 숫자 값으로 표현하고, 나중에 같은 숫자 값을 사용하여 데이터의 유뮤룰 확인하거나 또는 해당 숫자에 대응하는 원본 데이터를 추출하는 작업
  • 해시 함수(hash function) : 주어진 데이터로부터 고유한 숫자 값을 계산하는 함수

해싱

정수를 저장하고 있는 컨테이너가 있고, 이 컨테이너에 특정 정수가 들어 있는지 빠르게 판단하고 싶은 상황

• 가장 간단한 방법은 부울 타입 배열을 하나 만들고, 입력 정수를 이 배열 원소의 인덱스로 취급하는 것
  • data[x] = true
  • 이 방식에서 원소 삽입, 삭제, 검색의 시간 복잡도는 O(1)

• 위 방법의 문제점
  • 데이터가 실수인 경우 어떻게 저장할건가?
  • 데이터가 숫자가 아닌 경우 어떻게 저장할건가?
  • 데이터 범위가 너무 큰 경우
    • ex) 10억개의 숫자를 사용한다면 10억 크기의 부울 타입 배열이 필요하다
• 위 문제를 해결하기 위해 어떤 데이터 타입의 값이는 원하는 범위의 정수로 매핑하는 함수를 만들어 사용할 수 있다
  • 이 경우 원하는 정수 범위를 적절히 설정하면 부울 타입 배열을 만드는 것이 부담되지 않음
  • 이러한 역할을 하는 함수가 위에서 언급했던 해시 함수이다.
    • 이 함수는 데이터 원소를 인자로 받고 정해진 범위의 정수를 반환함
• 가장 간단한 해시 함수는 큰 범위의 정수를 인자로 받아 정해진 정수(n)으로 나눈 나머지를 반환하는 모듈로 함수(modulo function)이며, 보통 % 기호로 표시한다.
  • 이 경우 크기가 n인 배열을 사용할 수 있다
  • 해시 함수에 의해 반환되는 숫자 값을 해시 값(hash value)라고 한다
• 모듈로 함수의 문제점은, 이 함수가 서로 다른 데이터에 대해 같은 해시 값을 반환할 수 있다는 점이다
  • ex) 9 % 7과 16 % 7은 모두 해시값으로 2를 반환하는데, [2]에 들어 있는 데이터가 9인지 16인지, 또는 이를 만족하는 다른 정수인지를 알 수 없다
  • 이러한 문제를 충돌(collision)이라고 한다.
    • 즉, 해시 함수가 서로 다른 키에 대해 같은 해시 값을 반환함으로써 다수의 키가 같은 값을 갖게 되는 현상을 말한다
• 해시 테이블에 부울 값 대신 실제 데이터를 저장하면 해당 키에 어떤 데이터가 저장되어 있는지를 바로 알 수 있지만, 여전히 여러 데이터를 저장할 수는 없다
  • 해결 방법은 아래에 다시 나올거에요

Example) 정수 값을 저장하는 간단한 사전

#include <iostream>
#include <vector>

using uint = unsigned int;

class hash_map
{
    std::vector<int> data;

public:
    // 모든 원소를 -1로 초기화
    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);
    }

    // 삭제 함수
    void erase(uint value)
    {
        int n = data.size();

        if(data[value % n] == value)
        {
            data[value % n] = -1;

            std::cout << value << "을(를) 삭제했습니다." << std::endl;
        }
    }
};

using namespace std;

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;
    };

    map.insert(2);
    map.insert(25);
    map.insert(10);
    print(25);

    map.insert(100);
    print(100);
    print(2);

    map.erase(25);

    return 0;
}

 

 

• 해시 테이블을 사용할 때 단순히 해당 키가 있는 지를 확인하는 것이 아니라 해당 키에 대응하는 값이 있는지를 확인해야 한다
  • 이를 위해 키와 값을 함께 저장하는 방식을 사용해야 한다
• 삽입, 삭제, 룩업 함수에서 키를 기반으로 해시 값을 계산하여 배열에서의 위치를 알아낸 후 함께 저장된 값을 이용할 수 있어야 한다