Всем доброго времени суток!
Кто-нибудь знает метод хэширования без коллизий? Будет использоваться чисто в декоративных целях(на основе id), поэтому устойчивость к взлому необязательна.

md5
у него есть коллизии?

Почему бы тогда просто не генерировать строки в криптографическом порядке?

Нет, не знает и никогда не узнает


есть
А что?

Вообще, есть много способов получать уникальные строчки с буковок, помимо подсчета хэша...

Подскажите какие

Ну, например:
1, 2, 3, 4,... и так до бесконечности, и никогда не повторяются.
А запись числа — понятие относительное. Вспомните 16-ричную систему счисления. Строка "F4D4C654DE5" обозначает десятичное число 16824668605925. Достаточно каждый раз прибавлять +1 (или +2, или +10, или +100, но всегда одинаково) и строки никогда не повторятся. Нужно только проводить сложение не в десятичной, а 16-ричной системе.
При этом можно пользоваться k-ичной системой счисления со сколь угодно большим k, на которое хватит символов. Например, 36-ричной, если взять все цифры и английские буквы.

Второй пример:
Порождение комбинаторных объектов. На эту тему есть много материала, так как это раздел алгоритмизации, его преподают в университетах и т.п. Например, http://www.codenet.ru/progr/other/prbook/gl2.php
Можно, например, генерировать все возможные перестановки в какой-то строке, где нет одинаковых символов. Например, в "qwertyuiopasdfghjkl". При этом, чтобы создать следующее значение, достаточно знать только предыдущее.
Если в строке нет одинаковых символов, то все перестановки уникальны. Для строки в 19 символов их 121645100408832000 штук (надолго хватит...). Ну если начинать сразу с "qwertyuiopasdfghjkl", то остается чуть поменьше. (Первая строка — с символами в алфавитном порядке).
Поскольку мы получаем их последовательно, то никогда не получим уже полученного ранее значения.

Это сообщение отредактировал(а) Arantir - 1.6.2013, 01:32

как всё страшно) Спасибо!

и какие?

чисто интересно. а то пользуюсь и не догадываюсь, может мне нервничать надо?

Возьмем множество входов N = {0, ... n} и множество выходов N` = {H(0), ..., H(n)}, где H - хеш-функция. Допустим что хеш-функция на множестве входов N представляет собой однозначную подстановку из N в N`, т.е. любому входу из множества N будет однозначно соответствовать выход из множества N`. Теперь возьмем значение хеш-функции от n+1. Так как множество выходов хеш-функции ограничено множеством N`, на входе n+1 хеш-функция даст выход из множества N`.

Таким образом абсолютно любая хеш-функция на множестве входов > множества выходов будет иметь коллизии, т.е. два значения n и m, для которых H(n) == H(m)

Это сообщение отредактировал(а) cutwater - 2.6.2013, 00:08

Пример коллизии


Вообще насколько я понимаю, безколлизионных хэш функций быть не может.

Это сообщение отредактировал(а) krundetz - 3.6.2013, 09:48

пффф, ну ясен пень. если бы не было коллизий, то это было бы шифрование. при желании, даже обратимое

а как иначе оно может быть, если у нас на выходе 

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