Адресация записей
На рис.2 изображен структурированный граф (SG). Он показывает, сколько расщеплений было применено к блоку, и какие перераспределенные адреса были созданы каждым расщеплением. i-ое расщепление для адреса изображается вертикальным ребром ((m,i–1), (m,i)) и набором ребер перераспределения ((m,i–1), (m’,0)) для каждого перераспределенного адреса, обеспеченного этим расщеплением.
Граф на рис.2 соответствует расщеплению (А). Так, только одно ребро перераспределения создается посредством расщепления. Мы также показали hj для каждого расщепления. Только такие графы анализируются ниже.
Пусть g будет таким графом и пусть s(c) будет путь, сформированный всеми узлами (m,i), такими, что j-ый узел пути имеет m = hj(c). g составляется подпутями s(c,g), каждый из которых получен некоторыми первыми узлами s(c). Прямой (начальный) адрес для c , задаваемый графом g, есть конечный адрес соответствующего s(c,g).
Пусть задано N. Всякое множество M
есть множество конечных адресов ребер
перераспределения не более чем одного
графа g. Это значит, что из битовой таблицы
В, в которой В(m-N) = 1 эквивалентно тому,
что m есть конечный адрес ребра
перераспределения g , мы можем найти,
является ли hj(c) адресом узла в графе g.
Если для некоторого i узел (hj(c),i) является
конечным узлом графа g (листом графа),
то m – это искомый прямой (начальный)
адрес.
Рис.2 – структурированный граф. Страница m была расщеплена 3 раза функциями h1, h2, h3. Страница m+N была расщеплена 2 раза: сначала h2 , а затем h3 .
Пусть l(g) будет максимальной длиной пути s(c,g). Если мы вычисляем hl(g)(c) и этот адрес принадлежит g , то это должен быть адрес конечного узла (листа). Иначе, это справедливо для l(g)-1 и т.д. Прямой (начальный) адрес для ключа c может быть, таким образом, вычислен следующим алгоритмом:
Заключение
Хэширования, которое родилось еще в середине прошлого века, активно используется в наши дни везде, где требуется произвести быструю выборку данных. Появились новые методы хэширования, новые модификации алгоритмов, написанных ранее. По мнению Дональда Кнута, наиболее важным открытием в области хэширования со времен 70 годов, вероятно, является линейное хэширования Витольда Литвина. Линейное хэширования, которое не имеет ничего общего с классической технологией линейной адресации, позволяет многим хеш-адресам расти и/или выступать в поли вставляемых и удаляемых элементов. Линейное хэширования может также использоваться для огромных баз данных, распределенных между разными узлами в сети.
Разумеется, методы и сферы применения хэширования не ограничиваются тем, что представлено в этой работе. Не вдаваясь в строгий анализ эффективности, были рассмотрены только базовые, наиболее известные методы. Помимо них можно отметить полиномиальное хэширования (М. Ханан и др., 1963), упорядоченное хэширования (О. Амбль, 1973), линейное хэширования (В. Литвин, 1980).