СД типа хеш-файл.

Date: 2015-10-07; view: 429.

Осуществляется отображение n:1. Хеширование является реализацией вышерассмотренной идеи. Хеширование задается функцией:

Function h (key.Tk): 0..N;

При создании файла каждый элемент отмечается как пустой. Запись данных в файл производится следующим образом. Вычисляется значение функции h. Если элемент с вычисленным номером пуст, то данные сохраняются в этом элементе. В противном случае ищется первый справа пустой элемент. Если дошли до конца файла, то возвращаемся назад и продолжаем поиск. Записываем в первый пустой элемент.

Чтение из файла производится по ключу аналогично. Вычисляется значение функции h. Если элемент пуст, то нужного элемента в файле нет. В противном случае ключ этого элемента сравнивается с заданным и в случае совпадения – ключ найден. Если значения сравниваемых ключей различны, то начинаем последовательный просмотр следующих элементов до тех пор, пока не найдется первый пустой элемент или элемент с заданным ключом.

A = k mod N – функция хеширования (N – простое число)

[k mod (10000/100)]

h(k) = B + m[k mod (10 ⁿ/10 ^l)], где B и m – константы, n > l.

В качестве хеш-функции может быть использован полином. В таком случае ключ – значение данного полинома. Вначале вычисляется полином, а затем берется по модулю относительно переменной N.