Случайность функций хеширования, таких как SHA1

Я пытаюсь сгенерировать равномерное распределение случайных чисел на основе идентификаторов пользователей. То есть мне нужно случайное число для каждого пользователя, которое остается неизменным каждый раз, когда пользователь запрашивает случайное число (но пользователю не нужно хранить это число). Мой текущий алгоритм (в PHP) для подсчета распределения для заданного большого массива идентификаторов пользователей $arr:

$range = 100;
$results = array_fill(0, $range, 0);

foreach ($arr as $userID) {
    $hash = sha1($userID,TRUE);
    $data = unpack('L*', $hash);
    $seed = 0;
    foreach ($data as $integer) {
        $seed ^= $integer;
    }
    srand($seed);
    ++$results[rand(0, $range-1)];
}

Можно было бы надеяться, что это приведет к приблизительно равномерному распределению. Но это не так! Я проверил, чтобы убедиться, что каждое значение в $arr уникально, но одна запись в списке всегда получает гораздо больше активности, чем все остальные. Есть ли лучший метод генерации хэша строки, который даст приблизительно равномерное распределение? Очевидно, ША не подходит для этой работы. Я также пробовал MD5 и простой crc32, все с теми же результатами!?

Я сошел с ума? Является ли единственным объяснением, что я на самом деле не проверил, что каждая запись в $arr уникальна?

Author: Ed Marty, 2012-08-02
Source

4 answers

mt_rand() должно быть очень равномерное распределение по запрошенному диапазону. Когда пользователи будут созданы, создайте случайное начальное значение для этого пользователя, используя mt_rand(), а затем всегда mt_srand() с этим начальным значением для этого пользователя.

Чтобы получить равномерное распределение от 0 до 99, в качестве вашего примера, просто mt_rand(0,$range-1). Выполнение трюков с sha1, md5 или каким-либо другим алгоритмом хеширования на самом деле не даст вам более равномерного распределения, чем прямое случайное.

 1
Author: MightyE, 2012-08-01 23:39:01

Хэш-номера sha1 распределены довольно равномерно. После выполнения этого:

<?php

$n = '';
$salt = 'this is the salt';

for ($i=0; $i<100000; $i++) {
    $n .= implode('', unpack('L*', sha1($i . $salt)));
}   

$count = count_chars($n, 1);
$sum = array_sum($count);

foreach ($count as $k => $v) {
    echo chr($k)." => ".($v/$sum)."\n";
} 

?>

Вы получаете этот результат. Вероятность для каждого числа:

0 => 0.083696057956298
1 => 0.12138983759522
2 => 0.094558704004335
3 => 0.07301783188663
4 => 0.092124978934097
5 => 0.088623772577848
6 => 0.11390989553446
7 => 0.092570936094051
8 => 0.12348330833868
9 => 0.11662467707838

Вы можете использовать sha1 в качестве простого генератора случайных чисел на основе идентификатора пользователя.

В шестнадцатеричном виде распределение близко к идеальному: 

//  $n .= sha1($i . $salt, false);

0 => 0.06245515
1 => 0.06245665
2 => 0.06258855
3 => 0.0624244
4 => 0.06247255
5 => 0.0625422
6 => 0.0625246
7 => 0.0624716
8 => 0.06257355
9 => 0.0625005
a => 0.0625068
b => 0.0625086
c => 0.0624463
d => 0.06250535
e => 0.06250895
f => 0.06251425
 3
Author: Pedro L., 2012-08-02 01:19:15

Было бы полезно, если бы вы опубликовали свои результаты, которые привели вас к выводу, что вы не получаете соответствующего распространения, но, скорее всего, здесь происходит одна из трех вещей:

  1. Вы просто смотрите на слишком маленькую выборку и/или неправильно интерпретируете свои данные. Как отмечали другие, вполне разумно, чтобы равномерное распределение не имело абсолютно однородного результата.

  2. Вы бы увидели лучшие результаты, если бы использовали mt_rand вместо того, чтобы rand.

  3. (Лично я думаю, что это наиболее вероятно) Вы чрезмерно оптимизируете генерацию семян и теряете данные / дырявите голубей / в противном случае ухудшаете свою способность генерировать случайные числа. Читая ваш код, я думаю, что вы делаете следующее:

    1. Генерировать однородный случайный хэш неизвестного значения
    2. Разделите хэш на длинные строки и побитово соедините их вместе
    3. Установка начального значения rand и генерация случайного числа на основе этого семя

    Но почему вы делаете шаг 2? Как вы думаете, какую выгоду вы получаете от этого? Попробуйте сделать этот шаг и просто используйте первое значение, которое вы извлекли из хэша, в качестве исходного, и посмотрите, не даст ли это вам лучших результатов. Хорошее эмпирическое правило со случайностью - не пытайтесь перехитрить людей, которые реализовали алгоритмы, это невозможно:)

 0
Author: dimo414, 2012-08-02 00:43:36

Хотя все ответы здесь хороши, я дам ответ, который был правильным для меня, и это то, что я действительно был сумасшедшим. По-видимому, команда uniq на самом деле работает не так, как я ожидал (сначала необходимо отсортировать данные). Таким образом, объяснение действительно заключалось в том, что значения в $arr не были уникальными.

 0
Author: Ed Marty, 2012-08-02 14:16:04