08-4 해싱

※ 해싱(Hashing)

 - 해싱은 키값을 비교하여 검색하는 것이 아니라 산술적 연산을 이용하여 키가 있는 위치를 계산하여 바로 찾아가는 계산 방법이다.

 - 키값을 원소의 위치로 변환하는 함수를 해싱 함수(Hashing Function)라 한다.

 - 해싱 함수에 의해 계산된 주소의 위치에 항목을 저장한 표를 해시 테이블(Hash Table) 이라 한다.

 - 즉 해싱은 어떤 키값을 해시함수를 통해 그 키값이 저장될 해시 테이블의 위치를 구한다. 그리고 그 위치에 저장하거나 검색한다.

 - 해시 테이블을 버킷과 슬롯으로 구성한다.

 - 해싱 함수에 의해서 계산된 주소는 버킷 주소가 된다.

 - 버킷에 여러개의 슬롯을 만들어 값이 비슷한 여러개의 키값을 저장할 수 있다.

※ 해싱 구조 용어

1. 동거자 : 모든 키값이 고르게 사용되기 보다 사용되지 않는 키값도 있고 많이 사용되는 비슷한 키값도 있기 때문에 모든 키값의 수만큼 버킷을 만들면 메모리 낭비가 일어날 수 있다. 그렇기 때문에 해시테이블에선 비슷한 키값의 경우 버킷의 수를 줄이고 버킷 안에 여러 개의 슬롯을 두어 해싱 함수로 만든 주소가 같은 키값들은 같은 버킷에 저장한다. 이때 다른 키값을 가지지만 같은 버킷에 저장된 키값들을 동거자라고 한다.

2. 충돌 : 다른 키값이 버킷의 주소가 같을 때 충돌이라 한다. 충돌 상황에는 같은 버킷이라도 다른 슬롯에 저장하면 된다. 하지만 슬롯이 가득 차있다면 오버플로우가 발생한다.

3. 키값 밀도 : 사용 가능한 전체 키값들 중에서 현재 해시 테이블에 저장되어 실제 사용되고 있는 키값의 개수 정도  

       키값 밀도 = 사용되고 있는 키값의 개수 / 사용가능한 키값의 개수

4. 적재 밀도 : 해시 테이블에 저장 가능한 키값의 개수 중에서 현재 해시 테이블에 저장되어 실제 사용되고 있는 키값의 개수 정도

적재 밀도 = 실제 사용중인 키값의 개수/ 해시 테이블에 저장 가능한 전체 키값의 개수 

  = 실제 사용중인 키값의 개수 / 버킷 개수 X 슬롯 개수

※ 해싱 함수(Hashing Function)

 - 어떤 해싱함수(키값의 위치를 계산하는 함수)를 사용하느냐에 따라 해싱의 검색 효율이 달라진다. 

 - 좋은 해싱함수의 조건

1. 계산이 쉬워야 한다. 키값을 비교하는 검색보다 연산 수행시간이 빨라야 해싱 검색을 사용하는 의미가 있다.
2. 충돌이 적어야 한다. 충돌이 많이 발생한다 = 버킷에 할당받는 키값이 많다. 즉 비어있는 버킷이 많은데 어떤 버킷은 오버 플로우가 발생할 수 있는 상태가 되므로 좋은 해싱 함수가 아니다.
3. 해시 테이블에 고르게 분포할 수 있도록 주소를 만들어야 한다.   

※ 해싱 함수의 종류

 - 중간 제곱 함수 : 키값을 제곱한 결과값에서 중간에 있는 적당한 비트를 주소로 사용하는 방법.

   ex) 키값이 이진수로 00110101 10100111일때 

                                  00110101 10100111

     X                           00110101 10100111         

   -------------------------------------------------------------

     0000101100111110100100101111001

   

키값에 대한 이진수를 제곱한 결과 중 가운데 8비트는 11101001이 된다. 11101001의 10진수 값 233이 해시 테이블의 버킷 주소가 된다.

제곱 결과값에서 주소로 사용하는 비트의 수는 버킷의 수에따라 결정이 된다. 만약 버킷의 수가 256개이면 주소는 0~255를 쓴다. 256개의 값을 만들기 위한 최소의 비트 수는 2^8 = 256 이므로 제곱 결과값에서 8비트를 사용한다.

즉 버킷의 개수에 따라서 중간에 있는 적당한 비트의 수를 조절하여 사용한다.

 - 제산 함수 : 나머지 연산자 mod를 사용하는 방법. 키값을 해시 테이블의 크기로 나눈 나머지를 해시 주소로 사용 

h(k) = key mod HashSize 

HashSize로 나눈 나머지 값의 범위는 0~(HashSize-1) 이므로 해시 테이블의 인덱스로 사용할 수 있다. 충돌이 발생하지 않고 고르게 분포하도록 생성되어야 하므로 키값을 나누는 해시 테이블의 크기는 적당한 크기의 소수를 사용한다. 

 - 승산 함수 : 곱하기연산을 사용하는 방법. 키값에 정해진 실수를 곱한 결과에서 소수점 이하 부분만을 테이블 크기와 

곱하여 그 정수 값을 주소로 사용

 - 접지 함수 : 키의 비트 수가 해시 테이블의 인덱스의 비트 수보다 큰 경우 주로 사용하는 방법. 키값을 해시 테이블 

 인덱스의 비트수와 같은 크기로 분할한 후 분할된 부분을 더하는데, 이때 더하는 방법에 따리 이동 접지 함수와 경계 접지 함수로 나뉜다.

(1)이동 접지 함수 : 각 분할 부분을 이동시켜 오른쪽 끝자리가 일치하도록 맞춘 뒤에 더하는 방법.

 ex) 해시 테이블의 인덱스가 3자리이고, 키값이 12312312312인 경우 123/123/123/12로 나눈다. 그런다음

오른쪽 끝자리를 맞추어 더하면 123+123+123+12 = 381이 된다. 이 값이 인덱스 테이블의 주소가 된다.

                  

(2)경계 접지 함수 : 분할된 각 경계를 기준으로 접어 서로 마주보게 배치한 후 더하는 방법

ex) 해시 테이블의 인덱스가 3자리이고, 키값이 12312312312인 경우 123/321/123/21로 나눈다. 그런다음

오른쪽 끝자리를 맞추어 더하면 123+321+123+21 = 588이 된다. 이 값이 인덱스 테이블의 주소가 된다.

 - 숫자 분석 함수 : 키값을 이루고 있는 각 자리수의 분포를 분석하여 해시 주소로 사용. 각 키값을 적절히 선택한 진수로 

  변환한 후에 각 자리수를 분석하여 분포가 가장 고르게 분포된 자릿수부터 해시 테이블 주소의 자릿수     만큼 차례로 뽑아서 만든 수를 역순으로 바꾸어 주소로 사용

  ex) 학번 2008 04 1 03 이 있다고 하자 2008은 입학년도, 04는 학과, 1과 2는 주간과 야간, 마지막 

  두자리 는 학생 번호를나타낸다 할 때, 가장 고르게 분포된 번호는 학생번호와 주간 야간 구분 번호 

  이므로 이 두 번호룰 추출하여 합쳐서 3자리수의 해시 테이블 주소를 만든다.

 - 진법 변환 함수 : 키값이 10진수가 아닌 다른 진수일 때, 10 진수로 변환하고 해시 테이블 주소로 필요한 자릿수만큼만 

  하위 자리수를 사용하는 방법.

 - 비트 추출 함수 : 해시 테이블의 크기가 2^k일 때 키값을 이진 비트로 놓고 임의의 위치에 있는 비트들을 추출하여 

  주소로 사용하는 방법 충돌이 발생할 가능성이 많으므로 테이블의 일부에 주소가 편중되지 않도록 

  키값들의 비트들을 미리 분석하여 사용.

※ 오버플로우 처리 방법

 - 해시 테이블과 해싱 함수를 잘 선택하여 오버플로우가 발생하지 않도록 해야 하고, 발생할 경우 효율적으로 처리하여 

   해결해야 한다.

   오버플로우를 처리하는 방법은 충돌이 일어난 키값을 비어있는 버킷을 찾아 저장하는 선형 개방 주소법과 여러 개의 

   항목을 저장할 수 있도록 해시 테이블의 구조를 변경하는 체이닝 방법이 있다.

1.   선형 개방 주소법 

- 해당 버킷에 빈 슬롯이 없어서 오버플로우가 발생하면 그 다음 버킷에 빈 술롯이 있는지 조사한다. 

- 빈 슬롯이 있으면 저장하고 없으면 다음 버킷을 조사한다. 이런 과정을 반복하여 빈 슬롯에 순차적으로 찾아서 

  오버플로우를 해결한다.

2.   체이닝

 - 해시 테이블의 구조를 변경하여 각 버킷에 하나 이상의 키값을 저장할 수 있도록 하는 방법. 원활한 삽입과 

   삭제를 위해 연결 리스트를 사용한다. 각 버킷에 대한 헤드노드를 1차원 배열로 만들고 슬롯을 연결한다.