Funktion, die die Eingabe verbreitet

Ich würde gerne wissen, ob es eine Funktion von n-Bit-Zahlen bis n-Bit-Zahlen gibt, die die folgenden Eigenschaften aufweist:$f$

• $f$ sollte bijektiv sein
• Sowohl als auch sollten ziemlich schnell berechenbar sein$f$$f^{-1}$
• $f$ sollte eine Zahl zurückgeben, die keine signifikante Korrelation zu ihrer Eingabe aufweist.

Das Grundprinzip ist folgendes:

Ich möchte ein Programm schreiben, das mit Daten arbeitet. Einige Informationen der Daten werden in einem binären Suchbaum gespeichert, in dem der Suchschlüssel ein Symbol eines Alphabets ist. Mit der Zeit füge ich dem Alphabet weitere Symbole hinzu. Neue Symbole erhalten einfach die nächste freie Nummer. Daher wird der Baum immer eine kleine Neigung zu kleineren Schlüsseln haben, was mehr Neuausgleich bewirkt, als ich für nötig halte.

Meine Idee ist es, die Symbolzahlen mit so zu zerfleischen, dass sie über den gesamten Bereich von . Da die Symbolnummern nur bei der einmaligen Ein- und Ausgabe eine Rolle spielen, sollte die Anwendung einer solchen Funktion nicht zu teuer sein.$f$$[0,2^{64}-1]$

Ich habe über eine Iteration des Xorshift-Zufallszahlengenerators nachgedacht, aber ich weiß nicht wirklich, wie ich sie rückgängig machen kann, obwohl dies theoretisch möglich sein sollte.

Kennt jemand eine solche Funktion?
Ist das eine gute Idee?

Sie können nämlich Fibonacci-Hashing verwenden

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

Für Sie n paarweise getrennte Zahlen (ungefähr), die in [ 0 , 1 ] gleichmäßig verteilt sind . Wenn Sie auf [ 1 .. M ] skalieren und abrunden, erhalten Sie ungefähr gleichmäßig verteilte Zahlen in diesem Intervall.$k=1,\dots,n$$n$$[0,1]$$[1..M]$

Dies sind zum Beispiel skaliert auf [ 0..10000 ] (linke ursprüngliche Sequenz, rechts sortiert):$h_F(1), \dots, h_F(200)$$[0..10000]$

Dies ist ein Beispiel für das, was Knuth multiplikatives Hashing nennt . Für die Wortgröße des Computers, eine ganze Zahl, die relativ zu w primiert ist, und M die Anzahl der benötigten Adressen, die wir verwenden$w$$A$$w$$M$

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

als hashing funktion. Das Obige folgt mit (stellen Sie sicher, dass Sie es mit einer ausreichenden Genauigkeit berechnen können). Während dies auch mit jeder anderen irrationalen Zahl außerϕ-1funktioniert, ist es eine von nur zwei Zahlen, die zu den "am gleichmäßigsten verteilten" Zahlen führen.$A/w = \phi^{-1} = \frac{\sqrt{5}-1}{2}$$\phi^{-1}$

Mehr dazu in Die Kunst der Computerprogrammierung , Band 3 von Donald Knuth (Kapitel 6.4 ab Seite 513 in der zweiten Ausgabe). Insbesondere werden Sie feststellen, warum die resultierenden Zahlen paarweise verschieden sind (zumindest wenn ) und wie Sie die Umkehrfunktion berechnen, wenn Sie natürliches A und w anstelle von ϕ - 1 verwenden .$n \ll M$$A$$w$$\phi^{-1}$

Für Bit-Eingänge funktioniert diese Funktion:$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}$

Dies ist dahingehend umkehrbar, dass ist und nicht sequentielle Paare { n , m } , n < m , wobei h a s h ( m ) < h a s ist h ( n ) . Beachten Sie, dass Ausgabe und Eingabe korrelieren können, insbesondere wenn Ihre Eingabe in { 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: Reversible Hash-Funktion