해시(Hash)

 

  1. 해싱을 이용한 탐색

 

다양한 방법으로 구현한 맵의 최고성능은 시간 복잡도 O(logn)이다.

그러나, 이보다 더 빠른 탐색시간을 갖는 해싱으로 맵을 구현하면 탐색 연산의 이론적인 시간 복잡도가 O(1)이 된다.

 

  1.1 해싱이란?

  해싱은 하나의 문자열을 보다 빨리 찾을 수 있도록 해시 함수에 문자열 입력값을 넣어, 주소에 직접 접근할 수 있는 짧은 길이의 값이나 키 특정한 값으로 추출하는 것을 의미한다. 

 

  문자열을 찾을 때, 키값의 문자를 일일이 비교하는 것이 아니라, 문자열에 산술적인 연산으로 해시 키를 계산하여 인덱스(항목이 저장된 위치)에 직접 문자열을 저장해 둔다면, 찾을 때는 한 번의 해시 키 계산만으로 도 쉽게 찾을 수 있게된다.

이렇게 키값의 연산에 의해 직접 접근이 가능한 구조를 Hash Table(해시 테이블)이라 하며, 해시 테이블을 이용한 탐색을 Hashing(해싱)이라 한다.

 

해싱은 기본적으로 데이터를 흩뜨려놓는 성질이 있기 때문에 메모리를 많이 차지하는 단점이 있으나, 빠른 검색과 원문과 상관없는 비화된 문자열의 특성이 있어 '전자서명 알고리즘'에서 암호화 및 복호화에도 사용된다.

 

 

Ex) 탐색키들이 모두 1~1000 사이의 정수의 경우.

  - 가장 빠르게 자료를 저장하고 꺼낼 수 있는 방법은 1000개의 요소를 가지는 배열을 만드는 것. [O(1)]

  - 이를 바탕으로, 자료의 삽입과 탐색은 탐색키를 배열의 인덱스로 생각하고 단지 배열의 특정 요소를 읽거나 쓰면 된다는 것이 해싱.

 

현실적으로 탐색키들이 문자열이거나 굉장히 큰 숫자이기 때문에, 해시 함수(Hash Function)를 통해 각 탐색키를 고장된 작은 길이의 정수로 Mapping시킨다. 해시 주소(Hash Address)는 탐색키를 입력받아 해시 함수로 계산된 주소로, 삽입이나 삭제, 탐색 연산은 모두 이 주소에서 이루어진다.

 

 

 

  1.2 해싱 구조

  키 (Key)

   해싱할 때의 입력값. 키는 중복되지 않는 고유한 값이다.

 

  해시 테이블 (Hash Table)

   해시 함수로 매핑한 키 값을 인덱스로 한 배열 또는 객체.(자바스크립트 기준)

   해시 테이블에서 행은 버켓 (Bucket), 열은 슬롯 (Slot)이라 한다.

 

  충돌 (Collision)

   키 값을 해싱해서 얻은 값들이 모두 고유한 값은 아니다.  또한, 해시 테이블의 버켓 수가 제한적이므로, 서로 다른 키 값이 하나의 주소로 매핑될 수 있는데, 이를 해싱 충돌이라 한다.(이러한 키 k1과 k2를 동의어(synonym)라 함)

 

  해싱 충돌은 암호와 관련된 보안에서는 보안이 뚫리는 심각한 문제가 발생할 수 있으므로 대비할 필요가 있다.

 

  아래 그림 은 해싱의 구조를 보여준다. 키값 k를 입력받아 해시 함수로 연산한 결과인 해시 주소 h(k)를 인덱스로 사용하여 해시 테이블에 있는 항목에 접근한다. 해시 테이블 ht는 M개의 버켓(bucket)으로 이루어지는 테이블이고, 하나의 버켓에는 각각 레코드를 저장할 수 있는 여러 개의 슬롯(slot)을 가진다. 이것은 여러 개의 탐색키가 동일한 해시 주소로 변환될 수 있기 떄문에, 여기서는 슬롯이 하나라고 생각하자.

 

※ 해싱의 구조

 

충돌이 발생하더라도, 만약 버켓에 여러 개의 슬롯이 있다면 k1과 k2를 각각 다른 슬롯에 저장하면 된다. 그러나 오버플로우(overflow)로 충돌이 슬롯 수보다 더 많이 발생할 수도 있어, 해당 버켓에 더 이상 항목을 저장할 수 없게 된다.

 

충돌이 절대 일어나지 않는 경우가 이상적이나,  메모리가 지나치게 많이 든다.

 

주민등록번호가 탐색키라고 생각해보자. 탐색키 당 하나의 공간을 할당하는 경우에는 해시 테이블에 엄청나게 많은 공간이 필요함을 알 수 있다. 보통의 경우에는 탐색키에 비하여 해시 테이블의 크기가 작다. 따라서 더 작은 해시 테이블을 사용하는 해시 함수를 고안해야 한다.

 

간단하면서도 강력한 방법은 나머지 연산을 이용하는 것이다. 탐색키 i를 해시 테이블 크기 M으로 나누어서 나머지를 취하면 0에서 M-1까지의 숫자가 생성되고, 해시 테이블을 위한 유효한 인덱스가 된다. 물론 이 해시 함수는 완벽한 해시 함수가 아니다. 두 개 이상의 탐색키가 동일한 해시 주소로 계산될 수 있다. 예를 들어, 테이블의 크기 M을 31이라 하면 h(1024) = 1024%31= 1과 h(1055) = 1055%31 = 1은 같은 주소를 만든다. 따라서 충돌이 발생했고, 슬롯이 하나이므로 바로 오버플로우 상황이 된다. 실제의 해싱에서는 충돌과 오버플로우가 빈번하게 발생하므로 시간 복잡도는 이상적인 경우의 O(1)보다는 떨어지게 된다.

 

 

  1.3 해시 함수

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

 

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

 

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

 

 

제산법

  가장 일반적인 방법이 나머지 연산자 % (mod)를 사용하는 것이다.

 

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

 

 

폴딩법(중첩법)

  폴딩 함수는 탐색키를 동일한 길이로 나누어, 이를 더하거나 비트별로 XOR같은 부울 연산을 하는 것이다.

 

  주로 탐색키가 해시 테이블의 크기보다 더 큰 정수일 경우에 사용한다. 예를들어, 탐색키는 32비트이고 해시 테이블의 인덱스는 16비트 정수인 경우, 탐색키의 앞이 16비트를 무시하고 뒤의 16비트를 해시 코드로 사용한다면, 앞의 16비트만 다르고 뒤의 16비트는 같은 탐색키의 경우 충돌이 발생할 것이다.

 

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

 

 

중간제곱함수

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

 

 

비트 추출 방법

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

 

 

숫자 분석 방법

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

 

 

탐색키가 문자열인 경우

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

 

 

물론 최종적인 해시 주소는 문자열을 정수로 변환한 값에 해시 함수를 적용하여 만들어진다. 위에서 HashFunction() 함수는 제산 함수를 사용하였다. 아래 표는 이 방법으로 문자열 탐색키의 해시 주소를 계산하고 있다.

 

탐색키	덧셈식 변환 과정(transform())	덧셈 합계	해시 주소
do	100 + 111	211	3
for	102 + 111 + 114	327	2
if	105 + 102	207	12
case	99 + 97 + 115 + 101	412	9
else	101 + 108 + 115 + 101	425	9
return	114 + 101 + 116 + 117 + 114 + 110	672	9
function	102 + 117 + 110 + 99 + 116 + 105 + 111 + 110	870	12

표 1. 문자열 탐색키에서 해시 주소를 얻는 과정

 

 

 

  2. 해싱의 오버플로우 처리 방법

 

  해싱에서 오버플로우를 잘 처리하는 것은 매우 중요하다. 이러한 오버플로우 처리방법은 아래의 두 가지로 나눌 수 있다.

 

  1) 선형 조사법(linear probing) : 충돌이 일어나면 해시 테이블의 다른 위치를 찾아 항목을 저장

  2) 체이닝(chaining) : 해시 테이블의 하나의 위치가 여러 개의 항목을 저장할 수 있도록 해시 테이블의 구조를 변경한다.

 

  2.1 선형 조사법

  선형 조사법(linear probing)은 해싱 함수로 구한 버켓에 빈 슬롯이 없으면 그 다음 버켓에서 빈 슬롯이 있는지를 찾는 방법이다. 이 때, 비어있는 공간을 찾는 것을 조사(probing)이라고 하는데, 여러 가지의 조사 방법이 가능하다.

 

  만약 ht[k]에서 충돌이 발생했다고 두면, 선형 조사법은 먼저 ht[k|1]이 비어 있는지를 살핀다. 비어있지 않다면 다음 위치인 ht[k+2]를 살펴보는데, 이런 식으로 비어있는 공간이 나올 때까지 계속하는 조사방법이다. 만약 테이블의 끝에 도달하면 다시 테이블의 처음으로 간다. 처음 충돌이 났던 곳으로 다시 돌아오면 테이블이 가득 찬 것이 된다. 따라서 조사되는 위치는 다음과 같은 순서이다.

 

h(k), h(k)+1, h(k)+2, h(k)+3, ...

 

크기가 7인 해시 테이블에서 해시 함수로 h(k)=k mode 7을 사용한다고 가정하고, 8, 1, 9, 6, 13 순으로 탐색키를 저장해보자. 아래에서 살펴본 바와 같이 선형 조사법은 오버 플로우가 발생하면 항목의 저장을 위하여 빈 버켓을 순차적으로 탐색해 나간다.

 

1단계 (8  저장) : h(8) = 8 mod 7 = 1(저장)

2단계 (1  저장) : h(1) = 1 mod 7 = 1(충돌)  →  (h(1)+1) mod 7 = 2(저장)

3단계 (9  저장) : h(8) = 8 mod 7 = 2(저장)  →  (h(9)+1) mod 7 = 3(저장)

4단계 (6  저장) : h(8) = 8 mod 7 = 6(저장)

5단계 (13 저장) : h(8) = 8 mod 7 = 6(충돌) →  (h(13)+1) mod 7 = 0(저장)

 

 

 

  문자열 탐색키의 경우도 방법은 동일하다. 표 1과 같이 각 문자열에 대한 해싱 주소가 만들어지면 하나씩 테이블에 삽입하는데, "case", "else", "return"이 모두 같은 해시 주소로 계산되었고, "if"와 "function"도 충돌이 발생했다.

 

선형 조사법에서는 "case"가 삽입된 상태에서 "else"가 들어오면 다음의 빈 버켓인 10 위치에 삽입한다. 다시 "return"이 같은 주소로 들어오면 다음으로 가능한 빈 버켓인 11 위치에 저장된다. 버켓 조사는 원형으로 회전함을 기억해야 한다. 테이블의 마지막에 도달하면 다시 처음으로 간다. 표 3.은 삽입 결과를 보여주는데, 한번 충돌이 발생한 위치에서 항목들이 집중되는 현상이 나타난다. 이를 군집화(clustering) 현상이라 한다.

 

 

선형 조사법의 구현: 문자열 탐색키를 사용하는 레코드

  이제 선형 조사법을 구현해보자. 먼저 해시 맴에 저장할 레코드를 정의해야 한다. 레코드는 key와 문자열 value를 갖도록 한다. HashMap 클래스는 별도로 작성.

 

 

선형 조사법은 간단하다는 장점이 있으나, 오버플로우가 자주 발생하면 군집화 현상에 따라 탐색의 효율이 크게 저하될 수 있다. 또 다른 문제가 있다. 항목을 삭제하는 함수를 생각해보자. 선형 조사법에서 항목이 삭제되면 탐색이 불가능해질 수 있다. 예를들면, 크기가 10인 해시 테이블과 h(K) = k mod 10인 해시 함수를 가정하자. 탐색키가 5, 15, 25 순서로 삽입되었다고 하면 모두 충돌이 발생하게 되고 해시 테이블의 내용은 아래 그림과 같을 것이다.

 

만약 이 상태에서 탐색키 15를 삭제하였다고 가정해보자. 탐색키 25를 탐색하면 중간이 비어있기 때문에 25가 있는 위치로 갈 수 없다. 이 문제를 어떻게 해결할 수 있을까?

  한 번도 사용하지 않은 버켓

  사용은 되었지만 현재는 비어있는 버켓

  현재 사용중인 버켓

이처럼 버켓을 몇 가지로 분류해야 한다.탐색 함수에서는 한 번도 사용이 안 된 버켓을 만나야만 탐색이 중단되도록 해야 한다.

 

 

  2.2 이차 조사법

  이차 조사법(quadratic probing)은 선형 조사법과 유사하지만, 충돌 발생 시 다음에 조사할 위치를 연산을 거쳐 결정한다.

 

 

  여기서 주의할 것은, 모든 위치를 조사하게 만드려면 여전히 테이블 크기는 소수어야 한다는 점이다. 이 방법은 선형 조사법의 문제점인 군집화 현상을 크게 완화할 수 있다. 2차 집중 문제를 일으킬 수는 있지만, 1차 집중처럼 심각하진 않다.

  2차 집중은 동일한 위치로 Mapping되는 여러 탐색키들이 같은 순서에 의하여 빈 버켓을 조사하기 때문.

 

 

 

  2.3 이중 해싱법

  이중 해싱법(doubld hashing) 또는 재해싱(rehashing)은 오버플로우가 발생함에 다라 항목을 저장할 다음 위치를 결정할 떄, 원래 해시 함수와 다른 별개의 해시 함수를 이용하는 방법이다. 이 방법은 항목들을 해시 테이블에 보다 균일하게 분포시킬 수 있으므로 효과적이라 할 수 있다.

 

  선형 조사법과 이차 조사법은 충돌이 발생 시에 해시 함수값에 어떤 값을 더해서 다음 위치를 얻는다. 선형 조사법에서는 더해지는 값이 1이고 이차 조사법에서는 j^2이 된다. 따라서 해시 함수값이 같으면 차후에 조사되는 위치도 같게 된다. 예를 들어, 크기가 10인 해시 테이블에서 재산 함수를 해싱 함수로 사용한다고 할 때, 15와 25는 이차 조사법에서 5, 6, 9, 14...와 같은 조사 순서를 생성한다.

 

  이중 해싱법에서는 탐색키를 참조하여 더해지는 값이 결정된다. 따라서 해시 함수값이 같더라도 탐색키가 다르면 서로 다른 조사 순서를 갖는다. 따라서 이중 해싱법은 이차집중을 피할 수 있다.

 

  두 번째 해시 함수는 조사 간격을 결정하게 된다. 일반적인 형태는 다음과 같다.

 

step = C-(k mod C) = 1 + k mod C

이런 형태의 함수는 [1~C] 사이의 값을 생성한다.

충돌이 발생했을 경우, 조사되는 위치는 다음과 같이 된다.

 

h(k), h(k)+step, h(k)+2*step, h(k)+3*step, ... mod M

 

C는 보통 테이블의 크기인 M보다 약간 작은 소수이다. 이중 해싱에서는 보통 집중 현상이 매우 드물다. 이유는 같은 버켓과 같은 탐색 순서를 가지는 요소들이 거의 없기 때문이다.

 

 

  2.4 체이닝

  체이닝은 하나의 버켓에 여러 개의 레코드를 저장할 수 있도록 하는 방법이다. 버켓은 여러가지 방법으로 구현할 수 있겠지만, 저장할 항목의 수를 예측할 수 없으므로 연결 리스트로 구현하여, 오버플로우를 해결하는 방법을 체이닝(chainning)이라고 한다.

  다음은 크기가 7인 해시 테이블에 h(k)=k mod 7의 해시 함수를 이용하여 8, 1, 9, 6, 13을 삽입할 때에의 체이닝에 의한 충돌 처리를 나타낸다.

 

1단계 (8  저장) : h(8) = 8 mod 7 = 1(저장)

2단계 (1  저장) : h(1) = 1 mod 7 = 1(충돌)  →  새로운 노드 생성 및 저장

3단계 (9  저장) : h(8) = 8 mod 7 = 2(저장)

4단계 (6  저장) : h(8) = 8 mod 7 = 1(저장)

5단계 (13 저장) : h(8) = 8 mod 7 = 1(저장) →  새로운 노드 생성 및 저장

 

 

 

 

 

 

체이닝을 구현해보자. 레코드는 앞에서 사용한 Record를 그대로 사용하고, 노드 클래스 Node는 5장과 6장에서 사용한 것과 대부분 비슷하다. 체이닝을 사용하는 해시 맵 클래스를 HashChainMap이라 하자. 연결 리스트에서 삽입은 맨 앞에서 이루어지도록 하였다.

 

 

  2.5 해싱의 성능

  해싱의 시간 복잡도는 O(1)이나, 이는 충돌이 전혀 일어나지 않는 상황에서만 가능하다. 따라서 실제 해싱의 탐색 연산은 O(1) 보다는 느려진다.

  해싱의 성능을 분석하기 위해 해시 테이블이 얼마나 채워져 있는지를 나타내는 적재 밀도(loading density) 또는 적재 비율(loading factor)을 다음과 같이 정의한다.

 

ａ = 저장된 항목의 개수 / 해싱 테이블의 버켓의 개수 = m / M

 

ａ가 0이면 해시 테이블은 비어있다. ａ의 최댓값은 충돌 해결 방법에 따라 달라지는데, 선형 조사법에서는 테이블이 가득차면 모든 버켓에 하나의 항목이 저장되므로 1이 된다. 체인법에서는 저장할 수 있는 항목의 수가 해시 테이블의 크기를 넘어설 수 있기 때문에 ａ는 최댓값을 가지지 않는다.

 

  기존 연구 결과들을 바탕으로 해싱을 정리해보자.

 먼저 선형 조사법은 적재 밀도를 0.5 이하로 유지해야 한다.

 이차 조사법과 이중 해싱법에서는 적재 밀도를 0.7 이하로 유지하는 것이 좋다고 한다. 

 체인법은 적재 밀도에 비례하는 성능을 보인다. 성능을 저하하지 않고 얼마든지 저장할 수 있는 요소의 개수를 늘릴 수 있다는 것이 장점이다. 링크를 위한 메모리 낭비 문제는 저장되는 자료의 크기에 따라 달라진다.

 

 

 

  2.6 해싱과 다른 탐색 방법의 비교

  해싱을 배열을 이용하는 이진탐색과 비교하면 해싱이 일반적으로 빠르다. 또한 삽입이 어려운 이진 탐색과는 달리 해싱은 삽입이 쉽다.

  해싱을 이진 탐색 트리와 비교하여 보면 이진 탐색 트리는 현재 값보다 다음으로 큰 값이나 다음으로 작은 값을 쉽게 찾을 수 있는 장점이 있다. 또한 이진 탐색 트리에서는 값의 크기순으로 순회하는 것이 쉽다. 이에 반하여 해싱은 그야말로 순서가 없다. 또한 해시 테이블에 초기에 얼마나 공간을 할당해야 되는지가 불명확하다. 또한 해싱은 최악의 시간 복잡도는 아주 나쁘다. 최악의 경우는 모든 값이 하나의 버킷으로 집중되는 것으로 이 경우 시간 복잡도는 O(n)이 될 것이다.

 

  아래 표에 여러 가지 탐색 방법의 시간 복잡도를 정리하였다.

 

탐색 방법		탐색	삽입	삭제
순차 탐색		O(n)	O(1)	O(n)
이진 탐색		O(log₂n)	O(n)	O(n)
이진 탐색 트리	균형 트리	O(log₂n)	O(log₂n)	O(log₂n)
	경사 트리	O(n)	O(n)	O(n)
해싱	최선의 경우	O(1)	O(1)	O(1)
	최악의 경우	O(n)	O(n)	O(n)

 

 

 

해싱(hashing) : 네이버 블로그 (naver.com)

해싱(Hashing) 이란? (velog.io)

해싱 (naver.com)