[알고리즘] 해시 테이블(Hash Table)

1. 해시 테이블

- 완전 탐색(브루트 포스)으로 시간초과에 빠지게 되는 문제들을 풀기 위해 필요함

- Key, Value로 데이터를 저장하는 자료구조

- 데이터를 빠르게 검색할 수 있음

- 각 key에 따라 고유한 index를 생성하고 이 index 값을 활용해 값을 저장하거나 검색한다.

- 미리 key값으로 데이터들을 저장해 놓으면 데이터를 찾기 쉽다.

- 평균 시간복잡도 : O(1)

 

2. 해시 함수에서 고유 인덱스 값을 설정하는 방법

1) Division Method

- 나눗셈을 이용하는 방법

- 입력값을 테이블의 크기로 나누어 계산

- 테이블의 크기를 소수로 정하고 2의 제곱수와 먼 값을 사용해야 효과가 좋다고 알려짐

 

2) Digit Folding

- 각 key의 문자열을 ASCII 코드로 바꾸고 값을 합한 데이터를 테이블 내의 주소로 사용하는 방법

 

3) Multiplication Method

- 숫자로 된 key값 k와 0과 1사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 아래와 같이 계산

- h(k) = (kAmod1) x m (mod는 moduler의 약자로 나머지를 뜻함)

 

4) Univeral Hashing

- 다수의 해시함수를 만들어 집합 H에 넣어두고, 무작위로 해시함수를 선택해 해시값을 만드는 기법

 

3. 해시 값이 충돌할 경우 해결법

1) 분리 연결법(Separate Chaining)

- 동일한 버킷(Value를 담고있는 곳)의 데이터에 대해 자료구조를 활용해 추가 메모리를 사용하여 다음 데이터 주소를 저장하는 방법

- 해시 테이블의 확장이 필요없고 간단하게 구현 가능하며 손쉽게 삭제할 수 있음

- 데이터의 수가 많아지면 동일한 버킷에 chaining되는 데이터가 많아져 캐시의 효율성이 감소

 

2) 개방 주소법(Open Addressing)

- 비어있는 해시 테이블의 공간을 활용하는 방법

[1] Linear Probing : 현재의 버킷 index로부터 고정폭 만큼씩 이동하여 차례대로 검색해 비어있는 버킷에 데이터를 저장

[2] Quadratic Probing : 해시의 저장순서 폭을 제곱으로 저장하는 방식

[3] Double Hashing Probing : 해시된 값을 한번 더 해싱하여 해시의 규칙성을 없애버리는 방식

 

4. 소스코드(C++)

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

using namespace std;

static const int HASH_SIZE = 1000; // 가질 수 있는 키 값의 갯수
static const int HASH_LEN = 400; // 중복될 수 있는 키 값의 갯수
static const int HASH_VAL = 17; // 소수로 설정 -> key값을 구하기 위해 사용

static int _data[HASH_SIZE][HASH_LEN];
static int _length[HASH_SIZE];

static string s_data[HASH_SIZE][HASH_LEN];
static string str;

// 해시키를 구하는 함수
int getHashKey(string str)
{	
    int key = 0;
    
    for(int i = 0; i < str.length(); i++)
    {
    	// 해시 키 값 생성
    	key = (key * HASH_VAL) + str[i] + HASH_VAL;
    }
    
    // 키가 음수인 경우 양수로 변경
    if(key < 0) key = -key;
    
    // 키가 너무 큰 경우를 대비해 HASH_SIZE보다 작도록 HASH_SIZE로 나눈 나머지 사용
    return key % HASH_SIZE;
}

// 키가 중복되는지 확인하는 함수
int checking(int key)
{	
    // 현재 key로 찾은 value 값
    int len = _length[key];
    
    // 이미 들어온 적이 있는 경우
    if(len != 0)
    {
    	for(int i = 0; i < len; i++)
        {
        	// 이미 들어온 문자열이 해당 key 배열에 있는지 확인
        	if(str == s_data[key][i])
            {
            	// 같은 문자열이 있다면 현재 key의 index를 증가시킴
				_data[key][i]++;
                return _data[key][i];
			}
		}
        
        // 들어온 적이 없었던 경우 해당 key 배열의 문자열을 저장하고 배열의 길이를 늘림
        s_data[key][_length[key]++] = str;
        
        // 처음 들어가는 경우에는 -1을 리턴
        return -1;
    }
}

int main()
{	
    int N; // 반복 횟수
    
    for(int i = 0; i < N; i++)
    {
    	cin >> str; // 사용자의 입력 문자열을 받아옴
        
        int key = getHashKey(str); // 입력받은 문자열의 키값
        int cnt = checking(key); // 키값의 중복 체크(같은 키 값중 몇번째인지를 의미)
        
        // 처음 들어가는 경우가 아닌 경우 -> 중복 키 값이 있는 경우
        if(cnt != -1)
        {
        	// 복수 키 값인 경우
        	cout << key << " ";
            cout << cnt << endl;
		}
        else 
        {
        	// 단일 키 값인 경우
        	cout << "OK" << endl;
        }        
    }
    
    return 0;
}