Можно ли избежать коллизий при хэшировании, используя salt?

[mclaudt]

Допустим, есть 64 коротких строки и есть хэш-функция на множество 0-63, дающая коллизии. Нельзя ли добавить по ведру какой-то особой "соли" к исходным строкам (или к алгоритму), чтобы коллизии исчезли и все значения ровнехонько и однозначно уложились в интервал 0-63? Или же присутствие коллизий определяется только отношением мер множества значений хэш-функции и множества исходных элементов?

Может, кто шарит в теме - ответит утвердительно или же вкратце расскажет, почему такое в принципе не возможно.

Я не спец в этой области, просто для себя интересуюсь. Спасибо за внимание.

[ИСН]

Разумеется, соотношение мер. Допустим, Вы как-то подобрали такую соль, чтобы все кролики расселись по разным клеткам. И тут приводят ещё одного. Конец!

[mclaudt]

Привести ещё одного не получится, у нас строк всего 64 - это условие задачи. Т.е. изначально при плохой функции есть незадействованные значения, а есть задействованные несколько раз.

Допустим, что речь идет о соли, которая как-то специально зависит от исходного множества строк.

-- Сб мар 12, 2011 00:48:04 --

Т.е. можно ли изменениями алгоритма и специальным удлинением строк как-то вычесать колтуны коллизий в ровную однозначную гребенку? Или их присутствие неизбежно и определяется только отношением длины гребня и объема волос?

Да простят меня строгие аксиоматики за такое сравнение.

-- Сб мар 12, 2011 00:55:08 --

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

[venco]

mclaudt в сообщении #421976 писал(а):

невозможно из-за необратимости функции хэширования

А откуда взялась необратимость?

[mclaudt]

venco в сообщении #421993 писал(а):

А откуда взялась необратимость?

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

Действительно, тут, пожалуй, необратимость лишняя. Тогда неприменимость отменяется.

[worm2]

mclaudt в сообщении #421976 писал(а):

Допустим, что речь идет о соли, которая как-то специально зависит от исходного множества строк.

Почему бы тогда такой "соли" не отсортировать всё множество строк и не поставить в соответствие каждой строке её индекс в отсортированном списке? Проблема в том, что нужно продолжить хэш-функцию на множество всех строк?

[mclaudt]

Ну да, фактически перенумеровать строки. Можно конечно. Этим примером мне хотелось качественно понять механику зависимости количества коллизий.