Perfect Hash Funkcje

Question

Niedawno otrzymałem zadanie domowe, które zapytało, czy z podanej listy kluczy można utworzyć funkcję skrótu, która nie powoduje żadnych kolizji. Wykonując pewne badania, dowiedziałem się, że biorąc pod uwagę wcześniej przygotowaną listę kluczy, możliwe są doskonałe funkcje skrótu.

Jednak nie jestem do końca pewien, co powiedzieć dalej. Czy ktoś mógłby mi dać radę na temat tego, jak powstają perfekcyjne funkcje mieszające, lub co dokładnie daje predefiniowana lista dla twórcy funkcji mieszającej, która pozwala na doskonałą funkcję?

Dzięki za pomoc.

Answer 1

Jedynym sposobem na uniknięcie kolizji jest posiadanie relacji 1 do 1 między kluczem a wartością skrótu. Zakres wartości skrótu musi być co najmniej tak duży, jak liczba kluczy, a funkcja odwzorowania musi przekształcić każdy klucz na unikalną wartość. Znacznie więcej informacji tutaj: http://en.wikipedia.org/wiki/Perfect_hash