Понимание коллизий с помощью пользовательского хеширования

Question

Я использую в своем приложении следующее:

base64.urlsafe_b64encode(str(random.getrandbits(20))).lower().replace('=', '')

минус эстетические изменения:

base64.urlsafe_b64encode(str(random.getrandbits(20))

Как мне выяснить вероятность столкновения?

Answer 1

Есть 2 ^ 20 различных возможных случайных значений.Таким образом, вероятность того, что два заданных случайных значения будут равны, равна 1 / (2 ^ 20) или около 1 на миллион .

Однако, если вы создаете несколько значений, тогда из-зак парадоксу дня рождения вам нужно будет сгенерировать только около 2 ^ 10 или около тысячи различных значений , чтобы получить 50% -ную вероятность того, что два из них будут равны!

Чтобы избежать этого, я бы рекомендовал не менее 128 бит.Для этого требуется около 2 ^ 64 (~ 18 миллиардов миллиардов) значений, прежде чем вероятность столкновения составит 50%.При кодировании в base-64 длина будет 22 символа.

Answer 2

Это такая же вероятность столкновения одного random.getrandbits(20) с другим, поскольку внешние функции являются детерминированными.

Если выходные данные random.getrandbits на самом деле случайны - вероятность столкновения одного с другим составляет 1 / (2 ^ 20) или ... примерно 1 на миллион

Для n записей вероятность того, что дополнительная запись (запись n + 1) столкнется, равна n / (2 ^ 20). Таким образом, вероятность растет линейно с количеством записей в словаре. При 1048 576 записях гарантируется, что следующая запись столкнется.