Cтраница 2
Эта реализация хеш-функции для строковых ключей требует одного умножения и одного сложения на каждый символ в ключе. Если бы константу 127 мы заменили константой 128, программа просто вычисляла бы остаток от деления числа, соответствующего 7-разрядному ASCII-представлению ключа, на размер таблицы с использованием метода Горнера. [16]
Выбор второй хеш-функции требует определенной осторожности, поскольку в противном случае программа может вообще не работать. Во-первых, необходимо исключить случай, когда вторая хеш-функция дает значение, равное 0, поскольку это приводило бы к бесконечному циклу при первом же конфликте. [17]
Для определения совершенной хеш-функции ( не обязательно минимальной) требуется довольно большой объем первоначальных вычислений, пробы, ошибки и повторные вычисления. Однако в некоторых случаях, таких, как обработка ключевых ( зарезервированных) слов языка программирования или языка запросов информационной системы, имеет смысл проделать такую работу. [18]
Чтобы вычислить модульную хеш-функцию для длинных ключей, последние преобразуются фрагмент за фрагментом. [19]
Хеширование предполагает наличие хеш-функции. Хеш-функция h ( y) определена на множестве записей X и переводит его в множество 1 ш, где т - параметр хеш-функции. [20]
При случайном выборе хеш-функций необходимо иметь а-ун-и-версальное множество, из которого этот выбор производится. [21]
Хеширование предполагает наличие хеш-функции. Хеш-функция h ( у ] определена на множестве записей X и переводит его в множество 1, га, где га - параметр хеш-функции. [22]
Такая функция называется модульной хеш-функцией. [23]
Рассмотренные в разделе 14.1 хеш-функции преобразуют ключи в адреса таблицы; второй компонент алгоритма хеширования - определения способа обработки случая, когда два ключа представляются одним и тем же адресом. Самый прямой метод - построить для каждого адреса таблицы связный список элементов, ключи которых отображаются на этот адрес. Данный подход ведет непосредственно к обобщению метода элементарного поиска в списке ( см. главу 12) из программы 14.3. Вместо поддержки единственного списка поддерживаются М списков. [24]
Рассмотрим некоторые методы построения хеш-функций. [25]
В соответствии с этой хеш-функцией каждую граньч надо поместить в те гнезда, которые за девает прямоугольник грани, а при построении изображения ребра перебирать грани только из тех гнезд, которые задевает прямоугольник ребра. [26]
& схолько эондираваний, если хеш-функция создает значения, достаточно близкие случайным. [27]
Для проверки гипотезы, что хеш-функция создает случайные значения, можно использовать функцию статистического распределения 2 ( см. упражнение 14.5), но, возможно, это требование - слишком жесткое. Действительно, нас вполне может удовлетворить, если хеш-функция создает каждое значение одинаковое количество раз, что соответствует значению функции статистического распределения 2, равному 0, и местами не является случайным. [28]
Именно таким образом была определена совершенная хеш-функция для названий префектур, представленных в табл. 2.4, в начале данного раздела. [29]
Таким образом, при подборе хеш-функции важен не тот факт, что хеш-функция равномерно распределяет все множество К значений ключа по выделенному участку памяти. Необходимо, чтобы хеш-функция равномерно рассеивала по выделенному участку памяти те подмножества значений К ключа, которые могут встретиться в реальном файле. Эти вероятные подмножества редко можно точно охарактеризовать, поэтому хеш-функции обычно строятся на основе правил, подчиняющихся здравому смыслу. [30]