Как можно с помощью хэш-таблиц (и хэш-функции) получить быстрый доступ к данным ? Например, у меня такая задача: цепное хэширование - информация - это структура вида: "Номер, Ф.И.О." хэширование идет по полю 'Номер'.

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

На форуме нашел очень мало инфы про хэш.  

вот код получения хэш-кода от строки (из ядра Linux)




Это сообщение отредактировал(а) MAKCim - 27.5.2007, 21:14

На пальцах:
Пример 1. 
Есть таблица типа 

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

Пример 2. 
Таблица вида:

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

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

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

Понятно, что реальное расположение элементов будет зависеть от хеш-функции. 
В этом случае заполнение происходило так: 
для строки "zero" функция выдала хеш-код == 3 => проверяем, есть ли кто нить уже на этой позиции - нет, тогда заносим этот элемент в хеш-таблицу в соответствующую позицию.
для строки "one" получили 5 -> проверили -> занесли
для строки "two" получили 0 -> проверили -> занесли
для строки "three" возможны два варианта, либо мы получили 6, и сразу занесли запись на место, либо получили 5 и вышла коллизия, рассмотрим последний вариант.  получили 5 -> проверили - блин, занято, ну фиг с ним посмотрим на следующую ячейку - ага свободно, ну пусть тут и живет  

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

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

Что то про конкретные реализации есть в википедии, да в инете их вагон должен быть.
Удачи!

Это сообщение отредактировал(а) zkv - 27.5.2007, 23:28

Суть такая.

Имеется множество значений (там чисел строк и тп). Мы хотим отобразить его в множество с меньшей мощностью, да ещё и обращаться к нему за время O(1).
Мы придумываем такую перемалывающую (hash) функцию, которая для данного значения даёт нам индекс во втором массиве.

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

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

Посмотри также 

Хоть и не стандарт, но в STLport есть и с MS VC++ 7.1 помоему тоже уже есть.