Mandor
Новичок
tf
Вероятность увеличится. Сам алгоритм хеширования не принципиален, важно, что если мы на одном из этапов получим коллизию, то эта коллизия перейдет в результат. Причем достаточно получить коллизию на любом этапе, т.е. чем этих этапов больше, тем больше шанс.
Если говорить о принципиальной возможности уменьшить количество коллизий не увеличивая размер получаемого хеша, то это в общем случае не возможно. Вернее, это возможно путем улучшения самого алгоритма хеширования, что постоянно и делается.
Иногда существуют исключения, например, в данной задаче использовать длину файла явно хорошая идея. Даже если нельзя было бы увеличивать длину хеша, то можно было бы запросто выкинуть из него 4 байта и вставить туда длину и это наверняка уменьшило бы колличество коллизий. Про md5()/sha1()+длина вообще речи нет, не удивлюсь, что если прохешировать данной функцией все файлы на земле, то коллизии мы так и не встретим. (Конечно речь о том что коллизии не будут подбирать специально.)
Если поставить задачу так, что надо обязательно уменьшить количество коллизий, то, очевидно, что нужно увеличивать размер выходного хеша. Как именно - вариантов море: начиная от конкатенации результатов двух хеш функций и заканчивая функцией gzencode() (шанс коллизии 0%, но хеш большоой
).
P.S. Задача индексирования паблик торрент-трекеров не реальная, вообще никаких вариантов. Если вы гугль или рапидшара то можно подумать. Локальную сеть индексировать не проблема, но к чему тогда разговор про хеши, там файлов на много порядков меньше того значиния когда пора думать.
Я бы лучше начал решение вопроса с другой стороны: как заставить держателей файлов посчитать хеш по вашему алгоритму? Если не получится, то, может, составлять хеш из частей файла, т.е. скачивать куски выборочно (тем более что, вроде, торрент-клиенты считают хеши кусков), возможно удалось бы использовать какую-то паблик-информацию.
Вероятность увеличится. Сам алгоритм хеширования не принципиален, важно, что если мы на одном из этапов получим коллизию, то эта коллизия перейдет в результат. Причем достаточно получить коллизию на любом этапе, т.е. чем этих этапов больше, тем больше шанс.
Если говорить о принципиальной возможности уменьшить количество коллизий не увеличивая размер получаемого хеша, то это в общем случае не возможно. Вернее, это возможно путем улучшения самого алгоритма хеширования, что постоянно и делается.
Иногда существуют исключения, например, в данной задаче использовать длину файла явно хорошая идея. Даже если нельзя было бы увеличивать длину хеша, то можно было бы запросто выкинуть из него 4 байта и вставить туда длину и это наверняка уменьшило бы колличество коллизий. Про md5()/sha1()+длина вообще речи нет, не удивлюсь, что если прохешировать данной функцией все файлы на земле, то коллизии мы так и не встретим. (Конечно речь о том что коллизии не будут подбирать специально.)
Если поставить задачу так, что надо обязательно уменьшить количество коллизий, то, очевидно, что нужно увеличивать размер выходного хеша. Как именно - вариантов море: начиная от конкатенации результатов двух хеш функций и заканчивая функцией gzencode() (шанс коллизии 0%, но хеш большоой
).P.S. Задача индексирования паблик торрент-трекеров не реальная, вообще никаких вариантов. Если вы гугль или рапидшара то можно подумать. Локальную сеть индексировать не проблема, но к чему тогда разговор про хеши, там файлов на много порядков меньше того значиния когда пора думать.
Я бы лучше начал решение вопроса с другой стороны: как заставить держателей файлов посчитать хеш по вашему алгоритму? Если не получится, то, может, составлять хеш из частей файла, т.е. скачивать куски выборочно (тем более что, вроде, торрент-клиенты считают хеши кусков), возможно удалось бы использовать какую-то паблик-информацию.
