Función que extiende la entrada

Me gustaría saber si hay una función de números de n bits a números de n bits que tenga las siguientes características:$f$

• $f$ debe ser biyectivo
• Tanto como deben calcularse bastante rápidof - $f$$f^{-1}$
• $f$ debería devolver un número que no tenga una correlación significativa con su entrada.

La razón es esta:

Quiero escribir un programa que funcione con datos. Parte de la información de los datos se almacena en un árbol de búsqueda binario donde la clave de búsqueda es un símbolo de un alfabeto. Con el tiempo, agrego más símbolos al alfabeto. Los nuevos símbolos simplemente obtienen el siguiente número gratuito disponible. Por lo tanto, el árbol siempre tendrá un pequeño sesgo en las teclas más pequeñas, lo que provoca un reequilibrio mayor de lo que creo que debería ser necesario.

Mi idea es manglear los números de los símbolos con manera que se extiendan ampliamente en todo el rango de . Dado que los números de los símbolos solo importan durante la entrada y la salida, lo que ocurre solo una vez, la aplicación de dicha función no debería ser demasiado costosa.[ 0 , 2 64 - 1 $f$$[0,2^{64}-1]$

Pensé en una iteración del generador de números aleatorios Xorshift, pero realmente no sé cómo deshacerlo, aunque en teoría debería ser posible.

¿Alguien sabe tal función?
¿Es esta una buena idea?

Puede usar el hash de Fibonacci , a saber

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

Para obtienes n números separados por pares (aproximadamente) distribuidos uniformemente en [ 0 , 1 ] . Al escalar a [ 1 .. M ] y redondear (hacia abajo), obtienes números distribuidos uniformemente en ese intervalo.$k=1,\dots,n$$n$$[0,1]$$[1..M]$

Por ejemplo, estos son escalados a [ 0..10000 ] (secuencia original izquierda, ordenada a la derecha):$h_F(1), \dots, h_F(200)$$[0..10000]$

Esta es una instancia de lo que Knuth llama hashing multiplicativo . Para el tamaño de palabra de la computadora, A algún número entero relativamente primo para w y M el número de direcciones necesarias, utilizamos$w$$A$$w$$M$

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

como función hash. Lo anterior sigue con (asegúrese de poder calcularlo con suficiente precisión). Si bien esto también funciona con cualquier otro número irracional además deϕ-1, es uno de los dos únicos números que conducen a los números "más uniformemente distribuidos".$A/w = \phi^{-1} = \frac{\sqrt{5}-1}{2}$$\phi^{-1}$

Encuentre más en El arte de la programación de computadoras , Volumen 3 de Donald Knuth (capítulo 6.4 de la página 513 en la segunda edición). En particular, encontrará por qué los números resultantes son distintos por pares (al menos si ) y cómo calcular la función inversa si usa A y w naturales en lugar de ϕ - 1 .$n \ll M$$A$$w$$\phi^{-1}$

Para entradas de bits, esta función funciona:$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}$

Esto es reversible, ya que , y tiene pares no secuenciales { n , m } , n < m , donde h a s h ( m ) < h a s h ( n ) . Tenga en cuenta que la salida y la entrada pueden correlacionarse, especialmente si su entrada está en { 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: función hash reversible