[박혜웅] 최소 완전 해쉬 함수 (Minimal Perfect Hash Function)

• minimal perfect hash function(MPHF, 최소 완전 해쉬 함수)

• • m개의 키를 m개의 버킷에 충돌없이 해싱하는 완전 해쉬함수

    • 즉, 키와 버킷이 일대일 대응이며, 100% 적재율을 가진 해쉬 함수

  • perfect hash function(완전 해쉬 함수)

    • 모든 키들이 구별되는 다른 위치(버킷)로 대응되는 함수
    • 해쉬함수 정의 전에 키의 집합을 알고 있어야 함.
    • 키값 자체를 버킷번호로 사용하면, 완전해싱 함수는 구현이 가능하다. 단, 저장공간이 매우 커서 매우 비효율적이다.
    • 완전 해쉬 함수를 만들 수 있다면, 폐쇄 주소법보다 개방 주소법이 더 좋다.

 

• MOS(Mapping, Ordering, Searching)방식의 완전 해쉬 함수

  • Cichelli, Cerone 이 제안

  • 완전 해쉬함수 생성 방법

    1. mapping: 키를 새로운 유니버스(모집단)로 변환

       • 모집단: 통계적인 관찰의 대상이 되는 집단 전체
    2. ordering: 키를 순서화(정렬)
    3. searching: 각 단계의 키에 해쉬값을 할당, 수용불가능한 단계가 발생하면, 이전 단계로 역추적(backtracking)하여 새로운 해쉬값 찾음.

 

• Cichelli가 제안한 완전 해쉬 함수 (키가 문자열일 때)

• • h(s) = ( s.length() + g( first(s) ) + g( last(s) ) ) % m

    • s.length() = 문자열의 길이
    • first(s) = s.charAt(0) = 문자열의 첫 문자
    • last(s) = s.charAt(s.length()-1) = 문자열의 끝 문자

  • 완전 해쉬함수 생성 방법

  • 1. 키 집합의 모든 키에 대하여 첫 문자와 끝 문자를 뽑아 중복없이 나열하고, 각 문자에 대한 빈도수를 계산하여 문자 빈도수 테이블을 만든다.

    2. 각 키에 대하여 첫 문자와, 마지막 문자에 대한 빈도수의 합을 계산한다.

    3. 키 빈도수합 테이블을 빈도수합 내림차순으로 정렬한다.

    4. 정렬된 키 빈도수합 테이블에서 해쉬값 집합의 원소가 중복되지 않도록, g(문자) 함수를 정의한다. 중복될 경우에는 백트래킹(backtracking)을 이용하여, g(문자) 함수를 재정의 한다. 해쉬값은 아래 공식을 이용하여 구한다.

       • h(s) = ( s.length() + g( first(s) ) + g( last(s) ) ) % m

    5. 4를 반복하여 해쉬테이블과 g()함수를 완성한다.

  • 완전 해쉬함수 생성 방법의 예

    • [박혜웅] 완전해싱 예제.pdf

 

• Sager가 제안한 완전 해쉬 함수 알고리즘 (키가 문자열일 때)

  • Sager가 Cichelli의 방법을 정형화

  • 완전 해쉬함수 생성 방법

    • 3개의 보조함수

    • 
       

    • r<= m/2
    • g()는 탐색중에 선택됨