Se hai bisogno di circa 10 milioni di chiavi univoche (ad esempio), l'approccio migliore è scegliere uno spazio chiave esponenzialmente più grande e iniziare a generare in modo casuale. Leggi il Paradosso del compleanno -- è la cosa principale di cui dovresti preoccuparti. Se desideri 2^n chiavi univoche e sicure, assicurati che ci siano almeno 2^(2 * n) valori possibili. Ecco un algoritmo approssimativo O(n log n):
- Utilizza uno spazio chiave di almeno 2^50 (quindi, in altre parole, consenti 2^50 possibili valori univoci) e non avrai quasi nessuna collisione nell'intero set di dati e chiunque forzi bruscamente le tue chiavi lo farà hanno circa pari probabilità di ottenere una chiave se ne provano 2^25.
- genera tutti i numeri casuali di cui hai bisogno
- indicizza il database sulla tua chiave (questo è il passaggio O(n lg n):l'ordinamento)
- scorri il DB ed esegui l'iterazione sull'intero set di dati per eliminare i duplicati (pseudocodice di seguito)
- Elimina le righe duplicate e il gioco è fatto.
Pseudocodice:
$last = null;
while ($current = getnext()) {
if ($last == $current) {
push($toDelete, $current);
}
$last = $current;
}
