Funkcja, która rozprowadza dane wejściowe

Chciałbym wiedzieć, czy istnieje funkcja od liczb n-bitowych do liczb n-bitowych, która ma następujące cechy:$f$

• $f$ powinien być bijectywny
• Zarówno i powinny być obliczalne dość szybko$f$$f^{-1}$
• $f$ powinien zwrócić liczbę, która nie ma znaczącej korelacji z wprowadzonymi danymi.

Uzasadnienie jest następujące:

Chcę napisać program działający na danych. Niektóre informacje o danych są przechowywane w drzewie wyszukiwania binarnego, w którym klucz wyszukiwania jest symbolem alfabetu. Z czasem dodałem kolejne symbole do alfabetu. Nowe symbole po prostu uzyskają następny bezpłatny numer. Dlatego drzewo zawsze będzie miało niewielkie odchylenie od mniejszych kluczy, co powoduje większe zrównoważenie, niż myślę, że powinno być potrzebne.

Moim pomysłem jest zmieszanie liczb symboli tak, aby były szeroko rozłożone w całym zakresie . Ponieważ liczby symboli mają znaczenie tylko na wejściu i wyjściu, co dzieje się tylko raz, zastosowanie takiej funkcji nie powinno być zbyt drogie.[ 0 , 2 64 - 1 $f$$[0,2^{64}-1]$

Myślałem o jednej iteracji generatora liczb losowych Xorshift, ale tak naprawdę nie wiem, jak to cofnąć, chociaż teoretycznie powinno to być możliwe.

Czy ktoś zna taką funkcję?
Czy to dobry pomysł?

Możesz użyć skrótu Fibonacciego , a mianowicie

.$\qquad h_F(k) = k \cdot \frac{\sqrt{5} - 1}{2} - \left\lfloor k \cdot \frac{\sqrt{5} - 1}{2} \right\rfloor$

Dla dostać n liczb parami-wyraźny (o) równomiernie w [ 0 , 1 ] . Skalowanie do [ 1 .. M ] i zaokrąglanie (w dół) pozwala uzyskać równomierne rozłożenie liczb w tym przedziale.$k=1,\dots,n$$n$$[0,1]$$[1..M]$

Na przykład są to skalowane do [ 0..10000 ] (lewa pierwotna sekwencja, prawa posortowana):$h_F(1), \dots, h_F(200)$$[0..10000]$

Jest to przykład tego, co Knuth nazywa multiplikatywnym haszowaniem . Dla rozmiarze słowo komputera, niektóre całkowitą stosunkowo prime do wag i M liczby adresów potrzebnych używamy$w$$A$$w$$M$

$\qquad h(k) = \left\lfloor M \left( \bigl( k \cdot \frac{A}{w}\bigr) \mod 1 \right) \right\rfloor$

jako funkcja mieszająca. Powyżej następuje (upewnij się, że możesz go obliczyć z wystarczającą precyzją). Chociaż działa to również z dowolną inną liczbą niewymierną pozaϕ-1, jest to jedna z dwóch liczb, które prowadzą do liczb „najbardziej równomiernie rozmieszczonych”.$A/w = \phi^{-1} = \frac{\sqrt{5}-1}{2}$$\phi^{-1}$

Znajdź więcej w The Art of Computer Programming , Tom 3 autorstwa Donalda Knutha (rozdział 6.4 ze strony 513 w drugim wydaniu). W szczególności dowiesz się, dlaczego uzyskane liczby są odrębne parami (przynajmniej jeśli ) i jak obliczyć funkcję odwrotną, jeśli użyjesz naturalnego A i w zamiast ϕ - 1 .$n \ll M$$A$$w$$\phi^{-1}$

Dla wejść bit ta funkcja działa:$k$

$\mathrm{hash}(n) = (n \bmod 2^{\lceil\frac{k}{2}\rceil})\cdot 2^{\lceil\frac{k}{2}\rceil} + n \,\mathrm{div}\, 2^{\lceil\frac{k}{2}\rceil}$

Jest to odwracalne, ponieważ , i ma pary niesekwencyjne { n , m } , n < m , gdzie h a s h ( m ) < h a s h ( n ) . Uwaga: dane wyjściowe i wejściowe mogą się korelować, zwłaszcza jeśli dane wejściowe są w { 1 , … , 2 ⌈ $\mathrm{hash}(\mathrm{hash}(n)) = n$$\{n,m\}, n < m$$\mathrm{hash}(m) < \mathrm{hash}(n)$.$\{1,\dots,2^{\lceil\frac{k}{2}\rceil}-1\}$

Ref: Odwracalna funkcja skrótu