| Форумы
ЧАТ |
Орешник |
|
| Форумы -» | Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG |
|
| ||
|
|
Новости |
Поиск |
FAQ |
Статьи |
Книги |
Новости VCL
| | Форумы ЧАТ |
Орешник |
|
| |||
| |||
| |||
« предыдущая ветвь | форум | следующая ветвь »
Хэш
Coder: TCoder; © (2004-08-05 10:52:00)Подскажите, пожалуйста, что из себя представляет хэш и для чего он нужен.
Coder: TCoder; (2004-08-05 12:54:00) [1]Thanks!
Romkin (2004-08-05 11:58:00) [2]Объяснили :)
В общем, хеширование - одна из методик поиска данных по ключам. При хешировании множество всех ключей отображается на множество хешей, которое, как правило, содержит гораздо меньше элементов, и поддерживает быстрый доступ к каждому из них.
Например: Есть список слов, и хочется быстро искать в нем.
Нужна функция хеширования, которая получает на вход строку со словом, и выдает на выходе число в диапазоне, например, 0..60000 (это только пример! Не все так просто).
Делаем массив, и размещает каждое слово в том элементе, индекс которого равен результату хеширования этого слова. Понятно, что функция может выдать одинаковый результат для разных слов, этот случай называется коллизией. Обычно коллизии разрешают хранением в элементе массива не одного слова-ключа, а целого списка.
Теперь искать просто: берем искомое слово, пропускаем его через функцию кеширования, и получаем номер элемента. Остается посмотреть в список этого элемента - если в нем слово есть, значит нашли.
Проблема здесь в том, чтобы правильно выбрать функцию кеширования, чтобы ключи распределялись максимально равномерно по таблице. :)) Если у нас всего 600000 слов, то понятно, что средня длина списка будет около 10 слов в каждом элементе. Вот и получается быстрый поиск - вычисляем хеш и просматриваем примерно 10 слов.
Anatoly Podgoretsky (2004-08-05 11:04:00) [3]хэш это функция свертки
REA (2004-08-05 11:03:00) [4]Я так понимаю:
Достаточно короткий по объему набор данных полученный из большего исходного набора, но с высокой долей вероятности выделяющий этот больший набор из множества наборов.
Используется например для ускорения поиска.
Например, зная длину строки, можно для сравнения строк использовать алгоритм, который будет сначала сравнивать длины и потом уже содержимое.
| |
