Ако имате нужда от около 10 милиона уникални ключове (например), най-добрият подход е да изберете ключово пространство, което е експоненциално по-голямо, и да започнете произволно генериране. Прочетете за парадокса на рождения ден -- това е основното нещо, за което трябва да се тревожите. Ако искате 2^n уникални и сигурни ключа, уверете се, че има поне 2^(2 * n) възможни стойности. Ето един груб алгоритъм O(n log n):
- Използвайте ключово пространство от поне 2^50 (така че, с други думи, позволете 2^50 възможни уникални стойности) и едва ли ще имате сблъсъци в целия си набор от данни – и всеки, който грубо налага вашите ключове, ще имат приблизително равни шансове да получат ключ, ако опитат 2^25 от тях.
- генерирайте колкото се може повече случайни числа
- индексирайте базата данни на вашия ключ (това е стъпката O(n lg n):сортирането)
- преглеждайте базата данни и итерирайте целия набор от данни, за да изрежете дубликати (псевдокод по-долу)
- Изтрийте дублиращите се редове и сте готови.
Псевдокод:
$last = null;
while ($current = getnext()) {
if ($last == $current) {
push($toDelete, $current);
}
$last = $current;
}
