자료구조 :: 해싱(1) 정의, 해싱의구조, 해시함수

# 해싱

일반 적인 탐색 방법에 반하여 해싱은 키 값에 직접 산술적인 연산을 적용하여 항목이 저장되어 있는 테이블의
주소를 계산하여 항목에 접근한다. 이렇게  키값 연산에 의해 직접 접근이 가능한 구조를 해시테이블이라 부르며,
해시테이블을 이용한 탐색을 해싱이라 한다.

해싱은 이론적으로는 O(1)의 시간안에 탐색을 끝마칠 수도 있다. 해싱은 보통 사전과 같은 자료구조를 구현 할때
최상의 선택이 된다.


# 해싱의 구조

해싱에서는 자료를 저장하는데 배열을 사용한다. 배열은 단점도 있지만 만약 원하는 항목이 들어 있는 위치를
알고 있다면 매우 빠르게 자료를 삽입하거나 꺼낼 수 있다. 이 경우, 배열의 다른 요소들에는 전혀 접근할 필요가
없다. 해싱이란 이런 식으로 어떤 항목의 탐색 키만을 가지고 바로 항목이 들어 있는 배열의 인덱스를 결정하는
기법이다. 해시함수(hash function)란 탐색 키를 입력으로 받아 해시 주소(hash address)를 생성하고 이 해시
주소가 배열로 구현된 해시 테이블(hash table)의 인덱스가 된다. 이 배열의 인덱스의 위치에 자료를 저장 할수도
있고 거기에 저장된 자료를 꺼낼 수도 있다.

예를들어 영어 사전에서는 단어가 탐색키가 돠ㅣ고 이 단어를 해싱함수를 이용하여 적절한 정수i로 변환한 다음
배열 요소 ht[i]에 단어의 정의를 저장하는 것이다.
해시테이블 ht는 M개의 버켓으로 이루어지는 테이블로서 ht[0],ht[1].ht[M-1]의 원소를 가진다. 하나의 버켓은
s개의 슬롯을 가질 수 있으며, 하나의 슬롯에는 하나의 항목이 저장된다. 하나의 버켓에 여러개의 슬롯을 두는
이유는 서로 다른 두 개의 키가 해시 함수에 의해 동일한 해시 주소로 변환된수 있으므로 여러 개의 항목을 동일한
버켓에 저장하기 위함이다.

해시테이블에 존재하는 버켓의 수가 M이므로 해시 함수 h는 모든 키에 대하여 0≤h(x)≤M-1의 범위의 값을 제공
해야 한다. 대부분의 경우 해시테이블의 버켓 수는 키가 가질 수 있는 모든 경우의 수보다 매우 작으므로 여러개의
서로 다른 탐색 키가 해시 함수에 의해 같은 해시 주소로 맵핑되는 경우가 자주 발생한다.
서로 다른 두 개의 탐색키 k1과 k2에 대하여 h(k1) = h(k2)인 경우를 충돌(collision)이라고 하며, 이러한 키 k1과
k2를 동의어(synonym)라 한다. 만약 충돌이 발생하면 같은 버켓에 있는 다른 슬롯에 항목을 저장하게 된다.
충돌이 자주 발생하면 버켓 내부에서의 순차 탐색 시간이 길어져서 탐색 성능이 저하 될 수 있으므로 해시함수를
수정하거나 해시테이블의 크기를 적절히 조절해주어야 한다.
이러한 충돌이 버켓에 할당된 슬롯 수보다 많이 발생하게 되면 버켓에 더 이상 항목을 저장할 수 없게 되는 오버
플로우가 발생하게 된다. 만약 버켓 당 슬롯의 수가 하나(s=1)이면 충돌이 곧 오버플로우를 의미한다.
오버플로우가 발생하면 더 이상 항목을 저장할 수 없게 되므로오버플로우를 해결하기 위한 방법이 필요하다.


# 해시 함수

해싱에서는 키 값을 해시테이블의 주소로 변환하는 해시 함수가 잘 설꼐되어야만 탐색의 효율이 증대될 수 있다.
좋은 해시 함수의 조건은 다음의 3가지 이다.

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

1. 제산함수

제산함수는 나머지 연산자를 사용하여 탐색 키를 해시 테이블의 크기로 나눈 나머지를 해시 주소로 사용하는 방법
이다. 즉, 탐색키 k에 대해서 다음과 같은 연산식을 만들 수 있다. 

h(k) = k mod M

여기서 M은 해시 테이블의 크기로서 해시 함수의 값의 범위는 0~(M-1)이 된다. 따라서 해시테이블의 인덱스로
사용하기는 이상적인 값이 된다. 이는 가장 일반적인 해시 함수로서 해시 테이블의 크기 M으로 사용하는 수는
소수(prime number)로 나누어지지 않는 수로 선택한다.

M의 선택이 중요한 이유는 예를 들어 M이 짝수라면 k mod M은 k가 짝수이면 짝수가 되고 k가 홀수라면 홀수가
된다. 이런식으로 해시 주소가 한쪽으로 편향된다면 해시 테이블을 골고루 사용하지 않는 것이 되서 이는 결과적
으로 좋지 않다. 따라서 테이블의 크기인 M은 항상 홀수여야 하며 소수를 사용할 경우 0~(M-1)을 골고루 사용하는
값을 만들어 낸다.
만약 나머지 연산을 수행했을 때 음수가 나올 가능성에도 대비해야 한다. 따라서 k mod M이 음수라면 여기에 M을
더해서 결과값이 항상 0에서 M-1이 되도록 하여야 한다.

[나머지를 이용한 해시함수]

int hash_function(int key) 
{ 
int hash_index=key%M; 
if(hash_index < 0) 
        hash_index+=M; 
return hash_index; 
}

2. 폴딩함수

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

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

폴딩 함수는 탐색키를 여러부분으로 나누어 모두 더한 값을 해시 주소로 사용한다. 탐색키를 나누고 더하는 방법
에는 이동폴딩과 경계폴딩이 대표적이다. 이동폴딩은 탐색키를 여러부분으로 나눈 값들을 더하여 해시주소로
사용하고, 경계폴딩은 탐색키를 이웃한 부분을 거꾸로 더하여 해시 주소를 얻는다.
예를 들어 키값이 12320324111220일때 이동폴딩과 경계폴딩은 다음과 같이 나타낼 수 있다.

탐색키 : 123 203 241 112 20
이동폴딩 : 123 + 203 + 241 + 112 + 20 = 699
경계폴딩 : 123 + 302 + 241 + 211 + 20 = 897


3. 중간 제곱 함수

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


4. 비트 추출 방법

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


5. 숫자 분석 방법

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