Hvis du har brug for omkring 10 millioner unikke nøgler (for eksempel), er den bedste tilgang at vælge et nøglerum, der er eksponentielt større, og begynde at generere tilfældigt. Læs om fødselsdagsparadokset -- det er det vigtigste, du skal være bekymret for. Hvis du vil have 2^n unikke og sikre nøgler, skal du sørge for, at der er mindst 2^(2 * n) mulige værdier. Her er en grov O(n log n) algoritme:
- Brug et nøglerum på mindst 2^50 (så, med andre ord, tillad 2^50 mulige unikke værdier), og du vil næsten ikke have kollisioner i hele dit datasæt -- og enhver brutal tvinger dine nøgler vil har omtrent lige chancer for at få en nøgle, hvis de prøver 2^25 af dem.
- generer så mange tilfældige tal, som du har brug for
- indekser databasen på din nøgle (dette er O(n lg n)-trinnet:sorteringen)
- blad gennem databasen og gentag hele datasættet for at trimme dubletter (pseudokode nedenfor)
- Slet de duplikerede rækker, og du er færdig.
Pseudokode:
$last = null;
while ($current = getnext()) {
if ($last == $current) {
push($toDelete, $current);
}
$last = $current;
}