хэш

[Mayor]

в текстах иногда встречаются слова типа : хеширование , хэш символ , хеш таблица , а я даже не могу понять к какому компьютерному разделу это относится .

Что это такое и зачем они нужны ?

[MOPO3]

Хммм...  думаю, что в некоторых случаях это можно отнести к разделу криптования (или криптографии  :?: )

[ysv_]

Если коротко, то суть в следующем: иногда встречаются задачи, когда нужно поставить соответствие между названием каким-то сложным объектом (например строкой символов) и другим объектом (неимеет значения сложный он или нет). В качестве примера возьмем растояния от например Киева до любого города Земли. Тогда каждому названию соответствует растояние. Когда нужно найти расстояние например от Нью-Йорка до Киева - делается поиск по таблице. Вот тут и возникают разные варианты ускорения этого дела. Например строят индекс по таблице. Но при этом остается еще одна длительная операция - в нашем случае сравнение двух строк. Для того чтобы обойти это сравнение вводят функцию, которая для любой строки возвращает некоторое число. Это и есть хеш-функция. И тогда вместо индекса по строках строят индекс по числах. Поиск получается быстрее.

[Mayor]

Спасибо вроде частично понял:)

[npak]

Кнут, первый том.

[Mayor]

Если понимаешь , что пишет Кнут то тогда его тебе незачем читать
Спасибо за ссылку , но я 3й том пытался освоить - невышло , хотя может 1й попроще ...

[npak]

Был неправ, том третий, поиск и сортировка

Хэширование имеет непосредственное отношение к поиску.  Простейший подход к поиску заключается в сравнении объекта, который надо найти, с имеющимися объектами.   Например, поиск некоторой строки в списке строк (словарь).

Во многих случаях сравнение двух объектов -- дорогостоящая операция (например, для строк).  Поэтому идут другим путём.  С каждым объектом связывают некоторое число, хэш код.  Алгоритм сравнения изменяется:
    сначала сравнивают хэш-коды объектов
    если коды различаются, значит объекты различаются
    если коды совпадают, то надо сравнивать по-честному.

Есть накладные расходы на вычисление хэш-кода, но благодаря тому, что числа сравниваются быстро, такая оптимизации может экономить массу времени при поиске в больших массивах информации.

Ещё одно применение хэширования -- построение отображений.  Например отображение "имя пользователя" -> список заказов.  В таком случае наивная реализация -- хранить в массиве пары <ключ, значение>.  Соответственно, поиск значения по ключу заключается в переборе пар и сравнении ключей.

Хэш-код используют как индекс в массиве пар.  При добавлении пары вычисляют хэш-код ключа и сохраняют пару <ключ, значение> в ячейке, соответствующей хэш-коду.  Есть опасность коллизии, то есть хэш-коды для разных объектов будут одинаковыми.  Предложены различные способы разрешения коллизий, не о них сейчас речь.  Предположим, что коллизий нет.  Тогда поиск значения по ключу заключается в том, что вычисляют хэш-код ключа (по которому ищут) и заглядывают в соответствующую ячейку.  Если она пуста, значит в таблице нет записи о данном ключе.  Иначе возвращают значение, хранящееся в ячейке.

[Mayor]

Ну , пока не дошло до отображений все понимал

Практического применения этому в программировании пока не вижу - гораздо эфективнее отсортировать и поискать , хотя случаи разные бывают , может где потом и пригодиться ... когда пойму вторую половину

Вот если бы это ээээ типа как его хеш функция с точностью до полиморфизма ? в смысле ввести функцию порядка на множестве хеша взаимнооднозначную с функцией порядка на множестве имен. блин , проще говоря, если бы были bool fName(sz t1 , sz t2 ) == bool fHash( h h1, h h2 ) где h1=fh(t1) , h2=fh(t2)  при любых t1,t2
В общем у меня бооольшие проблеммы с мат. частью

Кстати , что такое кортеж ?

[npak]

Mayor,
когда мне первый раз рассказали про хэш таблицы, я тоже решил, что это что-то ненужное.  И тот человек, который мне про хэширование рассказывал, тоже признался, что в начале не понимал надобности в хэш-таблицах.  Так что это дело наживное.

[RXL]

Практического применения этому в программировании пока не вижу - гораздо эфективнее отсортировать и поискать , хотя случаи разные бывают , может где потом и пригодиться ... когда пойму вторую половину

Когда важна скорость поиска в большом числе объектов, то без этого не обойтись.
Или такой пример: для анализа логов у меня написано более 200 разных регулярных выражений. Поступила новая строка и мне нужно выбрать одно выражение, или несколько, но не никак не все - это будет работать слишком долго. Решение просто: использую первый символ строки как ключ, а выражения, начинающиеся с одного и того же символа объеденяю в список. В результате простейшего хеширования, для каждой строки вместо, всреднем, 100 выражений, используется единицы.

[Mayor]

RXL,  , ты меня совсем запутал : какой лог ? какие выражения ? какая строка ? , я ничего не понимаю

[Finch]

Mayor, Приставь ситуацию. Ты делаешь программу словарь англо-русский. Пользователь вводит слово. программа должна дать перевод этого слова. Есть два пути.
1. Просмотреть весь словарь. (ну это очень долго).
2. Просмотреть только ту область где первая буква такая же, как у твоего слова. Потом вторая буква и.т.д. (это согласись гораздо быстрее).

[npak]

Mayor, лог -- это последовательность строк, которые некоторая программа (или программы) сбросили в ходе работы.

Что такое регулярное выражение -- это отдельный и очень большой вопрос.  Можешь считать, что это некоторый шаблон, и есть операция, которая определяет, соответствует строка шаблону или нет.

RXL, похоже, решает задачу выбрать из лога (некоторого набора строк) только те строки, которые соответствуют по крайней мере одному  шаблону из числа заданных.  

Самое простое решение (наивное) это взять строку, затем применить шаблоны один за другим до тех пор, пока не будет найден подходящий или будут перебраны все шаблоны.  Если шаблонов 200, строк тысяч десять (нормальный небольшой лог   ), то получается надо произвести порядка миллиона сравнений.  Операция сравнения строки с шаблоном работает быстро, но не настолько

RXL сделал оптимизацию.  В качестве хэш-кода для шаблонов он  выбрал первый символ в шаблоне.  Сохранил в таблице отображение символ -> множество шаблонов, начинающихся с данного символа.

Оптимизированная процедура работы со строками:
 - По первому символу строки найти шаблоны, которые начинаются с данного символа (посмотреть в таблице)
 - По очереди сравнить найденные шаблоны со строкой.  

Если для каждого символа число шаблонов невелико, то получается значительное ускорение работы.

RXL, я правильно разъяснил суть работы?

RXL предложил красивое и эффективное решение.

[npak]

Mayor, Приставь ситуацию. Ты делаешь программу словарь англо-русский. Пользователь вводит слово. программа должна дать перевод этого слова. Есть два пути.
1. Просмотреть весь словарь. (ну это очень долго).
2. Просмотреть только ту область где первая буква такая же, как у твоего слова. Потом вторая буква и.т.д. (это согласись гораздо быстрее).

Пример не подходит.
Во-первых, можно так организовать словарь, что время поиска будет порядка lg2(n) (lg2 -- двоичный логарифм, n -- число записей в словаре).  Такой быстрый поиск гарантирует, например, сбалансированное двоичное дерево.  Для словаря мюллера (~ 70 000 записей) это даст глубину поиска 16-17.  То есть для поиска слова в словаре потребуется полтора десятка сравнений.  Это гораздо быстрее, чем последовательный просмотр словаря.

Во-вторых, предложенный метод поиска не имеет отношения к хэшированию.  В книге Ахо и Ульмана про алгоритмы этот метод был переведён на русский язык как "нагруженные деревья".  Возможно, в частном случае англо-русского словаря у этого метода есть преимущество в скорости работы и затратах памяти перед хэшированием.

Краткое описание применения хэширования к поиску слов в словарях.

При представление словарей хэш-таблицей задаётся хэш-функция для строк, назовём её h(sz str).  Пусть словарь представляется массивом размера N.  При помещении слова word в словарь вычисляется хэш-код слова hw = h(word) и слово (вместе со значением) кладётся в ячейку массива с номером hw%N (остаток от деления хэш-кода на размер массива).  В общем случае в одну ячейку может попасть несколько слов, в таком случае в ячейке хранится список слов.

При поиске слова word2 в словаре вычисляется его хэш-код hw2 = h(word2) и выбирается список слов из ячейки массива с номером hw2%N.  Дальше производится сравнение слова word2 со словами из выбранной ячейки.

Таким образом, перед хэш-функцией стоят такие задачи:
1.  Сделать так, чтобы слова равномерно распределились по ячейкам (то есть не было такого, что в одну ячейку попала половина слов, а в остальные по одному слову)
2. Обеспечить плотное заполнение таблицы, то есть чтобы было минимальное число ячеек, которые не хранят какое-либо слово
3.  Развести близкие слова по разным ячейкам.  Это делается для ускорения поиска внутри ячейки.  Если в неё попадут близкие слова (то есть слова с длинным общим префиксом), то для различения может потребоваться долгое сравнение.  Напротив, если в ячейку попадут далёкие друг от друга слова, то для различения будет достаточно сравнить 1-2 символа.

При хорошем выборе хэш-функции поиск в словаре потребует нескольких сравнений.

Хэш-таблицы работают не только для строк, но и для любых объектов, которые можно сравнивать.  Mayor, обрати внимание, что для построения и использования хэш-таблицы достаточно сравнения на равенство, сравнение больше-меньше не обязательно.  Хэш-таблица, вообще говоря, выигрывает в скорости у поиска в отсортированной структуре данных, так как для хорошо подобранных хэш-функции и размере таблицы число сравнений при поиске почти не зависит от размера таблицы (более-менее константа, хотя есть и исключения), в то время как самые лучшие алгоритмы поиска дают логарифмическую зависимость числа сравнений от размера таблицы.

Вот такое кратенькое введение в использование хэширования.

Специальные хэш функции используются также для защиты информации, но это совсем другая тема, нежели поиск в словаре.  Если интересно, могу рассказать.

[Finch]

npak,   :oops: Спасибо.  Разживал хотя и не до конца. Но как говорится в одном знаменитом фильме "Будем искать"

[RXL]

RXL, я правильно разъяснил суть работы?

Совершенно верно.

[Mayor]

когда мне первый раз рассказали про хэш таблицы, я тоже решил, что это что-то ненужное. И тот человек, который мне про хэширование рассказывал, тоже признался, что в начале не понимал надобности в хэш-таблицах. Так что это дело наживное.

 
Вы будете смеяться ,но в ближайшие пару дней мне придеться использовать хеширование и неважно понял я, что это такое или нет.
Ситуация такова: предстоит государственное аттестационное тестирование, вопросов с ответами наберется примерно на 1000 страниц и ни у кого нет желания их учить. Поэтому проноситься сотовый телефон, есстественно времени набирать на нем полностью каждый вопрос нет, придется в уме хешировать вопрос, чтобы в поле ввода оказалось 3-6 символов - теоретически для такого количесва вопросов это более чем достаточно, далее заранее написаный сервер отсылает обратно все вопросы и ответы с данным хеш кодом, единствено о чем следует позаботиться это легкость хеш функции и максимальная уникальность хеш кодов, чтобы MySQL на один из кодов не послал в ответе половины базы данных...



Для тех кто на бронепоезде - можно пример пары тройки регулярных выражений и логов ?

Как я понял в данной ситуации отношение порядка не ввести и поэтому был выбрано ускорение линейного алгоритма в N раз ...

Краткое описание применения хэширования к поиску слов в словарях.

 

Как называется этот алгоритм ( по автору или еще как, чтобы понимать когда о нем идет речь)?
Чертовки быстрый метод, памяти сожрет немерянно, неуниверсален, но скооорость !!!! WOOOW
Идея поиска быстрее, чем ln (N) мне даже не приходила в голову

Специальные хэш функции используются также для защиты информации, но это совсем другая тема, нежели поиск в словаре. Если интересно, могу рассказать.

 
Чертовски интересно, как и алгоритм построения сбалансированого дерева ( в упрор за 1.5 месяца не мог понять, как вставить новый элемент за время меньшее N*ln(N) ), жаль только из-за GPRS+MySQL+АХЗ  не смогу в этом разобраться в ближайшие несколько дней.

[RXL]

Mayor, лучше бы ты учил...

Используй сокращения - мозг, все таки, не компьютер. Далее просто: уникальное сокращение соответствует одному ответу. Можно и в БД залить.

Смотри только, чтобы тебе за изобретение пять не поставили...  

[npak]

RXL, пять чего? лет?  за мошенничество в особо крупных?  

Mayor, алгоритм так и называется -- хэш таблица, разрешение коллизии методом цепочек

Про применение хеширования к защите информации надеюсь сделать статью для сайта.

алгоритм построения сбалансированого дерева ( в упрор за 1.5 месяца не мог понять, как вставить новый элемент за время меньшее N*ln(N) )

Не понятно, что ты имеешь в виду про время вставки.

[RXL]

npak, ну ты, наверно, смотрел "Приключения Шурика" - вспомни экзамен.

[Mayor]

Используй сокращения - мозг, все таки, не компьютер. Далее просто: уникальное сокращение соответствует одному ответу. Можно и в БД залить.

 
Так и сделал, поиск удобнее всего оказался по первым буквам каждого слова, все было бы вообще зашибись если бы эти герои из Астрахани отсканировали, оба тома вопросов, а потом отредактировали их, дак нет они додумались первые несколько слов каждого вопроса вручную вводить -это из 4253 то  8-0 , потом нарезали по 3 буквы каждого слова в алфавитном порядке отсортировали и на шпоры распечатали: получилось 7 страниц формата А4 - 5 шрифтом .

По нескольким полям с сотового искать очень неэргономично оказалось, но понял я это только на тесте, перещел на одно поле по первым буквам каждого слова, а там то всякая билеберда сыпется то сразу выдает, нет такой комбунации потому-что, астраханцы на 2-3 слове иногда вопрос обрывали.

Еще MySQL сглючил - непонятно как там функции поиска и сравнения реализованы, но явно не так, как я себе это представлял, хотя может мы с кодировками символов напутали

Ну ладно, только убедительная просьба про учебу больше мне не напоминать , а то эти госы достааали
Никаких там " профессор конечно лопух, но аппаратура при нем" и тп и тд и ВООБЩЕ НИЧЕГО СОВСЕМ НИЧЕГО.

Про применение хеширования к защите информации надеюсь сделать статью для сайта.

 
прикольно  
Интересная тема оказалась

Mayor писал(а):
алгоритм построения сбалансированого дерева ( в упрор за 1.5 месяца не мог понять, как вставить новый элемент за время меньшее N*ln(N) )

Не понятно, что ты имеешь в виду про время вставки.

Про то как это дерево выглядит, как в него после сборки новые значения вставлять, если это вообще без перепостроения возможно.

[npak]

Mayor, есть двоичные деревья, вставка в которые осуществляется без перестройки дерева, но во многих случаях дерево может получиться несимметричным, с отдельными ветвями большой глубины.

Но это выходит за рамки обсуждения хэширования.