12강 제 6장 탐색 알고리즘 ( 해 싱 )

6.5 해 싱 ( hashing )

 

6.5.1. 개  념

> 탐색 키값을 기반으로 데이터의 저장 위치를 직접 계산

→ 상수 시간 내에 데이터를 탐색,삽입,삭제 가능

 

해싱이 적합한 형태의 응용 문제는?

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

동일한 키값을 가진 여러 개의 데이터가 존재하는 응용 

범위에 속하는 키값을 가진 모든 데이터를 탐색하는 문제

최대/최소의 키값을 가진 데이터를 찾는 문제

키값의 순서대로 데이터를 방문하는 형태의 문제

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

위의 것들은 적합하지 않음

 

특정 키값을 갖는 데이터를 찾는 문제

 

6.5.2 해시 함수

해시 함수 h는 키값을 해시 테이블 주소로 변환하는 함수

 

해시 함수

> 해시 함수  h : U -> { 0, 1, ......   , M -1 }

  - 키값을 해시 테이블 주소로 변환하는 함수

  - 종류 : 제산 잔여법, 비닝, 중간 제곱법, 문자열을 위한 함수 등

 

> 바람 직한 해시 함수는 

  - 계산이 용이해야 한다.

  - 각 키값을 테이블의 각 슬롯에 균등하게 사상시킬 수 있어야 한다.

 

 

해시 함수 _ 제산 잔여법

> h(K)=KmodM(K:키값,M:해시 테이블의 크기)

  - h(123)=123mod11=2 

> M의 선택에 주의 

  -  M=2r이면 h(K)는 하위 r비트의 값이 됨 

     -  키값의 전체 비트를 주소 계산에 활용하지 못함

 

h (int x ) {             // 0 ~ 15 ( 0000 ~ 1111 )

return x % 16;        // 39 = 100111 >> 7

}                          // 3751 = 111010100111 >>> 7 

 M=2r이면 h(K)는 하위 r비트의 값이 됨 • 키값의 전체 비트를 주소 계산에 활용하지 못함

 

해시 함수 _ 비닝

 

> 키의 집합 U를 단순히 M등분하여 각 등분을 각 슬롯으로 해시

 

 

 

 

 

 

 

해시 함수_중간 제곱법 

> h ( K ) = ( K^2 / 2^m) mod2^r

h ( int x )

{                                    // 키값:4자리 십진수

   return(x*x/1000)%100;     // 해시 테이블 크기: 100 

}

1.주어진 키값을 제곱한다.

( 4 5 6 7 )^2   >>>     2 0 8 5 7 4 8 9

2.제곱된 결과를 키값의 자릿수로 나눈 후,  M에 해당하는 하위 2자리 십진수를 취한다.

  2 0 8 5 7 4 8 9 

모든/대부분의 비트가 결과 생성에 기여 

→ 상위/하위 자리의 분포에 의해 지배적인 영향을 받지 않음

 

 

해시 함수_문자열을 위한 해시 함수 (1)

 

h1( ch x[] , int M)

{ // x : 입력 문자열, M : 테이블 크기           // 키값 “aaaabbbb”의 주소는?

   int xlength = length(x);

   for( sum=0 , i=0; i < xlength; i++ )         // a:97,b:98→ 97×4+98×4=780

      sum += x [ i ] ;                                // 780%100=80

   return sum % M;

}

- M«sum일 때 유용 

- 짧은 문자열에 대해서는 비효과적

- 문자열에서 문자의 출현 순서에 무관

 

해시 함수_문자열을 위한 해시 함수 (2) 

 

6.5.3 충돌 해결 방법

 

> 충돌 ? 

  -  서로 다른 키값 x , y 에 대하여 h( x ) = h ( y )인 경우

 

> 충돌 해결 방법

  - 개방 해싱 (연쇄법) 

    - 충돌된 데이터를 테이블 밖의 별도의 장소에 저장∙관리  
 

   -  폐쇄 해싱 (개방 주소법)

    - 테이블 내의 다른 슬롯에 충돌된 데이터를 저장∙관리

    - 버킷 해싱, 선형 탐사, 이차 탐사, 이중 해싱

 

 

충돌 해결 방법 _ 개방 해싱

테이블의 각 슬롯을 연결 리스트의 헤더로 사용

 

 

** 해시 테이블과 연결 리스트가 

주기억장치 내에서 유지 될때 적합한 방법

 

 

 

충돌 해결 방법_버킷 해싱 

버킷 (bucket ) 해싱은 해시 테이블 슬롯을 버킷으로

묶어 버킷 단위로 해싱 하는 것이다.

 

해시 테이블 M 개의 슬롯을 B + ! 개의 버킷으로 나누는데, 마지막 버킷이 F 개의 슬롯을 가지고 나머지 B개의 버킷은 각각 ( M - F ) / B 개의 슬롯으로 구성

 

마지막 버킷을 오버플로 버킷이라 부른다.

 

 

 

 

 

 

충돌 해결 방법_선형 탐사

 

> 탐사 순서probe sequence 

 -  어떤 키 K를 위해서 탐사되는 슬롯의 순서열

   -  p( K , i  )

→ p( k , 0) = h( K ) , p( K , 1 ) , p( K , 2) , p( K ,3 ) ,… 

 - 탐사 순서의 계산 방법에 따라 성능의 차이가 발생 

   -  선형 탐사,이차 탐사,이중 해싱

 

> 선형 탐사linearprobing    

  -  p( K , i ) = ( h( K ) + i  ) modM, ( i = 0 , 1 , … , M-1 ) 

    - 빈 슬롯을 찾을 때까지 테이블의 바로 다음 슬롯으로 순차적으로 이동 

  - 가장 간단한 방법,하지만 최악의 방법

 

( 예 )

-모든 슬롯이 새로운 데이터를 삽입할 후보가 됨

-“1차 클러스터링”문제 → 긴 탐사 순서를 만들어 평균 탐색 시간의 증가를 초래

  - 데이터들이 연속된 위치를 점유하여 클러스터를 형성하고,이것이 점점 커지는 현상 

 

 

충돌 해결 방법_이차 탐사

> 탐사 순서의 단계에 대한 이차식을 이용

  -  p(K,i)=( h(K)+ c1 × i^2 + c2 × i + c3 )modM

    - 충돌이 발생하는 횟수의 제곱 형태로 탐사 순서를 결정

 

> 서로 다른 홈 위치를 갖는 두 키는 서로 다른 탐사 순서를 가짐 

- p(K,i)=(h(K)+i2)mod10
- h(k1)=2 → 2,3,6,1,…

- h(k2)=5  → 5,6,8,4,…

 

> 모든 슬롯이 탐사 순서에 사용되지 않음 

-  p(K,i)=(h(K)+i2)mod10

  -  p(K,0)=2라면 슬롯 1,2,3,6,7,8만 탐사 가능

-  탐사 함수와 테이블 크기가 적절히 조합되면 많은 슬롯의 방문이 가능 

 

> 2차 클러스터링 문제 

 - 해시 함수가 특정 홈 위치에 대한 클러스터를 만드는 현상 

   - 서로 다른 두 키의 홈 위치가 동일하면 전체 탐사 순서가 동일

 

 

충돌 해결 방법_이중 해싱 

> 탐사 순서를 원래의 키값을 이용하여 계산

  - 1차/2차 클러스터링 문제 해결

> 서로 다른 두 키의 홈 위치가 동일해도 서로 다른 탐사 순서를 가짐

> 좋은 이중 해싱을 구현하려면 

 -  탐사 순서의 모든 상수가 테이블 크기 M과 서로소가 되어야 함 

    - M을 소수로 선택하고,h2가 1≤h2(K)≤M-1의 값을 반환

    -  M=2m으로 정하고, h2가 1과 2m 사이의 홀수를 반환

 

 

 

삭제 연산

> 두 가지 고려 사항

- 데이터의 삭제가 차후의 탐색을 방해하지 않아야 한다. 

    - 단순히 빈 슬롯을 두면 탐색이 해당 슬롯에서 종료되므로 그 이후의 레코드가 고립된다.

- 삭제로 인해 해시 테이블의 위치에서 사용할 수 없는 곳을 만들지 않아야 한다.

 

> 비석 tombstone

- 삭제된 데이터의 위치에 ‘비석’이라는 특별한 표시를 하는 방법

   - 탐색 → 비석을 무시하고 탐색을 계속 진행

   - 삽입 → 비석이 표시된 위치를 빈 위치로 간주하여 새 데이터를 삽입

- 비석의 개수가 증가할수록 평균 탐색 거리가 증가하는 문제