первым, кто упомянул идею деления на простое число и использование остатка в качестве хеш-адреса. В интересной статье Думи упоминает цепочки, но открытой адресации в ней нет. Советский математик А. П. Ершов в 1957 году независимо разработал метод линейной открытой адресации [ДАН СССР 118 (1958), 427-430]; он опубликовал эмпирические результаты по количеству проб, справедливо предположив, что среднее количество проб для успешного поиска < 2 при N/M < 2/3.

Классическая статья W. W. Peterson, IBM J. Research & Development 1 (1957), 130-146, была первой важной работой, посвященной поиску в больших файлах. Петерсон определил открытую адресацию в общем случае, проанализировал производительность равномерного исследования и привел многочисленные эмпирические статистические данные о поведении линейной открытой адресации с блоками различных размеров, указав на ухудшение производительности при удалении элементов. Другой всесторонний обзор предмета был опубликован шестью годами позже Вернером Букхольцем (Werner Buchholz) [IBM Systems J. 2 (1963), 86-111]. В его работе особый упор сделан на исследовании хеш-функций. Корректный анализ алгоритма L был впервые опубликован А. Г. Конхеймом (А. G. Konheim) и Б. Вейссом (В. Weiss) [SIAM J. Appl. Math. 14 (1966), 1266-1274], a также В. Подде-рюгиным [WissenschaftJiche Zeitschrift der Tecijniscijen Universitat Dresden 17 (1968), 1087-1089].

К этому времени линейное исследование было единственным типом схемы открытой адресации, описанной в литературе, хотя несколькими исследователями независимо была разработана другая схема, основанная на неоднократном случайном применении независимых хеш-функций (см. упр. 48). В течение нескольких последующих лет хеширование стало широко использоваться, хотя не было опубликовано никаких новых работ. Затем Роберт Моррис (Robert Morris) написал обзор по хешированию [САСМ 11 (1968), 38-44], оказавший впоследствии большое влияние на работы в этом направлении. В обзоре впервые появилась идея случайного исследования с вторичной кластеризацией. Статья Морриса оказалась наброском дальнейших исследований в этой области, которые завершились созданием алгоритма D и его усовершенствованных версий.

Интересно отметить, что слово "хеширование" (hashing), по-видимому, ни разу не появилось в печати (в его современном значении) до 60-х годов, хотя к тому времени оно прочно заняло место в компьютерном жаргоне во всем мире. Впервые это слово, вероятно, было использовано в книге Н. Hellerman, Digital Computer System Principles (New York: McGraw-Hill, 1967), 152. При работе над этим разделом автор изучил около 60 относящихся к хешированию документов, однако более раннее упоминание данного термина встретилось лишь один раз в неопубликованном меморандуме В. В. Петерсона, датированном 1967 годом. Получилось так, что, хотя глагол "хешировать" (to hash) стал стандартным термином в средине 60-х годов, никто не решался использовать в печати столь недостойное слово до 1967 года!*

* Становление нового термина - процесс непростой, и, пожалуй, уместно вспомнить, что еще совсем недавно вместо слова "компьютер" в нашей литературе использовалось в лучшем случае ЭВМ, вместо "винчестер" - НЖМД (для тех, кто не помнит этот термин, напомним, что он означает "накопитель на жестком магнитном диске"), вместо "дискета" - ГМД (гибкий магнитный диск). .. - Прим. перев.

Последние разработки. Со времени первой публикации этой главы в 1972 году в области теории и практики хеширования было сделано немало новых достижений, хотя основные идеи остались полезными для использования в обычных приложениях. Например, в книге J. S. Vitter and W.-C. Chen, Design and Analysis of Coalesced Hashing (New York: Oxford Univ. Press, 1987) рассмотрены и проанализированы различные поучительные варианты алгоритма С.

С практической точки зрения наиболее важным открытием в области технологии хеширования со времен 70-х годов, вероятно, является метод Витольда Литвина (Witold Litwin), называемый линейным хешированием [Ргос. 6th International Conf on Very Large Databases (1980), 212-223]. Линейное хеширование, которое не имеет ничего общего с классической технологией линейного исследования, позволяет многим хеш-адресам расти и/или выступать в роли вставляемых и удаляемых элементов. Превосходное обсуждение линейного хеширования, включая сравнение с другими методами, можно найти в работах Рег-Аке Larson, САСМ 31 (1988), 446-457, W. G. Griswold and G. М. Townsend, Software Practice & Exp. 23 (1993), 351-367 (в последней работе рассмотрены усовершенствования метода для одновременного использования множества больших и/или маленьких таблиц). Линейное хеширование может также использоваться для огромных баз данных, распределенных между многими узлами в сети [см. Litwin, Neimat, and Schneider, ACM Trans. Database Syst. 21 (1996), 480-525]. Альтернативная схема, называемая расширяемым хешированием {extendible hashing) и имеющая то свойство, что для выборки любой записи требуется не более двух ссылок на внешние страницы, была предложена в то же время в работе R. Fagin, J. Nievergelt, N. Pippenger, and H. R. Strong [ACM Trans. Database Syst. 4 (1979), 315-344]. Как линейное, так и расширяемое хеширования предпочтительнее использования В-деревьев (см. раздел 6.2.4) в том случае, когда порядок ключей не имеет значения.

В области теоретической были разработаны более сложные методы, которые могут гарантировать максимальное время доступа 0(1) со средним временем на вставку и удаление 0(1) независимо от ключа. Более того, общее количество пространства, требуемого для работы алгоритма, ограничено некоторой константой, умноженной на количество элементов, имеющихся в настоящий момент в наличии, плюс некоторая другая константа*. Этот результат, основанный на идеях Фредмана (Fredman), Комлёса (Komlos) и Семереди (Szemeredi) [JACM 31 (1984), 538-544], получен в работе Dietzfelbinger, Karlin, Mehlhorn, Meyer auf der Heide, Rohnert, and Tarjan [SICOMP 23 (1994), 738-761].

УПРАЖНЕНИЯ

1. [20] Насколько мало и насколько велико может быть содержимое г11 по достижении команды 9Н, приведенной в табл. 1, в предположении, что каждый из байтов 1, 2, 3 ключа К содержат символы с кодами, меньшими 30?

2. [20] Найдите довольно известное английское слово, которого нет в табл. 1 и которое может быть добавлено в нее без изменения программы.

* Иначе говоря, не мудрствуя, можно записать, что требуемая для хранения память составляет Cl N -\- С2. - Прим. перев.

3. [23] Объясните, почему программу, приведенную в табл. 1, нельзя заменить более простой программой, которая начинается с пяти следующих ниже команд, ни при какой константе а, с учетом того, что рмные ключи не могут иметь одинаковые хеш-адреса?

LD1 К(1:1) или LD1N К(1:1) LD2 К(2:2) или LD2N К(2:2) INC1 а,2 LD2 К(3:3) J2Z 9F

4. [МЗО] Сколько гостей следует пригласить на вечеринку, чтобы вероятность появления трех человек с одним и, тем же днем рождения была не менее ?

5. [15] Мистер Ламер писал компилятор FORTRAN с использованием десятичного компьютера MIX, и ему понадобилась таблица символов для хранения имен переменных в программе во время компиляции. Эти имена имеют ограниченную длину - не более десяти символов. Ламер решил использовать хеш-таблицу с М = 100, а для скорости работы использовал хеш-функцию h{K) - крайний левый байт К. Насколько хороша его идея?

6. [15] Насколько разумно заменить две первые команды из (3) командами LDA К; ENTX О?

7. [НМЗО] {Полиномиальное хеширование.) Назначение этого упражнения - рассмотреть построение полино.мов Р{х), как в (10), которые преобрмуют п-битовые ключи в ш-битовые адреса так, что различные ключи, отличающиеся не более чем t бит, будут иметь различные хеш-адреса. По заданным значениям п и f < п, и по данному целому fc, такому, что п делит 2* - 1, построим полином степени т, где т является функцией п, i и fc. (Обычно при необходимости п увеличивается, так что к может быть выбрано достаточно малым.)

Пусть S - минимальное множество целых чисел, таких, что {1,2,...,*} С S и {2j) mod п е S для всех j € S. Например, при п = 15, fc = 4Hi = 6 имеем S = {1, 2, 3,4, 5, 6, 8,10,12, 9}. Теперь определим полином Р{х) = Yljesi- ~ -) "- - элемент порядка п конечного поля GF(2*), а коэффициенты Р{х) вычисляются в этом поле. Степень т полинома Р{х) равна числу элементов в S. Поскольку, если - корень Р{х), то и а-" - корень Р{х), отсюда следует, что коэффициенты pj полинома Р{х) удовлетворяют условию р- -Рг, т. е. они представляют собой О или 1.

Докажите, что если R{x) = Гп-хж"- -Ь • • • -Ь rix + Го представляет собой некоторый ненулевой многочлен по модулю 2 с не более чем t ненулевыми коэффициентами, то R{x) не кратен Р{х) по модулю 2. (Отсюда следует, что соответствующая хеш-функция ведет себя, как и было обещано*.)

8. [М34] {Теорема о трех длинах.) Пусть в - иррациональное число между О и 1, представление которого в виде регулярной непрерывной дроби в обозначениях раздела 4.5.3 есть в = а1,а2,аз,... . Пусть до = О, ро = 1, gi = 1, pi = О и qk+i = QkQk + Як-\, Pk+i = йкРк + Pk-i при fc > 1. Пусть {х} означает z mod 1 = х - [х}, а {ж}""" - х -[х] + 1. Перенумеруем отрезки, получающиеся в результате последовательной вставки точек {в}, {20}, {Зв},... в интервал [О .. 1], в порядке их появления, причем первому отрезку присваивается номер 0. Докажите справедливость следующих утверждений. Интервал номер S длиной {t9}, где t = rqk + qk-i, О < г < Ок, к четно и О < s < д, имеет левую границу {sO} и правую границу {{s + i)}"""- Интервал номер s длиной 1 - {tO}, где t =

* Взгляните с этой точки зрения на полиномы i*--a;--a;--l и i*--a;*--a;*--i--i--a;--х +х° + х + х + х + x +х + + 1, определяющие CCITT CRC-16 и CRC-32 соответственно, и рассмотрите возможность использования CRC в качестве хеш-функции. - Прим. перев.