Хэш-функция и поиск

← →
boalse © (2005-11-28 10:34) [0]

Слышал, что при помощи хэш функции можно организовывыть быстрый поиск по большой базе данных. Как это работает? Объясните, пожалуйста, основной принцип на пальцах, если не трудно.

← →
Anatoly Podgoretsky © (2005-11-28 10:37) [1]

поиск по большой базе данных будет более быстрым если по полю будет индекс.

← →
boalse © (2005-11-28 10:39) [2]

А что такое индекс? Тоже на пальцах.
И всё-таки меня больше интересует не самый быстрый поиск, а как это хэш-функция может его осуществить? По какому алгоритму?

← →
Anatoly Podgoretsky © (2005-11-28 10:41) [3]

А никак, хеш функция замедляет поиск или делает его невозможным.

← →
Nikolay M. © (2005-11-28 10:43) [4]

Поиск сдох?
http://www.yandex.ru/yandsearch?rpt=rad&text=hash+%EF%EE%E8%F1%EA

← →
boalse © (2005-11-28 10:51) [5]

Искал я в поисковике, ничего понятного так и не нашел.

← →
Nikolay M. © (2005-11-28 10:59) [6]

Значит так искал. По моей ссылке в 4-м результате поиска все расписано более чем доступно.

← →
Sergey13 © (2005-11-28 11:05) [7]

2[2] boalse © (28.11.05 10:39)
>А что такое индекс? Тоже на пальцах.
Если тебе это непонятно, то и проку от хеш функций не будет. ИМХО.

← →
boalse © (2005-11-28 11:09) [8]

Мне не нужен от нее прок в данный момент, я хочу знать как это работает.

Nikolay M, спасибо, кое-что понял. Способ действительно не всегда удобный и оптимальный.

А про индексы. Буду рад конкретной ссылке.

← →
Sergey13 © (2005-11-28 11:23) [9]

2[8] boalse © (28.11.05 11:09)
Ты школьную программу с матанализа начинал изучать? Может все таки с азов?

← →
Nikolay M. © (2005-11-28 12:10) [10]

> Буду рад конкретной ссылке.

ya.ru

← →
PAVIA © (2005-11-28 22:27) [11]

Описываю в двух словах, что такое ХЭШ функции и как работает поиск.

Берем строку. Отпровляем ее в ХЭШ-функцию она высчитывает некоторое число по этой строке (ХЭШ). Число это должно быть уникальным для разных строк. Так как число по размеру меньши строки, то число различных строк ограничено некоторым конечным множеством. Так как размер числа много различных вариаций строк то возникают колизии. Это когда для разных строк получаються одинаковые значения. Для избежания колизий используют списки. Создается массив списков. Индэксем в которым служит ХЭШ. Для поиска данного значения в базе достаточно посчитать значение ХЭШ-фукции и подставить его в качестве индекса.

Нужно стремиться чтобы ХЭШ-функция, как можно более равномерно рапределяла значения для различных строк. Даже если строка отличаеться только одной буквой.

Пример ХЭШ функции.
function GetHesh(s:string;M:word):Word;
var h,i,a,b:Word;
begin
a:=31415;
b:=27183;
h:=0;
for i:=1 to length(s) do
begin
h:=(a * h + ord(s[i])) mod M;
a:=a*b mod (M - 1);
end;
GetHesh:=h;
end;
тут M размер массива.

Подробности ищи в интернете. Или у Кнута 3 том.

← →
boalse © (2005-11-29 04:27) [12]

> PAVIA © (28.11.05 22:27) [11]

Спасибо.

Хотелось бы подробнее узнать об индексации БД. Допустим, есть неупорядоченная БД:

Баранка
Яблоко
Груша
Абрикос
Финик

Как её нужно проиндесировать и как будет происходить поиск?
Я понимаю это так:

02 01 Баранка 05 02 Яблоко 03 03 Груша 01 04 Абрикос 04 05 Финик

первые две цифры индекса обозначают, какое значение должно быть первым, каое вторым, следующие две цифры - это реальное местоположение записи в БД.

Теперь, чтобы найти "Яблоко" делаем следующее:
1. тыкаемся в середину упорядоченных индексов, в данном случае 3, смотрим, что под этим индексом "груша", это меньше, чем "яблоко", значит искать надо в диапазоне индексов от 4 до 5.
2. Делим опять диапазон от 4 до 5 на два, округляя вверх или вниз, в данном случае середину можно взять, например, 4.
3. Смотрим, под индексом 4 - "финик", это меньше, чем "яблоко", значит искать нужно в диапазоне от 5 до 5, получается, что мы нашли нужное значение и его реальное положение в базе - 2.

Правильно ли я все это понимаю?

При такой индексации, как у меня, при добавлении новой записи нужно все переиндексировать, но это не приемлемо. Как проходит индексация в современных БД?

← →
evvcom © (2005-11-29 08:27) [13]

> Как проходит индексация в современных БД?

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

← →
boalse © (2005-11-29 09:08) [14]

> evvcom © (29.11.05 08:27) [13]

Где именно? Ничего я там не увидел.

← →
evvcom © (2005-11-29 09:11) [15]

> Где именно? Ничего я там не увидел.

Nikolay M. © (28.11.05 10:59) [6]
Я так сразу увидел. Там слева списочек, ты по линкам кликал?

← →
boalse © (2005-11-29 09:23) [16]

Кликать, то кликал, и даже прочитал вот только про индексацию ничего не нашел. про Хэш функции нашел, об этом еще в [8] сказал

← →
evvcom © (2005-11-29 10:20) [17]

Все что находится под "Словари" относится к индексам. В том числе и хеш-таблицы. Это разные методы (варианты) индексации. Причем это не полный список.

← →
boalse © (2005-11-29 10:23) [18]

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

Из этих высказываний следует, что это разные вещи.

← →
Anatoly Podgoretsky © (2005-11-29 10:42) [19]

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

> Хеши используются не для поиска, а для необратимого, одностороннего
> шифрования - это элемент безопасности, а не поиска.

И все же хеш используют и для поиска тоже. В Оракле, например, джойн 2 таблиц, из которых хотя бы одна большая, наиболее эффективным получается HASH JOIN. Естественно, что ни одна хеш-функция не дает гарантии абсолютной уникальности результата, поэтому я думаю, они после нахождения нужного хеш-значения, все-таки должны сравнить оригиналы. Но тем не менее осуществлять поиск по 4 байтам все равно будет гораздо быстрее, чем по 5 и более (для 32 разрядных ОС).

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

> можно делать поиск по полю с хешем

Ну так, если поле в таблице, а хеш в индексе, это так и будет. Надо найти Васю Пупкина, находим его хеш и ищем уже значение хеша в индексе. Что-то не так?
Ну а 4 байта или 16 - все зависит от количества и разнообразия данных. А то в теории можно предположить их такое количество, что и 32 байта будут давать огромное количество коллизий. :) Этот спор, я думаю, можно оставить.

Anatoly Podgoretsky

> хеш для поиска не используют, это не возможно,

Это возможно и это используется, как это делается я рассказал. Спорить тут не о чем.
Насчет размера ХЭШа все зависит от условий задачи. Если в базе 10 записей и ХЭШ из 4 байт(2^32 вариантов) то говорить о коллизии смешно. А если в базе 65536 записей и ХЭШ размером 2Байта(65536), то разуметься будут коллизии и их будет много.
16 Байт и более используется в криптографии для шифрования. Потому что перебрать 2^16 и 2^32 легко, а вот 2^128 уже долго.
Также ХЭШ используются для проверки целостности данных.

Преимущество ХЭШ поиска в том, что нам не нужно проверять всю запись подряд, а достаточно посчитать ХЭШ функцию. Далее результат будет моментальным. Так как подставить значение ХЭШ в массив не занимает времени. +Проверка на коллизии.

Насчет поиска по полю ХЭШ значений. Да базы данных обычно используют B+ деревья. Поэтому искать по значению ХЭШ нельзя, а можно только искать по полю ХЭШый. Что разуметься будет ниже по скорости.

to Anatoly Podgoretsky

> хеш для поиска не используют, это не возможно,

Смотря какой хэш.
Индексные файлы в базах данных ПРЕДСТАВЛЯЮТ СОБОЙ ХЭШ.
Как правило это двоичные деревья. Как они фунциклируют хорошо описано "Фундаментальные алгоритмы и типы данных в Delphi".

Например из строки "Сегодня модно быть хакером" можно выделить первые два слова и если данное значение больше не встречается - это стпудовый хэш. (Значение не повторяется на всём промежутке значений).

Ксати в перл есть такой тип данных - хэш поместь record и ассоциативного массива. Ты его тоже к криптографии подмешаешь?

Привет...
Кошмар, а книгу лень прочесть...

В книгах и статьях индексация упоминается мельком, ну, что она используется для ускорения поиска, а как именно она используется, ничего не сказано. Мне инетресно, например, как индексируются dbf файлы в 1C:Предприятии и т.п. Всё что я знаю по прочитанному руководству, это то, что создаётся файл CDX, в котором как-то записыны индексы. У индекса есть наименование, признак уникальности, выражение индекса и фильтр. А вот что для чего использутся написано мельком, типа, это не так важно. Для программирования в 1С, это действительно не так важно, но мне всёже хочется знать хотябы примерно структуру CDX и для чего именно используется каждая часть иднекса. И главное, как имено эти индексы ускоряют поиск.

чтобы пользоваться выключателем необязательно знать как устроен электрогенератор/и т.д. всю цепочку пока тог не "подошол" к выключателю...

а если всетаки хочется знать, то ты выбрал не те книги, руководство по 1С и долно описывать это мельком т.к. явно они это там все одно не используют а руководство всетаки именно по языку.

и в 4-ой ссылке поиска всетаки есть про то как построен индекс, раздел "Очень большие файлы", немного и теория (и явно не все возможные типы индексов) но чего хотел от поиска по хешу? для информации по индексам надо и поиск по ним делать
http://www.yandex.ru/yandsearch?text=%F1%F2%F0%F3%EA%F2%F3%F0%E0+%E8%ED%E4%E5%EA%F1%ED%FB%F5+%F4%E0%E9%EB%EE%E2&stype=ww w

Хэш-функция и поиск Найти похожие ветки