Minimalna funkcja skrótu mieszającego

Question

Mam wiele liczb całkowitych w zakresie [0; 2^63-1]. Istnieje jednak tylko 10^8 liczb całkowitych. Istnieje bez duplikatów. Pełna lista jest znana podczas kompilacji, ale jest to tylko unikatowe liczby losowe. Te numery nigdy nie zmieniają się.
Aby zapisać jedną liczbę całkowitą jawnie, wymagane są 8 bajtów i są skojarzone 1-bajtowe wartości, więc jawne przechowywanie wymaga około 860 MB.
Więc chcę znaleźć minimalną idealną funkcję skrótu do odwzorowania każdej z 10^8 liczb całkowitych z [0; 2^63-1] na [0; 10^8-1]. Powinienem znaleźć tę funkcję tylko raz, dane nigdy się nie zmieniają, a funkcja może być skomplikowana. Ale powinno być minimalne, idealne, a obliczanie powinno być szybkie. Jak mogę to zrobić lepiej? Być może jest możliwe znalezienie i użycie podciągów, jeśli tak się dzieje?
Dzięki.

Answer 1

Niech komputer do pracy dla Ciebie:

http://www.gnu.org/software/gperf/

Cytat:. „GNU gperf jest idealny generator funkcja mieszania dla danej listy ciągów, produkuje funkcji skrótu i ​​tabeli mieszania, w postaci kodu C lub C++, w celu sprawdzenia wartości zależnej od łańcucha wejściowego. Funkcja skrótu jest idealna, co oznacza, że ​​tabela mieszająca nie ma kolizji, a wyszukiwanie tablicy mieszającej wymaga tylko pojedynczego porównania ciągów znaków. "

Answer 2

Pracuję nad an algorithm and Java implementation that needs less than 1.6 bits per key.

Wcześniej zaimplementowałem a minimal perfect hash function tool in Java, która potrzebuje mniej niż 2,0 bity na klucz.

Inne algorytmy są zaimplementowane w CMPH. Na przykład CHD potrzebuje domyślnie około 2,06 bitów na klucz. Można go skonfigurować tak, aby zużywał mniej miejsca, ale generowanie jest wolniejsze.