Хеш таблица

Возник вопросик:
   Как проводить поиск по хеш-таблице с ключом? И, кстати, какая в етом выгода. Объясните плиз.

 Хэш-таблица - вещь а сущности простая. У тебя есть некоторые данные которые нужно хранить, и предположим данные эти занимают много места. Для простоты скажем строки, с большой длинной. Вот у тебя здоровая база этих строк. Теперь ты хочешь найти определенную строку. Сравнивать со всеми строками в базе довольно долго, и чтоб этого не делать, неплохо бы определить способ, при помощи которого можно было бы сделать это быстро. Мы знаем, что числовые значения сравниваются гораздо быстрее, чем строковые. Неплохо было бы каждой строке сопоставить числовое значение и искать именно по нему. Теперь представим, что у тебя база срок записанна в таком виде(пока она у тебя маленькая):

length        value
------------------------
 2           "at","on","go"
 3           "car","cat","dog"
 4           "rain","snow"

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

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

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

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

И еще одно - ключи должны сохранятся по попорядку (для быстрого поиска). Тоесть при добавлении мы смотрим куда елемент поставить по значению его ключа?

" Для строк сложно придумать чтото лучше, чем сумма кодов * на номер символа в строке. "

Ну почему. Можно CRC32, на всю строку байтов.


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

Это уже зависит от твоей изобретательности.  ;D Но в основном так и есть.  

Спасибо большое. Разобрался.

Хорошая Хеш-Функция
Привет
Мне вот что нужно.
Подскажи мне какую нибудь хорошую Хеш-Функцию для строковой переменой.
Заранее спасибо.

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