해싱

해싱

해싱은 키값을 비교하는 것이 아니라 탐색키에 산술적인 연산을 적용하여 항목이 저장되어 있는 위치, 즉 인덱스를 직접 계산하는 방식이다. 이렇게 키값의 연산에 의해 직접 접근이 가능한 구조를 해시 테이블(hash table)이라 하며, 해시 테이블을 이용한 탐색을 해싱(hashing)이라 한다.

예를 들어 탐색키들이 모두 1 ~ 1000 사이의 정수라고 가정해보자. 그렇다면 가장 빠르게 자료를 저장하고 꺼낼 수 있는 방법은 1000개의 요소를 가지는 배열을 만드는 것이다. 자료의 삽입과 탐색은 탐색키를 배열의 인덱스로 생각하고 단지 배열의 특정 요소를 읽거나 쓰면 된다. 이들 연산은 명백하게 이다. 이것이 해싱의 기본 아이디어이다.

현실적으로는 탐색키들이 문자열이거나 굉장히 큰 숫자이기 때문에 탐색키를 직접적으로 배열의 인덱스로 사용하지 못하고 각 탐색키를 작은 정수로 사상(mapping)시키는 어떤 함수가 필요하다. 이것을 해시 함수(hash function)라고 한다. 해시 함수는 탐색키를 입력 받아 해시 주소(hash address)를 계산하는데, 삽입이나 삭제, 탐색 연산은 모두 이 주소에서 이루어진다.

해시 테이블은 버켓(bucket)으로 이루어지는 테이블이고, 하나의 버켓에는 각각 레크드를 저장할 수 있는 여러 개의 슬롯(slot)을 가진다. 이것은 여러 개의 탐색키가 동일한 해시 주소로 변환될 수 있기 때문이다.

해시 테이블의 버켓의 수가 제한적이므로 경우에 따라 서로 다른 키 k1 과 k2 가 해시함수에 의해 같은 주소, 즉 h(k1) == h(k2) 로 계산되는 상황이 발생한다. 이것을 충돌(collision)이라고 하고, 이러한 키 k1 과 k2 를 동의어(synonym)라 한다.  

충돌이 발생하면 어떻게 할까? 만약 버켓에 여러 개의 슬롯이 있다면 k1 과 k2 를 각각 다른 슬롯에 저장하면 된다. 그러나 충돌이 슬롯 수보다 더 많이 발생할 수도 있는데, 이러한 상황을 오버플로우(overflow)라고 한다. 이 경우 해당 버켓에 더 이상 항목을 저장할 수 없게 된다. 따라서 해싱에서는 오버플로우를 해결하기 위한 방법이 반드시 필요하다.

• 해시 함수
  

좋은 해시 함수의 조건은 다음의 3가지이다.

• 충돌이 적어야 한다.
• 해시 함수 값이 해시 테이블의 주소 영역 내에서 고르게 분포 되어야 한다.
• 계산이 빨라야 한다.

예를 들면 영어 단어의 첫 문자만을 취하여 해시 함수로 사용하는 것은 좋지 않다. 왜냐하면 x나 z로 시작하는 단어는 별로 없기 때문이다. 즉, 이 경우 해시 테이블을 균일하게 사용하지 않는다. 먼저 탐색키가 정수라고 가정하고 해시 함수들을 살펴보자.

• 제산 함수
  

가장 일반적인 방법이 나머지 연산자 mod(C++에서 % 연산자)를 사용하는 것이다. 테이블의 크기가 M일 때 탐색키 k에 대하여 해시 함수는 다음과 같다.

h(k) = k mod M

이때, 가능하면 해시 주소를 더 고르게 분포시키기 위해 해시 테이블의 크기 M은 소수(prime number)를 선택한다. 즉, 1과 자기 자신만을 약수로 가지는 수라면 K mod M 은 0에서 M - 1 을 골고루 사용하는 값을 만들어 낸다.

• 폴딩 함수
  

폴딩 함수는 주로 탐색키가 해시 테이블의 크기보다 더 큰 정수일 경우에 사용된다. 예를 들어, 탐색키는 32비트이고 해시 테이블의 인덱스는 16비트 정수인 경우이다. 만약 이런 경우, 탐색키의 앞의 16비트를 무시하고 뒤의 16비트를 해시코드로 사용한다면, 앞의 16비트만 다르고 뒤의 16비트는 같은 탐색키의 경우, 충돌이 발생할 것이다. 따라서 탐색키의 일부만 사용하는 것이 아니고 탐색키를 몇 개의 부분으로 나누어 이를 더라거나 비트별로 XOR 같은 부울 연산을 하는 것이 보다 좋은 방법이다. 이것을 폴딩(folding)이라고 한다. 예를 들어, 32비트 키를 2개의 16비트로 나눠 비트별로 XOR 연산을 하는 코드는 다음과 같다.

hash_index = (short)(key ^ (key >> 16))

폴딩 함수는 탐색키를 여러 부분으로 나누어 모두 더한 값을 해시 주소로 사용한다. 탐색 키를 나누고 더하는 방법에는 이동 폴딩(shift folding) 과 경계 폴딩(boundary folding)이 대표적이다. 이동 폴딩은 탐색키를 여러 부분으로 나눈 값들을 더하고, 경계 폴딩은 이웃한 부분을 거꾸로 더해 해시 주소를 얻는다.

• 중간 제곱 함수

중간 제곱 함수는 탐색키를 제곱한 다음, 중간의 몇 비트를 취해서 해시 주소를 생성한다. 제곱한 값의 중간 비트들은 대개 탐색키의 모든 문자들과 관련이 있기 때문에 서로 다른 탐색키는 몇 개의 문자가 같을 지라도 서로 다른 해싱 주소를 갖게 된다. 탐색키 값을 제곱한 값의 중간 비트들의 값은 비교적 고르게 분산된다.

• 비트 추출 방법
  

해시 테이블의 크기가 M = 일때 탐색키를 이진수로 간주하여 임의의 위치의 k개의 비트를 해시 주소로 사용하는 것이다. 이 방법은 아주 간단하지만 탐색키의 일부 정보만을 사용하므로 해시 주소의 집중 현상이 일어날 가능성이 높다.

• 숫자 분석 방법
  

이 방법은 숫자로 구성된 키에서 각 위치마다 수의 특징을 미리 알고 있을 때 유용하다. 키의 각각의 위치에 있는 숫자 중에서 편중되지 않은 수들을 해시 테이블의 크기에 적합한만큼 조합하여 해시 주소로 사용하는 방법이다. 예를 들어, 학생의 학번이 2017305057 라 한다면 입학 년도를 의미하는 앞의 4자릿수는 편중되어 있으므르 가급적 사용하지 않고 나머지 수를 조합하여 해시 주소로 사용한다.

• 탐색키가 문자열인 경우
  

탐색키가 문자열인 경우는 보통 각 문자에 정수를 대응시켜 바꾸게 된다. 예를 들면 'a'부터 'z'에 1부터 26 을 할당할 수도 있고, 각 문자의 아스키 코드나 유니코드 값을 그대로 이용할 수 있다. 가능하면 문자열 안의 모든 문자를 골고루 사용하는 것이 좋을 것이다. 다음 함수는 아스키 값을 모두 더하는 방법을 사용한다.

---

#pragma once

#ifndef ___HashFunctions

#define ___HashFunctions

// hashFunctions.h : inline 해시 함수들

#define TABLE_SIZE 13 //해싱 테이블의 크기 (소수를 사용)

// 문자열로 된 탐색키를 숫자로 변환 : 간단한 덧셈 방식

inline int transform(const char* key) {

int number = 0;

while (*key)

number += (*key);

return number;

}

// 해싱 함수 : 제산 함수 사용

inline int hashFuntion(char *key) {

return transform(key) % TABLE_SIZE;

}

#endif // !___HashFunctions

---

물론 최종적인 해시 주소는 문자열을 정수로 변환한 값에 해시 함수를 적용하여 만들어진다. 위에서 hashFunction() 함수는 제산 함수를 사용하였다.