Как проверить хеш-столкновение

Question

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

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--; 
}