Cтраница 1
Хеш-функции могут быть использованы и для целей кодирования источника. Одна и та же хеш - функция может быть использована для кодирования нескольких источников. [1]
Хеш-функция производит пересчет ключа в адрес записи на файле. Эта операция выполняется СУБД всякий раз при поиске нужной записи по ключу. Связи позволяют осуществить группирование записей в множества, а также указывать взаимоотношения между этими множествами. На практике связь реализуется, как правило, в виде указателя. [2]
Хеш-функция зависит от типа ключа. Строго говоря, для каждого вида ключей, который может использоваться, требуется отдельная хеш-функция. Для повышения эффективности в общем случае желательно избежать явного преобразования типов, снова обратившись вместо этого к идее рассмотрения двоичного представления ключей в машинном слове в виде целого числа, которое можно использовать в арифметических вычислениях. Хеширование предшествовало появлению языков высокого уровня - на первых компьютерах было типичным в один момент времени рассматривать значение как строковый ключ, а в следующий - как целое число. В некоторых языках высокого уровня затруднительно создавать программы, которые зависят от того, как ключи представляются на конкретном компьютере, поскольку такие программы, по самой своей природе, являются машинно-зависимыми и поэтому их трудно перенести на другой компьютер. В общем случае хеш-функции зависят от процесса преобразования ключей в целые числа, поэтому в реализациях хеширования иногда трудно одновременно обеспечить независимость от компьютера и эффективность. Как правило, простое целочисленное значение или ключи типа с плавающей точкой можно преобразовать, выполнив всего одну машинную операцию, но строковые ключи и другие типы составных ключей требуют больше затрат и больше внимания в плане достижения высокой эффективности. [3]
Простейшие хеш-функции выбирают некоторое специальное подмножество из / address разрядов из строки с / name разрядами и используют их для формировзния адреса, как во втором и третьем примерах из рззд. Из нашего более рзннего обсуждения очевидно, что опзсность этого методз сострит в том, что он имеет тенденцию порождать чрезмерное количество коллизий, так кзк все имена, представления которых оказываются совпадзющими по подмножеству разрядов, выбранному хеш-функцией, отобрзжзются в один здрес. [4]
Хеш-функцию h определим следующим образом. [5]
Эти хеш-функции строятся с помощью полей Галуа. Длина программ этих функций близка к наименьшей. [6]
Пока хеш-функция относительно быстра и генерирует хеш-адреса, распределенные достаточно случайно, нам совершенно не важно, как она работает. [7]
Даже наилучшая хеш-функция не может дать полной гарантии того, что различные элементы данных при хешировании дадут различные хеш-адреса. Хотя желательно, чтобы хеш-функция распределяла генерируемые ею хеш-адреса по блоку как можно равномернее, почти неизбежна ситуация, когда два элемента данных дают при хешировании один и тот же хеш-адрес, что приводит к коллизии. [8]
Любая рационально подобранная хеш-функция удовлетворительно работает на большинстве значений ключа. В то же время для любой хеш-функции существуют множества значений ключа, на которых она плохо работает. Поэтому на основании экспериментальных данных подбирают такую хеш-функцию, которая не склонна отображать скученные значения ключа в скученные адреса. Хеш-функция приемлема, если она свободна от указанного недостатка в интересующей области значений ключа, ее легко вычислить и она хорошо работает на контрольных данных при решении контрольной задачи. Чтобы быстро вычислить хеш-адреса, большинство хеш-функций реализуется несколькими простейшими операциями, которые на ЭВМ можно выполнить несколькими командами над двоичным представлением значений ключей и адресов. [9]
Реализацию хеш-функции, поскольку она зависит от приложений, мы опускаем. Заметим лишь, что очень часто хеш-функция имеет вид h ( е) f ( е) mod р, где р - простое, a f ( е) функция с це-лыми значениями. [10]
Разработайте хеш-функцию для арокоиык ключей, основанную на HJCC одно йре нем но и заЕрузки 4 байт с последующим выполнением арифметических операции сразу нил 32 разрчлямл. [11]
Рассмотренные выше хеш-функции предполагают, что значения ключей записей и все промежуточные вычисления не превышают машинных форматов представления числовых данных для используемой ЭВМ. Есть и другие типы Хеш-функции. [12]
В идеале хеш-функция h: S - - A должна была бы легко вычисляться и отображать пространство имен в пространство адресов так, чтобы равномерно рассеять имена по памяти. S, то приемлемы простые хеш-функции, например функции, в которых подцепочки имени интерпретируются как двоичные целые. Однако на самом деле мы заботимся только о том, рассеивается ли содержимое таблицы, а не все пространство имен по памяти равномерно. Таким образом, хеш-функция должна была бы быть построена так, чтобы равномерно рассеять по памяти те подмножества множества S, которые могут встретиться в качестве содержимого таблицы. [13]
Метод вычисления хеш-функции и методы вычисления последовательностей псевдослучайных чисел имеет много общего: в основе их лежат одни и те же закономерности, а при их вычислении используются практически одни и те же простые операции. Получение очередного псевдослучайного числа последовательности не что иное, как вычисление значения хеш-функции от последнего ( или двух последних) полученного члена последовательности. При выборе метода вычисления хеш-функции на практике обычно отдают предпочтение делению или умножению из-за простоты этих методов, позволяющих производить вычисление с высокой скоростью и допускающих простую реализацию на языке высокого уровня. Однако для аппаратной или микропрограммной реализации хеш-функции очень хорошо подходит также метод деления многочленов. [14]
Эта реализация хеш-функции для строковые ключей требует одного умножения н Одного сложения на каждый сим & ол в к / ю е, Если Бы константу 127 мы константой 128, программа просго йыч сггяла бы рстзтдк от деления числа, стеующего 7-разрядно лу АЗС1Е првдсгападнию ключа, на размер габяииы с исполь-зопднием метода Горндрэ. [15]