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

Рехэширование - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.80
ahamoth
 Аватар для ahamoth
0 / 0 / 0
Регистрация: 26.11.2010
Сообщений: 111
01.11.2012, 20:09     Рехэширование #1
Добрый вечер, поясните пожалуйста работу алгоритма простого рехэширования при помощи произведения на конкретном примере.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
01.11.2012, 20:15     Рехэширование #2
Обращение хеша не возможно просто потому, что при хешировании теряется часть информации: даже если пароль короче хеша, или длины равны, то всё равно потеряется как минимум информация о длине, а если пароль длиннее, то хешу не хватит бит на все биты пароля. Каждый бит хеша зависит от всего пароля, но хеш в целом не несёт ни какой информации о том, с какой из коллизий конкретно совпадает пароль. Или тебя интересует что то другое? Тогда поясни вопрос.
ahamoth
 Аватар для ahamoth
0 / 0 / 0
Регистрация: 26.11.2010
Сообщений: 111
01.11.2012, 21:32  [ТС]     Рехэширование #3
Мне поставлена задача реализовать Создание таблиц идентификаторов с разрешением коллизий с помощью рехэширования при помощи произведения. Я это понимаю примерно так: Есть текстовый файл со строками . Каждая строка - это идентификатор. Задача состоит в том чтобы считать из текстового файла в двумерный массив вычисляя индексы для каждого элемента при помощи рехэширования произведением. Я не понимаю как работает этот алгоритм.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
02.11.2012, 20:41     Рехэширование #4
Что ты понимаешь под словом "рехеширование"?
ExcellencE
20 / 20 / 2
Регистрация: 22.08.2011
Сообщений: 79
02.11.2012, 21:41     Рехэширование #5
http://www.structur.h1.ru/hash.htm здесь все прекрасно и подробно описано), вам нужно почитать "Разрешение коллизий при хешировании методом открытой адресации." а что значит рехеширование произведением - спросите у своего препода, что он имел ввиду, а то мы вам такого напридумываем
ahamoth
 Аватар для ahamoth
0 / 0 / 0
Регистрация: 26.11.2010
Сообщений: 111
11.11.2012, 22:14  [ТС]     Рехэширование #6
Объясните пожалуйста как тут разобраться. Я нашел в книжке Молчанова как делается рехэширование при помощи произведения.
Существуют и другие методы организации функций рехэширования ht(A),
основанные на квадратичных вычислениях или, например, на вычислении
произведения по формуле: hi(A) = (h(A)N*i) mod N'm, где N'm — ближайшее простое число, меньшее Nm. В целом рехэширование позволяет добиться неплохих результатов для
Nm — максимальное значение из области значений хэш-функции h.
Допустим у меня есть массив. Я определяю хэш функцию так: считаю из скольки сиволов состоит каждый элемент массива mod размерность.
1) Например у меня есть нулевой элемент массива. его длина 3 символа: 3 mod 16 = 3.
2) вычисляю индекс рехэшированием произведением : 3*16*0 mod 2 (максимальное значение из обл. определения =3, 2 -ближайшее к нему) = 0
Но если начать вычислять индексы следующих элементов массива, то все они равны 0!. Помогите разобраться?
Yandex
Объявления
11.11.2012, 22:14     Рехэширование
Ответ Создать тему
Опции темы

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