2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Можно ли избежать коллизий при хэшировании, используя salt?
Сообщение12.03.2011, 00:24 
Аватара пользователя


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

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

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

 Профиль  
                  
 
 
Сообщение12.03.2011, 00:34 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Можно ли избежать коллизий при хэшировании, используя salt?
Сообщение12.03.2011, 00:42 
Аватара пользователя


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

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

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

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

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

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

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

 Профиль  
                  
 
 Re: Можно ли избежать коллизий при хэшировании, используя salt?
Сообщение12.03.2011, 02:30 
Заслуженный участник


04/05/09
4582
mclaudt в сообщении #421976 писал(а):
невозможно из-за необратимости функции хэширования
А откуда взялась необратимость?

 Профиль  
                  
 
 Re: Можно ли избежать коллизий при хэшировании, используя salt?
Сообщение12.03.2011, 02:53 
Аватара пользователя


14/01/10
252
venco в сообщении #421993 писал(а):
А откуда взялась необратимость?


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

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

 Профиль  
                  
 
 
Сообщение12.03.2011, 18:46 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 
Сообщение12.03.2011, 18:55 
Аватара пользователя


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group