Как проверить хеш-коллизию

Question

Я создал функцию в php, которая генерирует хеш из числа (id), и мне нужно убедиться, что не будет столкновений (два или более идентификаторов имеют одинаковый хеш). Какую функцию я могу использовать, чтобы убедиться, что в идентификаторах nexts 99999999 не будет коллизий? Спасибо!

Answer 1

Если ваша хеш-функция работает как положено, и всегда генерирует один и тот же вывод для одного и того же ввода. И ваши входные данные ограничены номерами 99999999, вы можете просто сгенерировать хэши для этих номеров и убедиться, что дубликатов нет.

Хотя хорошим решением было бы математически продемонстрировать, что ваша хеш-функция будет давать уникальные результаты для этих чисел.

Answer 2

Если хеш может быть полностью случайным, попробуйте использовать текущую временную метку в нем в качестве дополнительного рандомизатора.Например:

$hash = sha1(microtime() * rand(1, 9999));

Вероятность появления дубликата довольно мала.Кроме того, попробуйте установить поле базы данных равным UNIQUE, чтобы гарантировать, что дубликат INSERT невозможен.Затем, чтобы все было завершено, вы можете создать цикл, который будет пытаться выполнить до тех пор, пока он не будет успешным, например:

// SHA1 values shouldn't need escaping, but it doesn't really hurt to be extra sure :)
$query = "INSERT INTO `table` (`hash`) VALUES('" . mysql_real_escape_string($hash) . "')";

// Let's try the insert with a max of 10 random hashes
$tries = 10;
while(mysql_query($query) !== true) {
    if($tries <= 0) {
        break; // Something is really failing, stop trying!
    }

    // If this point is reached, apparantly a duplicate was created. Try again.
    $hash = sha1(microtime() * rand(1, 9999));

    // Decrement the tries counter.
    $tries--;
}