Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: хэш  (Прочитано 24672 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Mayor
Специалист

ru
Offline Offline

« : 12-05-2004 06:25 » 

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

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

1n c0de we trust
MOPO3
Ай да дэдушка! Вах...
Команда клуба

lt
Offline Offline
Пол: Мужской
Холадна аднака!


WWW
« Ответ #1 : 12-05-2004 07:15 » 

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

MCP, MCAD, MCTS:Win, MCTS:Web
ysv_
Помогающий

ua
Offline Offline

« Ответ #2 : 12-05-2004 07:34 » 

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

ru
Offline Offline

« Ответ #3 : 12-05-2004 15:27 » 

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

1n c0de we trust
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #4 : 12-05-2004 15:40 » 

Кнут, первый том.
Записан

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Mayor
Специалист

ru
Offline Offline

« Ответ #5 : 13-05-2004 00:57 » 

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

1n c0de we trust
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #6 : 13-05-2004 14:24 » 

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

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

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

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

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

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

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Mayor
Специалист

ru
Offline Offline

« Ответ #7 : 19-05-2004 01:49 » 

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

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

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

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

1n c0de we trust
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #8 : 19-05-2004 10:31 » 

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

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #9 : 19-05-2004 12:54 » 

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

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Mayor
Специалист

ru
Offline Offline

« Ответ #10 : 22-05-2004 04:16 » 

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

1n c0de we trust
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #11 : 22-05-2004 06:51 » 

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

Не будите спашяго дракона.
             Джаффар (Коша)
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #12 : 22-05-2004 21:30 » 

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

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

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

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

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

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

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

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

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

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #13 : 22-05-2004 22:11 » 

Цитата: Finch
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, обрати внимание, что для построения и использования хэш-таблицы достаточно сравнения на равенство, сравнение больше-меньше не обязательно.  Хэш-таблица, вообще говоря, выигрывает в скорости у поиска в отсортированной структуре данных, так как для хорошо подобранных хэш-функции и размере таблицы число сравнений при поиске почти не зависит от размера таблицы (более-менее константа, хотя есть и исключения), в то время как самые лучшие алгоритмы поиска дают логарифмическую зависимость числа сравнений от размера таблицы.

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

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

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Finch
Спокойный
Администратор

il
Offline Offline
Пол: Мужской
Пролетал мимо


« Ответ #14 : 23-05-2004 16:01 » 

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

Не будите спашяго дракона.
             Джаффар (Коша)
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #15 : 24-05-2004 10:52 » 

Цитата: npak
RXL, я правильно разъяснил суть работы?
Совершенно верно.
Записан

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Mayor
Специалист

ru
Offline Offline

« Ответ #16 : 01-06-2004 02:32 » 

Цитата

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

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



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

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


Цитата

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

 

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


Цитата

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

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

1n c0de we trust
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #17 : 01-06-2004 09:23 » 

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

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

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

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #18 : 01-06-2004 10:23 » 

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

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

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

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

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

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
RXL
Технический
Администратор

ru
Offline Offline
Пол: Мужской

WWW
« Ответ #19 : 01-06-2004 10:40 » 

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

... мы преодолеваем эту трудность без синтеза распределенных прототипов. (с) Жуков М.С.
Mayor
Специалист

ru
Offline Offline

« Ответ #20 : 06-06-2004 01:48 » 

Цитата

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

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

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

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

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



Цитата

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

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


Цитата

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

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


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

1n c0de we trust
npak
Команда клуба

ru
Offline Offline
Пол: Мужской

« Ответ #21 : 07-06-2004 07:30 » new

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

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

UniTesK -- индустриальная технология надежного тестирования.

http://www.unitesk.com/ru/
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines