Как длина влияет на коллизии
Это просто вопрос перестановок.
Если я использую небольшие хеш-значения (7-8 бит), то возникают некоторые коллизии.
Что ж, давайте проанализируем это. С 8 битами существует 2^8 возможных двоичных последовательностей, которые могут быть сгенерированы для любого заданного входа. Это 256 возможных хеш-значений, которые могут быть сгенерированы, что означает, что теоретически каждые 256 сгенерированных значения дайджеста сообщения гарантируют коллизию. Это называется проблемой дня рождения.
Если я увеличу биты в хеш-значении, скажем, до 31, то будет 0 коллизий - все ngrams сопоставляются с разными хэш-значениями.
Что ж, давайте применим ту же логику. С 31-битной точностью у нас есть 2^31 возможных комбинаций. Это 2147483648 возможных комбинаций. И мы можем обобщить это на:
Let N denote the amount of bits we use.
Amount of different hash values we can generate (X) = 2^N
Assuming repetition of values is allowed (which it is in this case!)
Это экспоненциальный рост, поэтому с 8 битами вы обнаружили много коллизий, а с 31 битами — очень мало столкновений.
Как это влияет на коллизии?
Что ж, с очень небольшим количеством значений и равной вероятностью сопоставления каждого из этих значений с входными данными у вас есть следующее:
Let A denote the number of different values already generated.
Chance of a collision is: A / X
Where X is the possible number of outputs the hashing algorithm can generate.
Когда X равняется 256, у вас есть 1/256 вероятность столкновения в первый раз. Тогда у вас есть 2/256 шанс столкновения, когда генерируется другое значение. Пока, в конце концов, вы не сгенерируете 255 различных значений, и у вас будет 255/256 вероятность столкновения. В следующий раз, очевидно, это станет 256/256 шансом, или 1, что является вероятностной уверенностью. Понятно, что обычно до этого не доходит. Столкновения, скорее всего, будут происходить гораздо чаще, чем каждые 256 циклов. На самом деле, парадокс дня рождения говорит нам, что мы можем начать ожидать коллизии после того, как будет сгенерировано 2^N/2 значений дайджеста сообщения. Следуя нашему примеру, мы создали 16 уникальных хэшей. Однако мы знаем, что это должно происходить минимум каждые 256 циклов. Что не хорошо!
На математическом уровне это означает, что вероятность коллизии обратно пропорциональна возможному количеству выходов, поэтому нам нужно увеличить размер дайджеста сообщения до разумной длины. .
Примечание об алгоритмах хеширования
Столкновения совершенно неизбежны. Это связано с тем, что существует чрезвычайно большое количество возможных входных данных (2 ^ Все возможные коды символов) и конечное количество возможных выходных данных (как показано выше).
person
christopher
schedule
06.05.2013
