Cтраница 3
Решение основывается на идее, что хеш-функция создает короткий сертификат, представляющий ключ; это важная концепция, находящая применение и в приложениях, которые отличаются от реализаций таблиц символов. [31]
Для множества ключей неопределенной длины найти хеш-функцию с идеальными свойствами практически невозможно. Даже если представить, что такую функцию h ( k) представить удалось, то она будет взаимно однозначной не более чем для конечного числа первых символов ключа. [32]
При открытой адресации ( open addressing) хеш-функция вычисляет положение элементов данных в массиве. [33]
К счастью, как мы увидим, хеш-функция не является самым важным фактором техники хеширования. Любая разумная хеш-функция будет удовлетворительно работать на большинстве множеств имен; и в то же время для любой хеш-функции существуют множества имен, на которых она работает плохо. В этом разделе описывается, как избежать хеш-функций, которые плохо работают на некоторых распространенных множествах имен. [34]
В литературе / 11 12 / предлагаются различные хеш-функции и разнообразные методы разрешения коллизий. При выборе функции желательно, чтобы время вычисления ее значения было как можно меньше и элементы располагались в таблице достаточно равномерно. Обычно размер памяти для таблицн должен я два-три раза превышать предполагаемое число элементов таблицы, что дает существенный выигрыш so времени доступа. [35]
Итак, каким бы ни был выбор хеш-функции, возможны коллизии, первичные и вторичные скучивания. Это связано с тем, что в основе хеширования лежат вероятностные законы. В худшем случае характеристики этих методов могут оказаться очень плохими. Поэтому особенно важно знать, каково поведение методов хеширования в среднем. [36]
Прежде всего, необходимо решить задачу вычисления хеш-функции, которая занимается преобразованием ключей в адреса в таблице. Обычно реализация этого математического вычисления не представляет сложности, но необходимо соблюдать определенную осторожность во избежание различных малозаметных ловушек. Идеальную хеш-функцию легко вычислить и аппроксимировать случайной функцией: для любого вводимого значения в определенном смысле выводимое значение должно быть равновероятным. [37]
Зная распределение кластеров, можно решить, какая хеш-функция является предпочтительной. [38]
Для такого контроля подсчитываются контрольные суммы и вычисляются хеш-функции, которые потом сравниваются с эталонными значениями для каждой ЭВМ. [39]
Существуют и другие методы организации памяти при использовании хеш-функций. [40]
Когда содержимое таблицы известно до того, как строится хеш-функция, само пространство имен не имеет значения. В этом примере мы могли предположить, что пространство имен было просто данным множеством из пяти слов, что оно было множеством всех наборов из двух букв или что это было множество всех наборов произвольной длины. [41]
Для случая промаха при поиске можно считать, что хеш-функция достаточно равномерно перемешивает значения ключей, чтобы поиск в каждом из М списков был равновероятным. Тогда характеристики производительности, рассмотренные в разделе 12.3, применимы к каждому списку. [42]
В широком смысле Л; 0 представляет собой последовательность хеш-функций. Выбор их, однако, представляет достаточно сложную проблему. Считая, что hu является одной из ранее рассмотренных функций, обсудим, какой вид могут иметь другие функции последовательности. [43]
Для того чтобы обеспечить быстрое вычисление хеш-адресов, большинство хеш-функций близки к примитивным операциям, допустимым для ЭВМ, в связи с чем они лучше описываются на уровне операций над двоичными наборами в представлениях имен и адресов. Поэтому будем полагать, что имена и адреса представлены двоичными наборами длины / name и / address соответственно. [44]
Отправитель информации ( / - и абонент) вычисляет хеш-функцию h ( X) от аргумента Л - передаваемого сообщения. [45]