Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
gunslinger17
0 / 0 / 0
Регистрация: 25.02.2012
Сообщений: 80
#1

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

05.11.2012, 18:10. Просмотров 1072. Ответов 13
Метки нет (Все метки)

Допустим, имеется некая хеш функция f(n)=n и необходимо оценить её качество.
Я понимаю, что нужно провести анализ на предмет возникновения коллизий. Но как это сделать программно, не представляю.
Вообще, с познаниями по части хеша имеются проблемы и был бы рад, если бы кто-нибудь просветил)
Заранее благодарю за помощь.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.11.2012, 18:10
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Оценка хеш-функции (C++):

хеш функции - C++
здраствуйте! собственно проблема в хеш функциях. не могу разобратся в принципе (гугль и книги читал). сам принцип хеширования понятен, а...

Вычисление хеш-функции - C++
Нужна помощь в реализации хеш-функции. Для алгоритма Эль-гамаля ( режим подписи ) необходимо вычислить хеш-функцию, но я не знаю как. ...

Неправильная работа хеш-функции - C++
Прежде чем начать не нужно сразу кидаться тапками и и.т.д я уже парюсь над этой задачей несколько дней так как не могу. Я читал несколько...

Хеш-функции. Метод открытого хеширования - C++
Написать программу, которая реализует метод открытого хеширования и хеш-функцией, основанной на методе деления со остатком. Если можно, то...

Ошибка в реализации хеш-функции SHA1 - C++
Здравствуйте, Решил написать простую реализацию, но результат вычислений оставляет желать лучшего Подскажите, пожалуйста, какой нюанс я...

Построение таблиц идентификаторов (хеш-функции, рехеширование) - C++
построить таблицу идентификаторов методом хэш-функции, использование метода рехеширования.

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

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

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

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

Не по теме:

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



Добавлено через 10 минут
Цитата Сообщение от Thinker Посмотреть сообщение
77Bender77,а хэш-функция от слова "abcdefg" чему будет равна?
надеюсь, что не просто сумма кодов, так как это уже не хэш-функция будет
0
05.11.2012, 19:18
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.11.2012, 19:18
Привет! Вот еще темы с ответами:

Список учеников имеет следующую структуру: фамилия – класс - оценка по алгебре - оценка по физике - средний балл - C++
Задание такое Список учеников имеет следующую структуру: фамилия – класс - оценка по алгебре - оценка по физике - средний балл. При...

Хеш-таблица - C++
В спортивных соревнованиях участвуют n команд. В файле SPORT содержатся прогнозы результатов соревнований. Каждый прогноз включает номер...

Хеш-таблица - C++
Почитав теорию найденную в поисковике, не особо понял как реализовать их на с++,может быть есть у кого-то есть время что бы объяснить на...

хеш-таблица - C++
как в хеш таблице на си/си++ мне указать таблицу сегментов?(массив содержащий коды) typedef struct spis { int val; spis...


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

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Опции темы

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