Хэш

← →
Coder: TCoder; (2004-08-05 10:52) [0]

Подскажите, пожалуйста, что из себя представляет хэш и для чего он нужен.

← →
REA © (2004-08-05 11:03) [1]

Я так понимаю:
Достаточно короткий по объему набор данных полученный из большего исходного набора, но с высокой долей вероятности выделяющий этот больший набор из множества наборов.
Используется например для ускорения поиска.
Например, зная длину строки, можно для сравнения строк использовать алгоритм, который будет сначала сравнивать длины и потом уже содержимое.

← →
Anatoly Podgoretsky © (2004-08-05 11:04) [2]

хэш это функция свертки

← →
Romkin © (2004-08-05 11:58) [3]

Объяснили :)
В общем, хеширование - одна из методик поиска данных по ключам. При хешировании множество всех ключей отображается на множество хешей, которое, как правило, содержит гораздо меньше элементов, и поддерживает быстрый доступ к каждому из них.
Например: Есть список слов, и хочется быстро искать в нем.
Нужна функция хеширования, которая получает на вход строку со словом, и выдает на выходе число в диапазоне, например, 0..60000 (это только пример! Не все так просто).
Делаем массив, и размещает каждое слово в том элементе, индекс которого равен результату хеширования этого слова. Понятно, что функция может выдать одинаковый результат для разных слов, этот случай называется коллизией. Обычно коллизии разрешают хранением в элементе массива не одного слова-ключа, а целого списка.
Теперь искать просто: берем искомое слово, пропускаем его через функцию кеширования, и получаем номер элемента. Остается посмотреть в список этого элемента - если в нем слово есть, значит нашли.
Проблема здесь в том, чтобы правильно выбрать функцию кеширования, чтобы ключи распределялись максимально равномерно по таблице. :)) Если у нас всего 600000 слов, то понятно, что средня длина списка будет около 10 слов в каждом элементе. Вот и получается быстрый поиск - вычисляем хеш и просматриваем примерно 10 слов.

← →
Coder: TCoder; (2004-08-05 12:54) [4]

Thanks!

Хэш Найти похожие ветки