Funzione hash casuale senza collisioni

Questa non è una funzione hash. È una funzione di codifica o di crittografia.

Di solito quando ho riscontrato un problema con questo modulo, è perché ho una sorta di ID che voglio "sembrare" casuale. Supponendo che non mi interessi per la sicurezza, normalmente creerò un algoritmo che funziona come segue:

1. Mappa i miei dati in numeri (di solito trattando una stringa in un set di caratteri contenente caratteri X come numero baseX).
2. Mappa i miei numeri a nuovi numeri. Eric Lippert suggerisce di utilizzare Multiplicative Inverses per questo scopo. La codifica Skip32 (la crittografia AKA di Skip32, ma è non sicura) funziona anche a questo scopo.
3. Invertire la mappatura nel passaggio 1.

Per decodificare, esegui gli stessi passaggi al contrario.

Utilizzerei una funzione di hash perfetta per mappare il tuo set di n input a un numero intero univoco < n, quindi usalo come indice in una matrice di output (ad esempio un elenco di n colori) o mappalo su una stringa univoca nel tuo set di caratteri (ad esempio converti il numero in base 26 e render ogni cifra in base-26 come quella lettera dell'alfabeto).

Mi sembra che Format Preserving Encryption sia esattamente quello che stai cercando, tranne forse le proprietà di sicurezza implicite dalla "crittografia". La pagina di Wikipedia rileva che

For such finite domains, and for the purposes of the discussion below, the cipher is equivalent to a permutation of N integers {0, ... , N−1} where N is the size of the domain.

Per il tuo caso, le parole di 4 lettere con x possibilità per ogni carattere sarebbero codificate come numeri interi trattandole come numeri base-x. Quindi la permutazione avrebbe mappato quell'input in un output distinto, che sarebbe stato decodificato in una stringa invertendo la trasformata base-x.

Sembra che il modo migliore per implementare tale permutazione sia applicare una permutazione di M-bit al valore di input, e se il risultato è N o più per applicarlo nuovamente al risultato fino a che il risultato è minore di N, chiamato anche ciclo walking. Funziona meglio quando N è leggermente inferiore a 2 ^ M.

Ci sono modi per utilizzare Feistel Networks per adattare crittografie di ampie dimensioni per produrre permutazioni di larghezza di bit arbitrarie, ma ciò richiede che iterazione della rete produca una buona permutazione.