2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

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

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

 
 
 
 Re: Можно ли избежать коллизий при хэшировании, используя salt?
Сообщение12.03.2011, 00:42 
Аватара пользователя
Привести ещё одного не получится, у нас строк всего 64 - это условие задачи. Т.е. изначально при плохой функции есть незадействованные значения, а есть задействованные несколько раз.

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

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

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

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

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

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

 
 
 
 Re: Можно ли избежать коллизий при хэшировании, используя salt?
Сообщение12.03.2011, 02:30 
mclaudt в сообщении #421976 писал(а):
невозможно из-за необратимости функции хэширования
А откуда взялась необратимость?

 
 
 
 Re: Можно ли избежать коллизий при хэшировании, используя salt?
Сообщение12.03.2011, 02:53 
Аватара пользователя
venco в сообщении #421993 писал(а):
А откуда взялась необратимость?


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

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

 
 
 
 
Сообщение12.03.2011, 18:46 
Аватара пользователя
mclaudt в сообщении #421976 писал(а):
Допустим, что речь идет о соли, которая как-то специально зависит от исходного множества строк.
Почему бы тогда такой "соли" не отсортировать всё множество строк и не поставить в соответствие каждой строке её индекс в отсортированном списке? Проблема в том, что нужно продолжить хэш-функцию на множество всех строк?

 
 
 
 
Сообщение12.03.2011, 18:55 
Аватара пользователя
Ну да, фактически перенумеровать строки. Можно конечно. Этим примером мне хотелось качественно понять механику зависимости количества коллизий.

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group