|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
10.05.2011, 12:13 | #1 |
любитель-далеко не
Участник клуба
Регистрация: 13.04.2010
Сообщений: 1,156
|
Идея хеширования и хэш-таблиц - уточнения.
Здравствуйте, уважаемые программисты!
Мне нужно было создать коллекцию на основе алгоритма хеширования и в процессе осмысления последней, я пришёл к выводу, что не совсем понимаю принципиальное отличие хеширования от обычного поиска. Итак, поясню в чем непонятка - В общем случае "от некого элемента Э можно вычислить некоторую функцию, которая укажет его адрес в таблице" (это из Дональда Кнута.) - то есть элемент будет или обнаружен или в этой таблице размещен. 1) ведь в этом же и есть основная идея всех алгоритмов хеширования,да? 2) Получается, что при таком подходе к поиску мы рассматриваем само обнаружение элемента по индексу (условимся для понятности, что наша таблица - это массив) как нечто моментальное или, по крайней мере, нас не интересующее. это так? 3) но если мы всё же будем рассматривать механизм получения элемента по индексу, то придём к выводу, что это именно поиск....-то есть мы именно переходим к нужному элементу путём обнаружения нужного индекса (разве что индексы всегда упорядочены). правильно ли это? 4) На практике самое сложное (после создания самой хеш-функции) - реализация извлечения элемента по его индексу, который с помощтю хеш-функции получен (в случае, если обычный миассив использовать нельзя). ------------- и вообще - почему-то в многочисленных примерах очень мало уделено внимания именно получению области памяти, на которую указывает полученный хэш-код..... (если всё сильно запущено - и отвечать на это сложно просто киньте ссылки - почитать и разобраться.) Заранее благодарю!) Последний раз редактировалось vedro-compota; 10.05.2011 в 12:18. |
10.05.2011, 12:57 | #2 | ||||
добрый няша
Старожил
Регистрация: 29.10.2006
Сообщений: 4,804
|
Цитата:
Цитата:
Цитата:
Например, имеется массив строк в каждом по 20-50 символов (например, ФИО) есть их массив из 1000 таких строк, поиск по нему очень долгая операция, но если мы заведём дополнительное поле содержащее хэш строки размером например 128 бит или 16 символов (байт) то поиск по хэшу будет быстрее, в начале мы получаем хэш искомой строки и пробегаем по массиву сравнивая только поле с хэшем. При этом чем меньше размерность хэша тем быстрее поиск. В случае если элементов в массиве менее миллиона, то вполне может подойти хэш размерностью 24-32 бита. (хотя такой хэш уже не хэш, его можно просто назвать контрольной суммой, но не в этом суть) В "прицепе" находятся исходники моей лабы по хэшированию которую я делал на первом курсе универа (поиск по большому списку с "е-мэйлами", е-мэйлы в файлике "test"), хэш использовал размерностью 32 бита, хэширующую функцию придумал за 5 минут. Цитата:
В общем, вот такие пироги .... Последний раз редактировалось rpy3uH; 10.05.2011 в 13:12. |
||||
10.05.2011, 13:21 | #3 |
Старожил
Регистрация: 04.02.2009
Сообщений: 18,136
|
1) Не только. Хеши удобны и для ряда случаев. Например, вместо того, чтобы оперировать какими-либо данными (строками, рисунками, мп3шками, фильмами и пр.) проще пользоваться их хешами, которые в сравнении с самими данными имеют очень малый размер. Самый простой пример - замечали как происходит перемещение файлов из папки в папку в рамках одного диска? Такое перемещение всегда быстро и практически не зависит от размера файлов, потому что физически файлы остаются на своих местах...
То есть главное не только организация хеша. Важно именно его применение.
Маньяк-самоучка
Utkin появился в результате деления на нуль. Осторожно! Альтернативная логика |
11.05.2011, 19:25 | #4 | ||
любитель-далеко не
Участник клуба
Регистрация: 13.04.2010
Сообщений: 1,156
|
Цитата:
Цитата:
|
||
11.05.2011, 21:09 | #5 | |
Старожил
Регистрация: 04.02.2009
Сообщений: 18,136
|
Что есть результат хеш-функции? Указатель
Цитата:
Маньяк-самоучка
Utkin появился в результате деления на нуль. Осторожно! Альтернативная логика |
|
12.05.2011, 09:37 | #6 |
добрый няша
Старожил
Регистрация: 29.10.2006
Сообщений: 4,804
|
SHA1 или MD5 хеш это указатель? хеш это некоторая контрольная сумма которая позволяет высокой вероятностью отличить одни данные от других, не сравнивания при этом сами данные. Чем больше битность хеша тем больше вероятность
|
12.05.2011, 09:43 | #7 | |
любитель-далеко не
Участник клуба
Регистрация: 13.04.2010
Сообщений: 1,156
|
Цитата:
|
|
12.05.2011, 12:32 | #8 |
Старожил
Регистрация: 04.02.2009
Сообщений: 18,136
|
Контрольные суммы и криптография это только одна из областей применения хешей. По сути да МД5 при оперировании с несколькими суммами однозначно указывает на уникальные данные. Если хотите это идентификатор некоторых данных.
Маньяк-самоучка
Utkin появился в результате деления на нуль. Осторожно! Альтернативная логика Последний раз редактировалось Utkin; 12.05.2011 в 12:44. |
Опции темы | Поиск в этой теме |
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Пример Хеширования | 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 |