Fonction qui propage l'entrée

Je voudrais savoir s'il existe une fonction des nombres à n bits aux nombres à n bits qui présente les caractéristiques suivantes: $f$

$f$ doit être bijectif
Les deux et devrait être assez rapide calculable $f$ $f^{-1}$
$f$ doit renvoyer un nombre qui n'a pas de corrélation significative avec son entrée.

La justification est la suivante:

Je veux écrire un programme qui fonctionne sur des données. Certaines informations des données sont stockées dans une arborescence de recherche binaire où la clé de recherche est un symbole d'un alphabet. Avec le temps, j'ajoute d'autres symboles à l'alphabet. Les nouveaux symboles obtiennent simplement le prochain numéro gratuit disponible. Par conséquent, l'arborescence aura toujours un petit biais vers des touches plus petites, ce qui provoque un rééquilibrage plus important que je ne le pense.

Mon idée est de réduire les nombres de symboles avec telle sorte qu'ils soient largement répartis sur toute la plage de . Étant donné que les numéros de symbole n'ont d'importance que lors de l'entrée et de la sortie, ce qui ne se produit qu'une seule fois, l'application d'une telle fonction ne devrait pas être trop coûteuse. $f$ $[0,2^{64}-1]$

J'ai pensé à une itération du générateur de nombres aléatoires Xorshift, mais je ne connais pas vraiment un moyen de l'annuler, bien que cela devrait théoriquement être possible.

Quelqu'un connaît-il une telle fonction?
Est-ce une bonne idée?

binary-trees hash binary-arithmetic FUZxxl
la source

Je ne suis pas un expert, mais vous pouvez peut-être utiliser une permutation pseudo-aléatoire (voir par exemple le chiffrement Feistel )

Vor

Si vous calculez essentiellement une fonction de hachage, pourquoi ne pas utiliser le hachage?

vonbrand

@vonbrand Hashing n'est pas réversible. Voir exigence numéro 2.

FUZxxl

Pourquoi doit-il être réversible? Quel est le problème avec le rendre réversible par recherche?

vonbrand

Vous pouvez stocker (f (x), x) sous forme de clés.

adrianN

Réponses:

Vous pouvez utiliser le hachage de Fibonacci , à savoir

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

Pour vous obtenez nombres distincts par paires (environ) répartis uniformément dans . En mettant à l'échelle et en arrondissant (vers le bas), vous obtenez des nombres répartis uniformément dans cet intervalle. $k=1,\dots,n$ $n$ $[0,1]$ $[1..M]$

Par exemple, ce sont mis à l'échelle (séquence d'origine gauche, trié à droite): $h_F(1), \dots, h_F(200)$ $[0..10000]$

entrez la description de l'image ici

Ceci est un exemple de ce que Knuth appelle le hachage multiplicatif . Pour la taille du mot de l'ordinateur, certain entier relativement premier à et le nombre d'adresses nécessaires, nous utilisons $w$ $A$ $w$ $M$

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

comme fonction de hachage. Ce qui précède suit avec (assurez-vous de pouvoir le calculer avec une précision suffisante). Bien que cela fonctionne également avec tout autre nombre irrationnel en plus de, c'est l'un des deux seuls nombres qui conduisent aux nombres "les plus uniformément répartis". $A/w = \phi^{-1} = \frac{\sqrt{5}-1}{2}$ $\phi^{-1}$

Pour en savoir plus, consultez L'art de la programmation informatique , volume 3 de Donald Knuth (chapitre 6.4 à partir de la page 513 de la deuxième édition). En particulier, vous découvrirez pourquoi les nombres résultants sont distincts par paires (au moins si ) et comment calculer la fonction inverse si vous utilisez et naturels au lieu de . $n \ll M$ $A$ $w$ $\phi^{-1}$

Raphael
la source

Comment calculer efficacement

f^{- 1}

$f^{-1}$

frafl

@frafl J'espère que ma modification répond quelque peu à votre préoccupation. Il est clair, cependant, que ces techniques de hachage ne sont pas spécialement conçues pour être efficacement inversibles.

Raphael

Oui, je vais le voter, mais je ne le recommanderais pas comme réponse acceptée.

frafl

Pour les entrées bits, cette fonction fonctionne: $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}$

Ceci est réversible, en ce que , et a des paires non séquentielles , où . Attention, la sortie et l'entrée peuvent être corrélées, surtout si votre entrée est en $\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\}$

Réf: Fonction de hachage réversible

Reza
la source

Cela semble simple et agréable. Je vais tester celui-là.

FUZxxl

1

$1$

ρ

$\rho$

c'est assez clair! pour 64 bits (0x00000000FFFFFFFF) et vous devez décaler (<<) 32 bits. Cette fonction est simple, pratique et assez rapide en pratique.

Reza

x \in {1, \dots, 2^{32} - 1}

$x \in \{1,\dots,2^{32}-1\}$

2^{32} x

$2^{32}x$