Форум программистов, компьютерный форум CyberForum.ru

Оценка хеш-функции - C++

Войти
Регистрация
Восстановить пароль
 
gunslinger17
 Аватар для gunslinger17
0 / 0 / 0
Регистрация: 25.02.2012
Сообщений: 80
05.11.2012, 18:10     Оценка хеш-функции #1
Допустим, имеется некая хеш функция f(n)=n и необходимо оценить её качество.
Я понимаю, что нужно провести анализ на предмет возникновения коллизий. Но как это сделать программно, не представляю.
Вообще, с познаниями по части хеша имеются проблемы и был бы рад, если бы кто-нибудь просветил)
Заранее благодарю за помощь.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Thinker
Эксперт C++
 Аватар для Thinker
4216 / 2190 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
05.11.2012, 18:26     Оценка хеш-функции #2
Цитата Сообщение от gunslinger17 Посмотреть сообщение
Допустим, имеется некая хеш функция f(n)=n и необходимо оценить её качество.
Я понимаю, что нужно провести анализ на предмет возникновения коллизий. Но как это сделать программно, не представляю.
Во-первых, функция f(n)=n не является хэш-функцией,
во-вторых, программно хорошую хэш-функцию проверить невозможно, только теоретически
gunslinger17
 Аватар для gunslinger17
0 / 0 / 0
Регистрация: 25.02.2012
Сообщений: 80
05.11.2012, 18:29  [ТС]     Оценка хеш-функции #3
Цитата Сообщение от Thinker Посмотреть сообщение
Во-первых, функция f(n)=n не является хэш-функцией,
во-вторых, программно хорошую хэш-функцию проверить невозможно, только теоретически
Эм... У меня просто задание такое в лабораторной) Уж не знаю, что там возможно, а что нет)
77Bender77
 Аватар для 77Bender77
18 / 18 / 0
Регистрация: 16.12.2010
Сообщений: 145
05.11.2012, 18:30     Оценка хеш-функции #4
хэш-функция возвращает сумму букв идентификатора (может и не всех, смотря какая функция). она получает какой-то идентификатор, считает, например, сумму всех его букв, потом эту сумму (число) сравнивает с суммами других (уникальных по имени) идентификаторов. если ей встречаются такие же числа (тоесть коллизии присутствуют), то хэш-функция не очень эффективна

тоесть программно ты должен получать число из хэш-функции и сравнивать его с другими числами. есть коллизии - плохо, нет - хорошо
gunslinger17
 Аватар для gunslinger17
0 / 0 / 0
Регистрация: 25.02.2012
Сообщений: 80
05.11.2012, 18:34  [ТС]     Оценка хеш-функции #5
Цитата Сообщение от 77Bender77 Посмотреть сообщение
хэш-функция возвращает сумму букв идентификатора (может и не всех, смотря какая функция). она получает какой-то идентификатор, считает, например, сумму всех его букв, потом эту сумму (число) сравнивает с суммами других (уникальных по имени) идентификаторов. если ей встречаются такие же числа (тоесть коллизии присутствуют), то хэш-функция не очень эффективна

тоесть программно ты должен получать число из хэш-функции и сравнивать его с другими числами. есть коллизии - плохо, нет - хорошо
Применимо к данной функции, получается так: хеш от числа 7 будет равен 7 и данная функция считается эффективной, т.к. коллизий (читай повторений) не будет вообще? Ведь числа все разные. Я правильно понял?
Thinker
Эксперт C++
 Аватар для Thinker
4216 / 2190 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
05.11.2012, 18:36     Оценка хеш-функции #6
Цитата Сообщение от gunslinger17 Посмотреть сообщение
Эм... У меня просто задание такое в лабораторной) Уж не знаю, что там возможно, а что нет)
значит задание связана с реализацией хэш-функций с маленькими длинами сверток, в этом случае коллизии еще как-то можно обнаружить, подойдет тот же парадокс дней рождений

Добавлено через 52 секунды
Цитата Сообщение от gunslinger17 Посмотреть сообщение
Применимо к данной функции, получается так: хеш от числа 7 будет равен 7 и данная функция считается эффективной, т.к. коллизий (читай повторений) не будет вообще? Ведь числа все разные. Я правильно понял?
нет, это не хэш-функция
gunslinger17
 Аватар для gunslinger17
0 / 0 / 0
Регистрация: 25.02.2012
Сообщений: 80
05.11.2012, 18:42  [ТС]     Оценка хеш-функции #7
Цитата Сообщение от Thinker Посмотреть сообщение
нет, это не хэш-функция
уж извиняйте... какое задание дадено, такое и решаю)
77Bender77
 Аватар для 77Bender77
18 / 18 / 0
Регистрация: 16.12.2010
Сообщений: 145
05.11.2012, 18:44     Оценка хеш-функции #8
Цитата Сообщение от gunslinger17 Посмотреть сообщение
Применимо к данной функции, получается так: хеш от числа 7 будет равен 7 и данная функция считается эффективной, т.к. коллизий (читай повторений) не будет вообще? Ведь числа все разные. Я правильно понял?
нет, число 7 - это не идентификатор. идентификатор - это имя, оно состоит обязательно из букв + могут быть из цифр, никак не наоборот.
у каждого символа (цифры, буквы, знака пунктуации и тд) есть свой код
из этих кодов и получается сумма символов идентификатора
gunslinger17
 Аватар для gunslinger17
0 / 0 / 0
Регистрация: 25.02.2012
Сообщений: 80
05.11.2012, 18:50  [ТС]     Оценка хеш-функции #9
Цитата Сообщение от 77Bender77 Посмотреть сообщение
нет, число 7 - это не идентификатор. идентификатор - это имя, оно состоит обязательно из букв + могут быть из цифр, никак не наоборот.
у каждого символа (цифры, буквы, знака пунктуации и тд) есть свой код
из этих кодов и получается сумма символов идентификатора
Тогда f(идентификатор)=код в таблице, к примеру, f(a)=97 (согласно таблице по ссылке)? Так?
77Bender77
 Аватар для 77Bender77
18 / 18 / 0
Регистрация: 16.12.2010
Сообщений: 145
05.11.2012, 18:57     Оценка хеш-функции #10
Цитата Сообщение от gunslinger17 Посмотреть сообщение
Тогда f(идентификатор)=код в таблице, к примеру, f(a)=97 (согласно таблице по ссылке)? Так?
да, если а - латинская =)
gunslinger17
 Аватар для gunslinger17
0 / 0 / 0
Регистрация: 25.02.2012
Сообщений: 80
05.11.2012, 18:59  [ТС]     Оценка хеш-функции #11
Цитата Сообщение от 77Bender77 Посмотреть сообщение
да, если а - латинская =)
77Bender77, спасибо, хоть с этим стало понятно)
А как оценить надежность функции? Ну, допустим, в одной будет больше коллизий, в другой - меньше. И одна будет надежнее другой, но как их сравнить? По какому параметру? Или там, ввести какой-нибудь collision_counter и сравнивать друг с другом?
Thinker
Эксперт C++
 Аватар для Thinker
4216 / 2190 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
05.11.2012, 19:01     Оценка хеш-функции #12
Цитата Сообщение от 77Bender77 Посмотреть сообщение
хэш-функция возвращает сумму букв идентификатора
надеюсь, что вы понимаете, что говорите об отдельно взятой хэш-функции, коих можно напридумывать очень много.
А хэш-функция от слова "abcdefg" чему будет равна?
77Bender77
 Аватар для 77Bender77
18 / 18 / 0
Регистрация: 16.12.2010
Сообщений: 145
05.11.2012, 19:06     Оценка хеш-функции #13
Цитата Сообщение от gunslinger17 Посмотреть сообщение
А как оценить надежность функции? Ну, допустим, в одной будет больше коллизий, в другой - меньше. И одна будет надежнее другой, но как их сравнить? По какому параметру?
сравнить только практически, на одних и тех же примерах, и исходя из этого уже делать выводы. но нужно понимать, что теоретически может получиться совсем другой результат.
Или там, ввести какой-нибудь collision_counter и сравнивать друг с другом?
да, можно и так
надеюсь, что вы понимаете, что говорите об отдельно взятой хэш-функции, коих можно напридумывать очень много.
конечно, я в самом первом своем посте об этом сказал
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.11.2012, 19:18     Оценка хеш-функции
Еще ссылки по теме:

Хеш функция C++
Ошибка в реализации хеш-функции SHA1 C++
C++ Неправильная работа хеш-функции
Хеш-таблица C++
C++ Вычисление хеш-функции

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Thinker
Эксперт C++
 Аватар для Thinker
4216 / 2190 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
05.11.2012, 19:18     Оценка хеш-функции #14
Цитата Сообщение от 77Bender77 Посмотреть сообщение
конечно, я в самом первом своем посте об этом сказал

Не по теме:

тогда хорошо)



Добавлено через 10 минут
Цитата Сообщение от Thinker Посмотреть сообщение
77Bender77,а хэш-функция от слова "abcdefg" чему будет равна?
надеюсь, что не просто сумма кодов, так как это уже не хэш-функция будет
Yandex
Объявления
05.11.2012, 19:18     Оценка хеш-функции
Ответ Создать тему
Опции темы

Текущее время: 22:13. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru