[Algorithm] Perfect Hash Function

Perfect Hash Function은 빠른 해시테이블 접근을 위한 해시의 한 기법이다.
아주 제한적인 상황에서만 사용이 가능하다. 이 기법을 사용하려면 input으로 들어올 수 있는 hash key를 전부 알고 있어야 한다.

일반적인 해시테이블 구조

일반적으로 해시테이블 구현체들은 다음과 같이 구현되어있다.

키값을 해시하면 무작위의 해시값이 생성된다. 하지만 대다수 구현체에서 해시는 반드시 충돌이 발생할 수 있다.
foo와 bar라는 다른 키값이 동일한 해시값을 만들 수 있기 때문이다.

그래서 보통 내부적으로 배열이나 linked list를 사용해서 해시 키마다 "bucket"이란걸 둔다. 해시 충돌이 발생하면 버킷에 쌓아놓는 것이다.

이런 구조는 일반적인 웹서비스 비즈니스 로직 수준에서는 충분한 성능을 보인다.
하지만 극한의 최적화가 필요한 상황에서는 성능에 불리한 점이 많은 것도 사실이다. 단일 배열이 아니다보니 캐시라인 최적화도 잘 안되고, 해시 함수 자체의 부하도 적지는 않다.

Perfect Hash Function - Minimal Perfect Hash Function

Perject Hash Function에는 꽤 다양한 변형 알고리즘이 있다. 개중에서도 Minimal Perfect Hash Function는 매우 간단한 원리로 구조를 단순화한다.
그냥 키를 1:1로 인덱스 값으로 매핑해놓은 다음에, 배열을 고정으로 생성하는 것이다.

원리 자체는 그렇게 어려울 것이 없다.

이렇게 해시 함수를 먼저 만든다.
해시함수는 미리 키 테이블을 생성해놓고, 그것과 일치하는 값이 들어오면 해시값. 그러니까 여기서는 배열 인덱스 값을 반환한다.

이후에는 키 길이만큼의 배열을 만들고 해시값을 기반으로 값을 할당하거나 수정할 수 있게 된다.

Minimal Perfect Hash Function - 정렬 기반 최적화 (MOS)

여기서 조금 고민해야할 부분은 perpect_hash 자체의 성능이다. 저 키가 많다면 많을 수록 인덱스를 구하는데 시간이 좀 걸릴 것이다. 해싱을 할때마다 O(N)의 부하가 걸린다면, 해시테이블이라는 구조를 사용하는 의미가 전혀 없다.

여기서 가장 간단한 방법은 key 목록을 정렬해놓고 binary search를 하는 것이다.
최소 setup에만 O(N log N) 연산이 발생하고, 이후에는 해시 함수의 성능이 O(log N) 정도가 나올 것이다.

이런 방법론을 MOS(Mapping, Ordering, Searching) 방법론이라고 부르는 것 같다.

Minimal Perfect Hash Function - 다른 해시 생성법

보통은 1:1로 매칭을 시켜서 인덱스를 바로 만드는 것이 일반적인 방법이지만, 복잡한 해시 생성법들도 있다.

1. Cichelli의 알고리즘
   문자열의 길이, 첫 문자와 끝 문자를 조합해서 해시값을 생성하는 방법이다.

완전히 엄격한 방법은 아니라서, 충돌이 발생할 경우에는 재귀적으로 극복하는 것을 지향한 것 같다. 근데 이걸 완전하다고 할 수 있나? 불완전한 것 같다.

참조
https://en.wikipedia.org/wiki/Perfect_hash_function
https://searchall.tistory.com/74
https://github.com/rust-phf/rust-phf
https://scholarsmine.mst.edu/cgi/viewcontent.cgi?article=1000&context=comsci_techreports
https://stackoverflow.com/questions/8233965/perfect-hash-functions