본문 바로가기

자료구조 & 알고리즘

[박혜웅] 최소 완전 해쉬 함수 (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()함수를 완성한다.

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

 

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

    • Sager가 Cichelli의 방법을 정형화

    • 완전 해쉬함수 생성 방법

      • 3개의 보조함수
      •  

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