Om du behöver cirka 10 miljoner unika nycklar (till exempel), är det bästa tillvägagångssättet att välja ett nyckelutrymme som är exponentiellt större och börja generera slumpmässigt. Läs om födelsedagsparadoxen -- Det är det viktigaste du bör vara orolig för. Om du vill ha 2^n unika och säkra nycklar, se till att det finns minst 2^(2 * n) möjliga värden. Här är en grov O(n log n)-algoritm:
- Använd ett nyckelmellanrum på minst 2^50 (så, med andra ord, tillåt 2^50 möjliga unika värden), så kommer du knappt ha kollisioner i hela din datauppsättning -- och alla råa som tvingar dina nycklar kommer att har ungefär jämna odds att få en nyckel om de provar 2^25 av dem.
- generera så många slumptal som du behöver
- indexera databasen på din nyckel (detta är O(n lg n)-steget:sorteringen)
- bläddra igenom databasen och iterera över hela datamängden för att trimma dubbletter (pseudokod nedan)
- Ta bort dubblettraderna och du är klar.
Pseudokod:
$last = null;
while ($current = getnext()) {
if ($last == $current) {
push($toDelete, $current);
}
$last = $current;
}