해시 테이블(Hash Table)

코딩 테스트를 위한 자료 구조와 알고리즘 with C++

 

 

빠른 검색의 필요성

• 선형 검색은 O(n) 복잡도를 갖는다.
• 균형 트리에서의  검색은 O(log n) 복잡도를 갖는다.

유전자 데이터처럼 수백 수천만의 데이터가 저장된 경우에는 훨씬 효과적인 검색 방법이 필요하다.

 

 

해시 함수

주어진 입력을 고정 길이의 고유한 값으로 변환하는 단방향 함수이다.
그러므로 해시 값을 통해 원본 문자열을 복원하는 역함수는 존재하지 않는다.
좋은 해시 함수는 중복 확률이 낮은 함수이다.

해싱

해시 함수로 계산한 값을 통해 자료 저장 주소를 찾아내는 탐색 방법이다.

 

해시 테이블

• 해시 함수로 계산한 값을 인덱스로 하여 키(해시)와 값을 저장하는 자료구조이다.
• 키 값만 가지고는 테이블에 원소가 존재하는지 알 수 없고 값도 함께 확인해야 한다.

 

해시 테이블의 사용 예

• 데이터베이스 시스템
• 사전에서 단어와 뜻

 

입력된 양수를 맵의 크기로 나눈 나머지를 해시 값으로 하는 간단한 해시 맵 구현 예시

 

#include <iostream>
#include <vector>

using namespace std;
using uint = unsigned int;

class hash_map
{
    vector<int> data;

public:
    hash_map(size_t n) : data(vector<int>(n, -1)) {}

    void insert(uint value)
    {
        data[hash(value)] = value;

        cout << value << "을(를) 삽입했습니다." << endl;
    }

    bool find(uint value)
    {
        return (data[hash(value)] == value);
    }

    void erase(uint value)
    {
        uint hs = hash(value);

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

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

private:
    uint hash(uint value)
    {
        return value % data.size();
    }
};

void main()
{
    hash_map map(7);

    auto print = [&](int value)
    {
        if (map.find(value))
            cout << "해시 맵에서 " << value << "을(를) 찾았습니다.";
        else
            cout << "해시 맵에서 " << value << "을(를) 찾지 못했습니다.";
        cout << endl;
    };

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

    // 2와 100의 해시 값은 같다.
    map.insert(100);
    print(100);
    print(2);

    map.erase(25);
}

 

출력

2을(를) 삽입했습니다.
25을(를) 삽입했습니다.
10을(를) 삽입했습니다.
해시 맵에서 25을(를) 찾았습니다.
100을(를) 삽입했습니다.
해시 맵에서 100을(를) 찾았습니다.
해시 맵에서 2을(를) 찾지 못했습니다.
25을(를) 삭제했습니다.