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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Добавлено через 52 секунды
Цитата Сообщение от gunslinger17 Посмотреть сообщение
Применимо к данной функции, получается так: хеш от числа 7 будет равен 7 и данная функция считается эффективной, т.к. коллизий (читай повторений) не будет вообще? Ведь числа все разные. Я правильно понял?
нет, это не хэш-функция
gunslinger17
0 / 0 / 0
Регистрация: 25.02.2012
Сообщений: 80
05.11.2012, 18:42  [ТС]     Оценка хеш-функции #7
Цитата Сообщение от Thinker Посмотреть сообщение
нет, это не хэш-функция
уж извиняйте... какое задание дадено, такое и решаю)
77Bender77
18 / 18 / 0
Регистрация: 16.12.2010
Сообщений: 145
05.11.2012, 18:44     Оценка хеш-функции #8
Цитата Сообщение от gunslinger17 Посмотреть сообщение
Применимо к данной функции, получается так: хеш от числа 7 будет равен 7 и данная функция считается эффективной, т.к. коллизий (читай повторений) не будет вообще? Ведь числа все разные. Я правильно понял?
нет, число 7 - это не идентификатор. идентификатор - это имя, оно состоит обязательно из букв + могут быть из цифр, никак не наоборот.
у каждого символа (цифры, буквы, знака пунктуации и тд) есть свой код
из этих кодов и получается сумма символов идентификатора
gunslinger17
0 / 0 / 0
Регистрация: 25.02.2012
Сообщений: 80
05.11.2012, 18:50  [ТС]     Оценка хеш-функции #9
Цитата Сообщение от 77Bender77 Посмотреть сообщение
нет, число 7 - это не идентификатор. идентификатор - это имя, оно состоит обязательно из букв + могут быть из цифр, никак не наоборот.
у каждого символа (цифры, буквы, знака пунктуации и тд) есть свой код
из этих кодов и получается сумма символов идентификатора
Тогда f(идентификатор)=код в таблице, к примеру, f(a)=97 (согласно таблице по ссылке)? Так?
77Bender77
18 / 18 / 0
Регистрация: 16.12.2010
Сообщений: 145
05.11.2012, 18:57     Оценка хеш-функции #10
Цитата Сообщение от gunslinger17 Посмотреть сообщение
Тогда f(идентификатор)=код в таблице, к примеру, f(a)=97 (согласно таблице по ссылке)? Так?
да, если а - латинская =)
gunslinger17
0 / 0 / 0
Регистрация: 25.02.2012
Сообщений: 80
05.11.2012, 18:59  [ТС]     Оценка хеш-функции #11
Цитата Сообщение от 77Bender77 Посмотреть сообщение
да, если а - латинская =)
77Bender77, спасибо, хоть с этим стало понятно)
А как оценить надежность функции? Ну, допустим, в одной будет больше коллизий, в другой - меньше. И одна будет надежнее другой, но как их сравнить? По какому параметру? Или там, ввести какой-нибудь collision_counter и сравнивать друг с другом?
Thinker
Эксперт C++
4221 / 2195 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
05.11.2012, 19:01     Оценка хеш-функции #12
Цитата Сообщение от 77Bender77 Посмотреть сообщение
хэш-функция возвращает сумму букв идентификатора
надеюсь, что вы понимаете, что говорите об отдельно взятой хэш-функции, коих можно напридумывать очень много.
А хэш-функция от слова "abcdefg" чему будет равна?
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++
Как можно получить хеш строки на C++ с использованием только стандартных библиотек? Думал так: unsigned long long hash(char *str,size_t...

Хеш функция - C++
Всем добрый день! В общем, нужно подсчитать кол-во коллизий. За это отвечает функция size_t collisions_count(), но почему-то не...

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

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

хеш-таблицы - C++
Реализовать ассоциативный массив в виде хеш-таблицы с операциями добавления, поиска . Ключом массива должна быть строка, значением – целое...


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

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

Не по теме:

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



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

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