해시(Hash)

해시라는 것은 DB를 공부할 때 많이 들었다. 테이블 구조에서 성능을 끌어올 때 해시구조로 변형시키는 튜닝방법이 있었다. 

또 암호화 할 때 해시라는 것을 많이 들었는데, 정확히 무엇이다 규정을 내릴 수 없는 상태였다. 해시라는 것을 정리해보겠다.

해시(Hash)

-주어진 키를 이용해서 실제 레코드의 주소를 직접적으로 계산해내는 것을 해시라고 한다. 

-임의의 데이터를 고정 길이의 데이터로 변화한 값을 해시값, 이 과정을 해시라고 한다. 

(쫌 어렵다)

해시에 대한 정의도 중요하지만 어디에 해시가 사용하는지를 알아야 한다.

해시의 궁극적인 목표

데이터 개수 N개와 무관하게 단번에 찾겠다는 것, 탐색효율이 logN도 아니라 O(1)을 지향한다!

어떻게?

키를 입력하면 해시함수를 통해서 해시테이블의 인덱스로 바로 접근한다!

해시함수(Hash Function)란?

해시함수(Hash Function)란 탐색키를 입력으로 받아 해시주소(Hash Address)를 생성하고 

이 해시 주소가 배열로 구현된 해시 테이블(Hash Table)의 인덱스가 된다.

ex) 영어 사전에서는 단어(탐색키)를 이용하여 해싱 함수를 통과하면 적절한 정수 i가 도출되는데 

이를 통해 ht[i]에 접근하면 단어에 대한 내용을 볼 수 있게 되는 것이다.

해시테이블(Hash Table)의 구조?

-해시테이블은 M개의 버켓(bucket)과 S개의 슬롯(Slot)으로 구성된다. 

-하나의 버켓은 여러 개의 슬롯을 가질 수 있다.

해시(Hash)의 방법?

1) 제산법

나머지 연산자(%)를 사용하여 테이블 주소를 계산하는 방법

레코드 키 값을 수치 자료로 간주하여 어떤 양의 정수(대개 해시 테이블의 크기)로 나눈 나머지를 홈 주소로 결정하는 간단한 방법

ex) 버킷 주소 = 키 값 % 해쉬 테이블의 크기

12 = 512 % 100

2) 제곱법

- 제곱법은 레코드 키 값을 제곱한 후에 결과 값의 중간 부분에 있는 몇 비트를 선택하여 해시 테이블의 홈 주소로 사용

- 제곱된 결과의 중간 비트는 대개 레코드의 모든 문자에 의존하므로, 레코드를 구성하는 몇 개의 문자가 같은 지라도 서로 다른 레코드 키는 다른 홈 주소를 갖게 될 확률이 높다

- 홈 주소를 얻기 위해 사용되는 비트 수는 테이블의 크기에 따라 달라지는데, 중간 부분의 자릿수를 n이라 하면 각 레코드 값들이 가지는 범위인 해시 테이블의 크기는 2n 이 된다.

- 키 값 제곱 => 해시 테이블 크기에 따라 주소 값 산출

ex) 레코드 키 값이 K = 512이고, 해시테이블의 크기가 100일 때 제곱법에 의한 레코드 주소는?

512제곱 = 262144

====> 중간 2자리 "21"최종 주소값이 됨

3) 숫자 분석법

- 레코드 키를 구성하는 수들이 모든 키들 내에서 각 자리별로 어떤 분포인지를 조사하여 비교적 고른 분포를 나타내는 자릿수를 필요한 만큼 선택하여, 레코드의 홈 주소로 사용하는 방법

ex) 해시 테이블의 크기 = 1000, 홈 주소 : 0 ~ 999까지(3자리 필요) 레코드 키 값이 다음의 (a)와 같을 때 숫자 분석법을 이용하여 각 키들에 대한 홈 주소를 결정하시오.

012 - 452 - 0236   =>     426

012 - 153 - 0530   =>     150

015 - 342 - 0935   =>     395

012 - 752 - 1032   =>     702

012 - 852 - 0470   =>     840

012 - 543 - 0231   =>     512

     (레코드 키값)         (각 키의 홈 주소)

(1) (a)에서 왼쪽 3자리는 거의 같으므로 제거

(2) 왼쪽 5열, 6열, 7열, 9열 역시 동일 숫자가 많이 분포하였으므로 무시

(3) 비교적 고른 숫자 분포를 가진 4열, 8열, 10열을 선택하여 주소로  사용

4) 폴딩법

- 폴딩법은 레코드의 키를 마지막 부분을 제외한 모든 부분의 길이가 동일하게 여러 부분으로 나누고, 이들 부분을 모두 더 하거나 배타적 논리합(XOR)을 취하여, 해시 테이블의 홈 주소로 이용하는 방법으로 두 가지 방법이 사용 된다.

(1) 이동 폴딩(shift Folding)

(2) 경계 폴딩(Boundary Folding)

3	0	1	2	3	0	1	2	3	2	1	3	3	0
P1			P2			P3			P4			P5

이동폴딩 => 

P1 + P2 + P3 + P4 + P5 

= 301 + 230 + 123 + 213 + 30 = 897

897 = 홈주소

경계폴딩 => 

P1 + P2(역) + P3 + P4(역) + P5

= 301 + 032 + 123 + 312 + 30 = 798

798 = 홈주소

5) 기수변환법

- 기수 변환법은 어떤 진법으로 표현된 주어진 레코드 키를 다른 진법으로 간주하고 키를 변환하여 홈 주소를 얻는 방법으로, 어떤 키 값이 16진법으로 표현되어 있다면 이를 10진법으로 표현된 것으로 간주하고 키 값을 변환하여 해당 레코드의 홈 주소를 구한다.

- 해시 테이블의 크기가 10의 멱승으로 표현되어 변환된 해당 레코드의 주소 값이 테이블의 크기를 초과할 때는 주소 값의 최하위 자리부터 해시 테이블의 크기가 허용하는 멱승수만큼 취하여 해당 레코드의 홈 주소로 사용한다.

ex) 해시 테이블의 크기 = 10000()

- 십진수로 입력된 키 값(B2538)10을 16진수로 간주하여 그 값을 다시 10진수로 계산하는 기수 변환법을 이용하여 홈 주소를 구하시오. 

(풀이) (1 * 165) + (3 * 164) + (2 * 163) + (5 * 163) + (4 * 161) + (8 * 160)

= 1048576 + 196608 + 8192 + 1280 + 64 + 8

= (1254728)10

홈 주소 = 4728

- 레코드의 주소값 (1254728)10에서 해시 테이블이 허용하는 하위 4자리를 선택한다.

6) 무작위방법

- 난수 발생 프로그램을 이용하여 난수(random number)를 발생시켜 각 레코드 키의 홈 주소를 결정하는 방법으로, 보통 난수는 1보다 작은 양의 실수를 산출하므로,

- 해시 테이블의 크기인 n을 산출된 난수에 곱하여 0~(n-1)까지의 범위 값으로 변환하여 사용하며, 만일 충돌이 발생하게 되면 그 다음 난수를 레코드의 홈 주소로 사용한다.

해시충돌(Hash Collision)이란?

- 서로 다른 두 개의 탐색키와 k1과 k2에 대하여

- h(k1) = h(k2)인 경우에는 충돌이 일어난다.

- 이러한 충돌이 버켓이 할당된 슬롯 수보다 많이 발생하게 되면 

버켓에 더 이상 항목을 저장할 수 없게 되는 오버플로우(Overflow)가 발생한다.

해시충돌을 해결하는 방법?

- 선형 검색법

- 2차 검색법

- 무작위 검색법

- 체인 이용법

* 해시 함수에 의해 같은 기억공간에 할당되어 충돌이 발생한 레코드들을 연결 리스트(Linked List)로 연결하는 방법으로

해시 테이블 자체는 포인터의 배열로 만들고, 같은 버켓에 할당되는 레코드들을 체인으로 만들어 연결한다.

=> 해시 연쇄법은 연결 리스트를 사용하므로 해시 테이블에서의 삽입이나 삭제 연산이 용이하며, 충돌의 횟수를 감소시키지는 못하지만 다른 충돌 해결 방법에 의해 해시 테이블을 검색 할 때 발생하는 소요시간을 감소 시킬 수 있다.

* 장점 

=> 충돌이 발생한 명칭들만 연결 리스트에서 검색해 주면 되므로 속도가 빠르다.

=> 삽입 가능한 명칭의 수가 해시 테이블 크기에 영향을 받지 않는다.

* 단점

=> 구조가 복잡하고 기억 장소 소모량이 많다.