Questo è in qualche modo correlato a Quale algoritmo di hashing è meglio per unicità e velocità? . In questa domanda, la risposta in modo eccellente scritta note,
Randomnessification
The other subjective measure is how randomly distributed the hashes are. Mapping the resulting HashTables shows how evenly the data is distributed.
(qui, "random" non viene usato per significare "deterministico" - tutte le funzioni in esame sono deterministiche.)
Sulla base dell'eccellente risposta di questa domanda, ho implementato FNV-1A. Tuttavia, i risultati che sto ottenendo non sembrano particolarmente "casuali" distribuiti:
In [19]: for x in xrange(10):
....: h = Fnv1A(); h.update(b'testing' + str(x)); print hex(h.value)
....:
0x3e249fc5d899c731L
0x3e249ec5d899c57eL
0x3e249dc5d899c3cbL
0x3e249cc5d899c218L
0x3e24a3c5d899cdfdL
0x3e24a2c5d899cc4aL
0x3e24a1c5d899ca97L
0x3e24a0c5d899c8e4L
0x3e2497c5d899b999L
0x3e2496c5d899b7e6L
Si noti che la maggior parte dei bit nell'output qui sono uguali.
FNV-1A si suppone che sia una funzione estremamente discontinua? vale a dire che l'output cambia drasticamente per piccole modifiche nell'input; mostra l'effetto Avalanche .
Si noti che questo è ortogonale all'essere uniformemente distribuito, che anch'io voglio.
Sto tentando di utilizzare FNV-1A per distribuire casualmente gli utenti in uno dei bucket ponderati n . Nessuno degli input è controllato dall'utente, quindi la sicurezza non è molto preoccupante, ma gli input sono altamente non casuali (sono interi autoincrementanti ...); Tuttavia, ho bisogno che i due output siano casuali (ma deterministici): per un dato ID utente, dovrebbe essere casuale in quale bucket essi finiscono.
In realtà ho chiesto un'altra domanda simile qualche tempo fa; Capisco che le uscite hash non necessariamente bisogno siano casuali (per hashtables, tutto quello che ti interessa è che non entrano in collisione). Per la mia particolare applicazione, sfortunatamente ho bisogno di casualità.
(Nel caso in cui sei curioso della correttezza della mia implementazione,
In [22]: h = experiment.Fnv1A(); h.update(b'foobar'); h.value
Out[22]: 9625390261332436968L
... visto che questo è per lavoro, sto provando a condividere il meno codice necessario. Questa domanda riguarda più FNV-1A stesso, piuttosto che la mia particolare implementazione.)