Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Общие вопросы по программированию, компьютерный форум
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 10.05.2011, 12:13   #1
vedro-compota
любитель-далеко не
Участник клуба
 
Аватар для vedro-compota
 
Регистрация: 13.04.2010
Сообщений: 1,156
По умолчанию Идея хеширования и хэш-таблиц - уточнения.

Здравствуйте, уважаемые программисты!

Мне нужно было создать коллекцию на основе алгоритма хеширования и в процессе осмысления последней, я пришёл к выводу, что не совсем понимаю принципиальное отличие хеширования от обычного поиска.
Итак, поясню в чем непонятка - В общем случае "от некого элемента Э можно вычислить некоторую функцию, которая укажет его адрес в таблице" (это из Дональда Кнута.) - то есть элемент будет или обнаружен или в этой таблице размещен.
1) ведь в этом же и есть основная идея всех алгоритмов хеширования,да?
2) Получается, что при таком подходе к поиску мы рассматриваем само обнаружение элемента по индексу (условимся для понятности, что наша таблица - это массив) как нечто моментальное или, по крайней мере, нас не интересующее. это так?
3) но если мы всё же будем рассматривать механизм получения элемента по индексу, то придём к выводу, что это именно поиск....-то есть мы именно переходим к нужному элементу путём обнаружения нужного индекса (разве что индексы всегда упорядочены). правильно ли это?
4) На практике самое сложное (после создания самой хеш-функции) - реализация извлечения элемента по его индексу, который с помощтю хеш-функции получен (в случае, если обычный миассив использовать нельзя).
-------------
и вообще - почему-то в многочисленных примерах очень мало уделено внимания именно получению области памяти, на которую указывает полученный хэш-код.....
(если всё сильно запущено - и отвечать на это сложно просто киньте ссылки - почитать и разобраться.)

Заранее благодарю!)
против абортов=за + жизнь;.фкн вгу;_______________________мойблг

Последний раз редактировалось vedro-compota; 10.05.2011 в 12:18.
vedro-compota вне форума Ответить с цитированием
Старый 10.05.2011, 12:57   #2
rpy3uH
добрый няша
Старожил
 
Аватар для rpy3uH
 
Регистрация: 29.10.2006
Сообщений: 4,804
По умолчанию

Цитата:
Сообщение от vedro-compota Посмотреть сообщение
Итак, поясню в чем непонятка - В общем случае "от некого элемента Э можно вычислить некоторую функцию, которая укажет его адрес в таблице" (это из Дональда Кнута.) - то есть элемент будет или обнаружен или в этой таблице размещен.
1) ведь в этом же и есть основная идея всех алгоритмов хеширования,да?
в целом да.

Цитата:
Сообщение от vedro-compota Посмотреть сообщение
2) Получается, что при таком подходе к поиску мы рассматриваем само обнаружение элемента по индексу (условимся для понятности, что наша таблица - это массив) как нечто моментальное
в этом и основная проблема, расмерность хэша очень большая чтобы поиск по нему был моментальным. например MD5 хэш имеет размер 128 бит, если сам хэш будет индексом, то это какой же размерности будет массив?

Цитата:
Сообщение от vedro-compota Посмотреть сообщение
3) но если мы всё же будем рассматривать механизм получения элемента по индексу, то придём к выводу, что это именно поиск....-то есть мы именно переходим к нужному элементу путём обнаружения нужного индекса (разве что индексы всегда упорядочены). правильно ли это?
фактически всё к этому и сводится, в итоге надо все равно пройтись по массиву/таблице в поисках нужного хэша. В этом случае выигрыш будет только в том случае если сравнение хэша быстрее, чем сравнение самих данных ассоциированных с хешем.
Например, имеется массив строк в каждом по 20-50 символов (например, ФИО) есть их массив из 1000 таких строк, поиск по нему очень долгая операция, но если мы заведём дополнительное поле содержащее хэш строки размером например 128 бит или 16 символов (байт) то поиск по хэшу будет быстрее, в начале мы получаем хэш искомой строки и пробегаем по массиву сравнивая только поле с хэшем. При этом чем меньше размерность хэша тем быстрее поиск. В случае если элементов в массиве менее миллиона, то вполне может подойти хэш размерностью 24-32 бита. (хотя такой хэш уже не хэш, его можно просто назвать контрольной суммой, но не в этом суть)

В "прицепе" находятся исходники моей лабы по хэшированию которую я делал на первом курсе универа (поиск по большому списку с "е-мэйлами", е-мэйлы в файлике "test"), хэш использовал размерностью 32 бита, хэширующую функцию придумал за 5 минут.


Цитата:
Сообщение от vedro-compota Посмотреть сообщение
4) На практике самое сложное (после создания самой хеш-функции) - реализация извлечения элемента по его индексу, который с помощтю хеш-функции получен (в случае, если обычный миассив использовать нельзя).
если хэш имеет большую размерность, лазить по всему массиву/базе/таблице тоже становится не очень быстро. В случае если с хэшем ассоциирован текст или картинка, то у хэша есть одно очень большое преимущество : его можно сравнивать, т.е. если у нас имеется два хеша, то всегда можно их сравнить и сказать что один больше или выше другого. Базу/массив/таблицу в таком случае надо сортировать по хэшу. В этом случае при поиске мы сначале получаем хэш того что ищем, тыкаем примерно в середину и смотрим хэш, если он больше чем тот который мы ищем, значит искомый элемент находится в первой половине и т.д. и т.п., в общем получается бинарный поиск.

В общем, вот такие пироги ....
Вложения
Тип файла: zip HASH_LAB.zip (8.90 Мб, 16 просмотров)

Последний раз редактировалось rpy3uH; 10.05.2011 в 13:12.
rpy3uH вне форума Ответить с цитированием
Старый 10.05.2011, 13:21   #3
Utkin
Старожил
 
Аватар для Utkin
 
Регистрация: 04.02.2009
Сообщений: 18,136
По умолчанию

1) Не только. Хеши удобны и для ряда случаев. Например, вместо того, чтобы оперировать какими-либо данными (строками, рисунками, мп3шками, фильмами и пр.) проще пользоваться их хешами, которые в сравнении с самими данными имеют очень малый размер. Самый простой пример - замечали как происходит перемещение файлов из папки в папку в рамках одного диска? Такое перемещение всегда быстро и практически не зависит от размера файлов, потому что физически файлы остаются на своих местах...
То есть главное не только организация хеша. Важно именно его применение.
Маньяк-самоучка
Utkin появился в результате деления на нуль.
Осторожно! Альтернативная логика
Utkin вне форума Ответить с цитированием
Старый 11.05.2011, 19:25   #4
vedro-compota
любитель-далеко не
Участник клуба
 
Аватар для vedro-compota
 
Регистрация: 13.04.2010
Сообщений: 1,156
По умолчанию

Цитата:
В общем, вот такие пироги ....
весьма понятно) спасибо , rpy3uH)
Цитата:
- замечали как происходит перемещение файлов из папки в папку в рамках одного диска?
Utkin,там вроде как что-то вроде указателей меняется)
против абортов=за + жизнь;.фкн вгу;_______________________мойблг
vedro-compota вне форума Ответить с цитированием
Старый 11.05.2011, 21:09   #5
Utkin
Старожил
 
Аватар для Utkin
 
Регистрация: 04.02.2009
Сообщений: 18,136
По умолчанию

Что есть результат хеш-функции? Указатель
Цитата:
"от некого элемента Э можно вычислить некоторую функцию, которая укажет его адрес в таблице"
Соль одна и та же.
Маньяк-самоучка
Utkin появился в результате деления на нуль.
Осторожно! Альтернативная логика
Utkin вне форума Ответить с цитированием
Старый 12.05.2011, 09:37   #6
rpy3uH
добрый няша
Старожил
 
Аватар для rpy3uH
 
Регистрация: 29.10.2006
Сообщений: 4,804
По умолчанию

Цитата:
Сообщение от Utkin Посмотреть сообщение
Что есть результат хеш-функции? Указатель
SHA1 или MD5 хеш это указатель? хеш это некоторая контрольная сумма которая позволяет высокой вероятностью отличить одни данные от других, не сравнивания при этом сами данные. Чем больше битность хеша тем больше вероятность
rpy3uH вне форума Ответить с цитированием
Старый 12.05.2011, 09:43   #7
vedro-compota
любитель-далеко не
Участник клуба
 
Аватар для vedro-compota
 
Регистрация: 13.04.2010
Сообщений: 1,156
По умолчанию

Цитата:
хеш это некоторая контрольная сумма которая позволяет высокой вероятностью отличить одни данные от других, не сравнивания при этом сами данные.
ну Utkin имел ввиду указатель в общем смысле) что-то ассоциированное с чем-то)
против абортов=за + жизнь;.фкн вгу;_______________________мойблг
vedro-compota вне форума Ответить с цитированием
Старый 12.05.2011, 12:32   #8
Utkin
Старожил
 
Аватар для Utkin
 
Регистрация: 04.02.2009
Сообщений: 18,136
По умолчанию

Контрольные суммы и криптография это только одна из областей применения хешей. По сути да МД5 при оперировании с несколькими суммами однозначно указывает на уникальные данные. Если хотите это идентификатор некоторых данных.
Маньяк-самоучка
Utkin появился в результате деления на нуль.
Осторожно! Альтернативная логика

Последний раз редактировалось Utkin; 12.05.2011 в 12:44.
Utkin вне форума Ответить с цитированием
Старый 12.05.2011, 21:19   #9
vedro-compota
любитель-далеко не
Участник клуба
 
Аватар для vedro-compota
 
Регистрация: 13.04.2010
Сообщений: 1,156
По умолчанию

Цитата:
Если хотите это идентификатор некоторых данных.
да. именно это я и хотел сказать)
Цитата:
указатель в общем смысле)
Utkin+1)
против абортов=за + жизнь;.фкн вгу;_______________________мойблг
vedro-compota вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Пример Хеширования gs.Soroka Помощь студентам 0 04.04.2011 23:25
Реализация ХЭШ таблиц на С++... Romksuper Помощь студентам 4 01.03.2011 00:57
хэш-функция N-хэш Temka Общие вопросы Delphi 1 29.11.2010 21:11
MD5 хеширования ZET78 Общие вопросы C/C++ 2 06.07.2010 23:33
Уточнения по ассемблеру. max-tasm Assembler - Ассемблер (FASM, MASM, WASM, NASM, GoASM, Gas, RosAsm, HLA) и не рекомендуем TASM 2 17.05.2010 17:43