\input style
\chapno=6\subchno=3\chapnotrue

%%601

\subchap{їх°шЁютрэшх} % 6.4
фО СИХ ПОР МЫ РАССМАТРИВАЛИ МЕТОДЫ ПОИСКА, ОСНОВАННЫЕ НА СРАВНЕНИИ ДАННОГО
АРГУМЕНТА~$K$ С ИМЕЮЩИМИСЯ В ТАБЛИЦЕ КЛЮЧАМИ ИЛИ НА ИСПОЛЬЗОВАНИИ ЕГО
ЦИФР ДЛЯ УПРАВЛЕНИЯ ПРОЦЕССОМ РАЗВЕТВЛЕНИЯ. эО ЕСТЬ И ТРЕТИЙ ПУТЬ: НЕ
РЫСКАТЬ ВОКРУГ ДА ОКОЛО, А ПРОИЗВЕСТИ НАД~$K$ НЕКОТОРОЕ АРИФМЕТИЧЕСКОЕ
ВЫЧИСЛЕНИЕ И ПОЛУЧИТЬ ФУНКЦИЮ~$f(K)$, УКАЗЫВАЮЩУЮ АДРЕС В ТАБЛИЦЕ, ГДЕ
ХРАНИТСЯ~$K$ И АССОЦИИРОВАННАЯ С НИМ ИНФОРМАЦИЯ.

эАПРИМЕР, РАССМОТРИМ ВНОВЬ МНОЖЕСТВО ИЗ 31~АНГЛИЙСКОГО СЛОВА, КОТОРОЕ МЫ
ПОДВЕРГАЛИ ВОЗДЕЙСТВИЮ РАЗЛИЧНЫХ СТРАТЕГИИ ПОИСКА В П.~6.2.2 И \S~6.3.
ЄАБЛИЦА~1 СОДЕРЖИТ КОРОТКУЮ ПРОГРАММУ ДЛЯ \MIX, ПРЕОБРАЗУЮЩУЮ КАЖДЫЙ ИЗ
31~КЛЮЧА В УНИКАЛЬНОЕ ЧИСЛО~$f(K)$ МЕЖДУ~$-10$ И~$30$. хСЛИ МЫ СРАВНИМ
ЭТОТ МЕТОД С \MIX-ПРОГРАММАМИ ДЛЯ УЖЕ ИЗУЧЕННЫХ НАМИ МЕТОДОВ (НАПРИМЕР, С
БИНАРНЫМ ПОИСКОМ, ОПТИМАЛЬНЫМ ПОИСКОМ ПО ДЕРЕВУ, БОРОВОЙ ПАМЯТЬЮ,
ЦИФРОВЫМ ПОИСКОМ ПО ДЕРЕВУ), ТО УВИДИМ, ЧТО ОН ЛУЧШЕ КАК С ТОЧКИ ЗРЕНИЯ
ПРОСТРАНСТВА, ТАК И С ТОЧКИ ЗРЕНИЯ СКОРОСТИ; ТОЛЬКО БИНАРНЫЙ ПОИСК
ИСПОЛЬЗУЕТ НЕСКОЛЬКО МЕНЬШЕ ПРОСТРАНСТВА. т САМОМ ДЕЛЕ, ПРИ ИСПОЛЬЗОВАНИИ
ПРОГРАММЫ ИЗ ТАБЛ.~1 СРЕДНЕЕ ВРЕМЯ ПОИСКА СОСТАВЛЯЕТ ЛИШЬ
ОКОЛО~$17.8u$ (ДАННЫЕ О ЧАСТОТЕ ВЗЯТЫ ИЗ РИС.~12), И ДЛЯ ХРАНЕНИЯ
31~КЛЮЧА ТРЕБУЕТСЯ ТАБЛИЦА ВСЕГО ДЛЯ 41~ЭЛЕМЕНТА.

ъ СОЖАЛЕНИЮ, НАХОДИТЬ ПОДОБНЫЕ ФУНКЦИИ~$f(K)$ ДОВОЛЬНО СЛОЖНО. ёУЩЕСТВУЕТ
$41^{31}\approx10^{50}$~РАЗЛИЧНЫХ ОТОБРАЖЕНИЙ МНОЖЕСТВА ИЗ 31~ЭЛЕМЕНТА В
МНОЖЕСТВО ИЗ 41~ЭЛЕМЕНТА, И
ТОЛЬКО $41\cdot40\cdot\ldots\cdot11=41!/10!\approx10^{43}$ ИЗ НИХ ДАЮТ
РАЗЛИЧНЫЕ ЗНАЧЕНИЯ ДЛЯ КАЖДОГО АРГУМЕНТА; ТАКИМ ОБРАЗОМ, ЛИШЬ ОДНА ИЗ
КАЖДЫХ 10~МИЛЛИОНОВ ФУНКЦИЙ ОКАЗЫВАЕТСЯ ПОДХОДЯЩЕЙ.

ЇУНКЦИИ, ДАЮЩИЕ НЕПОВТОРЯЮЩИЕСЯ ЗНАЧЕНИЯ, НЕОЖИДАННО РЕДКИ ДАЖЕ В СЛУЧАЕ
ДОВОЛЬНО БОЛЬШОЙ ТАБЛИЦЫ. эАПРИМЕР, ЗНАМЕНИТЫЙ ПАРАДОКС ДНЕЙ РОЖДЕНИЯ
УТВЕРЖДАЕТ, ЧТО, ЕСЛИ В КОМНАТЕ ПРИСУТСТВУЕТ НЕ МЕНЕЕ 23~ЧЕЛОВЕК, ИМЕЕТСЯ
ХОРОШИЙ ШАНС НА ТО, ЧТО У ДВУХ ИЗ НИХ СОВПАДЕТ ДЕНЬ РОЖДЕНИЯ!
шНЫМИ СЛОВАМИ, ЕСЛИ МЫ ВЫБИРАЕМ СЛУЧАЙНУЮ ФУНКЦИЮ, ОТОБРАЖАЮЩУЮ 23~КЛЮЧА В
365-ЭЛЕМЕНТНУЮ ТАБЛИЦУ, ТО С ВЕРОЯТНОСТЬЮ~$0.4927$ (МЕНЕЕ ПОЛОВИНЫ) ВСЕ
КЛЮЧИ ПОПАДУТ В РАЗНЫЕ МЕСТА. ёКЕПТИКИ, СОМНЕВАЮЩИЕСЯ В ЭТОМ, МОГУТ
ПОПЫТАТЬСЯ НАЙТИ СОВПАДЕНИЕ ДНЕЙ РОЖДЕНИЯ НА БЛИЖАЙШЕЙ БОЛЬШОЙ ВЕЧЕРИНКЕ.
[яАРАДОКС ДНЕЙ РОЖДЕНИЯ ВПЕРВЫЕ УПОМЯНУТ В РАБОТАХ ФОН~ьИЗЕСА ({\sl Istanbul
%%602
\"Universitesi Fen Fak\"ultesi Mecmuasi,\/} {\bf 4} (1939), 145--163)
И~є.~ЇЕЛЛЕРА (тВЕДЕНИЕ В ТЕОРИЮ ВЕРОЯТНОСТЕЙ И ЕЕ ПРИЛОЖЕНИЯ, ь., "ьИР",
1964, ГЛ.~2, \S~3).]

ё ДРУГОЙ СТОРОНЫ, ПОДХОД, ИСПОЛЬЗОВАННЫЙ В ТАБЛ.~1, ДОВОЛЬНО ГИБКИЙ
[СР.~С~ь.~уРЕНЕВСКИ И~т.~ЄУРСКИ, {\sl CACM,\/} {\bf 6} (1963), 322--323],
И ДЛЯ ТАБЛИЦЫ СРЕДНЕГО РАЗМЕРА ПОДХОДЯЩУЮ ФУНКЦИЮ МОЖНО НАЙТИ ПРИМЕРНО
ЗА ДЕНЬ. т САМОМ ДЕЛЕ, ОЧЕНЬ ЗАНЯТНО РЕШАТЬ ПОДОБНЫЕ ГОЛОВОЛОМКИ.

ЁАЗУМЕЕТСЯ, ТАКОЙ МЕТОД ИМЕЕТ СУЩЕСТВЕННЫЙ НЕДОСТАТОК, ИБО СОДЕРЖИМОЕ
ТАБЛИЦЫ ДОЛЖНО БЫТЬ ИЗВЕСТНО ЗАРАНЕЕ; ДОБАВЛЕНИЕ ХОТЯ БЫ ОДНОГО КЛЮЧА
МОЖЕТ ВСЕ ИСПОРТИТЬ, И НАМ ПРИДЕТСЯ НАЧИНАТЬ ФАКТИЧЕСКИ НА ПУСТОМ МЕСТЕ.
ьОЖНО ПОЛУЧИТЬ ГОРАЗДО БОЛЕЕ ГИБКИЙ МЕТОД, ЕСЛИ ОТБРОСИТЬ ИДЕЮ
ОДНОЗНАЧНОСТИ, ДОПУСКАЯ СОВПАДЕНИЯ ЗНАЧЕНИЙ~$f(K)$ ДЛЯ РАЗЛИЧНЫХ
АРГУМЕНТОВ, И ИСПОЛЬЗОВАТЬ ОСОБЫЙ МЕТОД РАЗРЕШЕНИЯ НЕОПРЕДЕЛЕННОСТИ ПОСЛЕ
ВЫЧИСЛЕНИЯ~$f(K)$.

эАШИ РАССМОТРЕНИЯ ПРИВОДЯТ К ШИРОКО ИЗВЕСТНОМУ КЛАССУ МЕТОДОВ, ОБЫЧНО
НАЗЫВАЕМЫХ \dfn{ХЕШИРОВАНИЕМ} ИЛИ \dfn{РАССЕЯННОЙ ПАМЯТЬЮ.} рНГЛИЙСКИЙ
ГЛАГОЛ "to hash" ИМЕЕТ СМЫСЛ НАРЕЗАТЬ, РАСКРОШИТЬ ЧТО-ЛИБО ИЛИ СДЕЛАТЬ ИЗ
ЭТОГО МЕСИВО; ИДЕЯ ХЕШИРОВАНИЯ СОСТОИТ В ТОМ, ЧТОБЫ ВЗЯТЬ НЕКОТОРЫЕ
ХАРАКТЕРИСТИКИ КЛЮЧА И ИСПОЛЬЗОВАТЬ ПОЛУЧЕННУЮ ЧАСТИЧНУЮ ИНФОРМАЦИЮ
В КАЧЕСТВЕ ОСНОВЫ ПОИСКА. ьЫ ВЫЧИСЛЯЕМ \dfn{ХЕШ-ФУНКЦИЮ $h(K)$} И БЕРЕМ
ЭТО ЗНАЧЕНИЕ В КАЧЕСТВЕ АДРЕСА НАЧАЛА ПОИСКА.

яАРАДОКС ДНЕЙ РОЖДЕНИЯ СЛУЖИТ ДЛЯ НАС ПРЕДОСТЕРЕЖЕНИЕМ, ЧТО, ВЕРОЯТНО,
НАЙДУТСЯ РАЗЛИЧНЫЕ КЛЮЧИ~$K_i\ne K_j$, ДЛЯ КОТОРЫХ
%%603
$h(K_i)=h(K_j)$. яОДОБНОЕ СОБЫТИЕ НАЗЫВАЕТСЯ \dfn{КОЛЛИЗИЕЙ;} ДЛЯ
РАЗРЕШЕНИЯ КОЛЛИЗИЙ БЫЛИ РАЗРАБОТАНЫ ИНТЕРЕСНЫЕ ПОДХОДЫ. ўТОБЫ
ИСПОЛЬЗОВАТЬ РАССЕЯННУЮ ТАБЛИЦУ, ПРОГРАММИСТ ДОЛЖЕН ПРИНЯТЬ ДВА ПОЧТИ
НЕЗАВИСИМЫХ РЕШЕНИЯ: ОН ДОЛЖЕН ВЫБРАТЬ ХЕШ-ФУНКЦИЮ~$h(K)$ И МЕТОД
РАЗРЕШЕНИЯ КОЛЛИЗИЙ. ¤ТИ ДВА АСПЕКТА ЗАДАЧИ ПОИСКА МЫ И РАССМОТРИМ ПО ОЧЕРЕДИ.

\section їЕШ-ФУНКЦИИ. фЛЯ ОПРЕДЕЛЕННОСТИ НА ПРОТЯЖЕНИИ ЭТОГО ПУНКТА БУДЕТ
ПРЕДПОЛАГАТЬСЯ, ЧТО ХЕШ-ФУНКЦИЯ~$h$ ИМЕЕТ НЕ БОЛЕЕ $M$~РАЗЛИЧНЫХ ЗНАЧЕНИЙ
И ЧТО ЭТИ ЗНАЧЕНИЯ УДОВЛЕТВОРЯЮТ УСЛОВИЮ
$$
0\le h(K)<M
\eqno(1)
$$
ДЛЯ ВСЕХ КЛЮЧЕЙ~$K$. т РЕАЛЬНОМ ФАЙЛЕ МНОГО ПОЧТИ ОДИНАКОВЫХ КЛЮЧЕЙ,
ПОЭТОМУ ЖЕЛАТЕЛЬНО ВЫБРАТЬ ХЕШ-ФУНКЦИЮ, РАССЕИВАЮЩУЮ ИХ ПО ТАБЛИЦЕ. ¤ТО
ВАЖНО ДЛЯ УМЕНЬШЕНИЯ ЧИСЛА КОЛЛИЗИЙ.

ЄЕОРЕТИЧЕСКИ НЕВОЗМОЖНО ТАК ОПРЕДЕЛИТЬ ХЕШ-ФУНКЦИЮ, ЧТОБЫ ОНА СОЗДАВАЛА
СЛУЧАЙНЫЕ ДАННЫЕ ИЗ НЕСЛУЧАЙНЫХ РЕАЛЬНЫХ ФАЙЛОВ. эО НА ПРАКТИКЕ НЕТРУДНО
СДЕЛАТЬ ДОСТАТОЧНО ХОРОШУЮ ИМИТАЦИЮ СЛУЧАЙНОСТИ, ИСПОЛЬЗУЯ ПРОСТЫЕ
АРИФМЕТИЧЕСКИЕ ДЕЙСТВИЯ, ОБСУЖДАВШИЕСЯ В ГЛ.~3. эА САМОМ ДЕЛЕ МЫ МОЖЕМ
ПОСТУПИТЬ ДАЖЕ ЛУЧШЕ, ВЫЯВЛЯЯ НЕСЛУЧАЙНЫЕ СВОЙСТВА РЕАЛЬНЫХ ДАННЫХ И
СТРОЯ НА ИХ ОСНОВЕ ХЕШ-ФУНКЦИЮ, ДАЮЩУЮ МЕНЬШЕ КОЛЛИЗИЙ; ЧЕМ КОГДА ИМЕЮТСЯ
ИСТИННО СЛУЧАЙНЫЕ КЛЮЧИ.

ЁАССМОТРИМ, НАПРИМЕР, СЛУЧАЙ ДЕСЯТИЗНАЧНЫХ КЛЮЧЕЙ НА ДЕСЯТИЧНОМ КОМПЬЮТЕРЕ.
 ёАМ СОБОЙ НАПРАШИВАЕТСЯ СЛЕДУЮЩИЙ СПОСОБ ВЫБОРА ХЕШ-ФУНКЦИИ: ПОЛОЖИТЬ~$M$
РАВНЫМ, СКАЖЕМ, 1000,
%%604
А В КАЧЕСТВЕ~$h(K)$ ВЗЯТЬ ТРИ ЦИФРЫ, ВЫБРАННЫЕ ПРИМЕРНО ИЗ СЕРЕДИНЫ
20-ЗНАЧНОГО ПРОИЗВЕДЕНИЯ~$K\times K$. ъАЗАЛОСЬ БЫ, ЭТО ДОЛЖНО ДАВАТЬ
ДОВОЛЬНО РАВНОМЕРНОЕ РАСПРЕДЕЛЕНИЕ ЗНАЧЕНИЙ МЕЖДУ~$000$ И~$999$ С НИЗКОЙ
ВЕРОЯТНОСТЬЮ КОЛЛИЗИЙ. т САМОМ ДЕЛЕ, ЭКСПЕРИМЕНТЫ С РЕАЛЬНЫМИ ДАННЫМИ
ПОКАЗАЛИ, ЧТО ТАКОЙ МЕТОД "СЕРЕДИНЫ КВАДРАТА" НЕПЛОХ ПРИ УСЛОВИИ, ЧТО
КЛЮЧИ НЕ СОДЕРЖАТ МНОГО ЛЕВЫХ ИЛИ ПРАВЫХ НУЛЕЙ ПОДРЯД. тЫЯСНИЛОСЬ, ОДНАКО,
ЧТО СУЩЕСТВУЮТ БОЛЕЕ НАДЕЖНЫЕ И ПРОСТЫЕ СПОСОБЫ, ПОДОБНО ТОМУ КАК В ГЛ.~3
МЕТОД СЕРЕДИНЫ КВАДРАТА ОКАЗАЛСЯ НЕ СЛИШКОМ ХОРОШИМ ДАТЧИКОМ СЛУЧАЙНЫХ ЧИСЕЛ.

ьНОГОЧИСЛЕННЫЕ ПРОВЕРКИ РЕАЛЬНЫХ ФАЙЛОВ ВЫЯВИЛИ ОЧЕНЬ ХОРОШУЮ РАБОТУ ДВУХ
ОСНОВНЫХ ТИПОВ ХЕШ-ФУНКЦИЙ. юДИН ИЗ НИХ ОСНОВАН НА ДЕЛЕНИИ, А ДРУГОЙ НА
УМНОЖЕНИИ.

ьЕТОД ДЕЛЕНИЯ ОСОБЕННО ПРОСТ: ИСПОЛЬЗУЕТСЯ ОСТАТОК ОТ ДЕЛЕНИЯ НА~$M$
$$
h(K)=K\bmod M.
\eqno(2)
$$
т ЭТОМ СЛУЧАЕ, ОЧЕВИДНО, НЕКОТОРЫЕ ЗНАЧЕНИЯ~$M$ МНОГО ЛУЧШЕ ДРУГИХ.
эАПРИМЕР, ЕСЛИ $M$---ЧЕТНОЕ ЧИСЛО, ТО ЗНАЧЕНИЕ~$h(K)$ БУДЕТ ЧЕТНЫМ ПРИ
ЧЕТНОМ~$K$ И НЕЧЕТНЫМ В ПРОТИВНОМ СЛУЧАЕ; ЧАСТО ЭТО ПРИВОДИТ К
ЗНАЧИТЕЛЬНЫМ СМЕЩЕНИЯМ ДАННЫХ. ёОВСЕМ ПЛОХО БРАТЬ~$M$ РАВНЫМ СТЕПЕНИ
ОСНОВАНИЯ СИСТЕМЫ СЧИСЛЕНИЯ ¤ть, ТАК КАК ТОГДА $h(K)$~ДАЕТ НАМ ПРАВЫЕ
ЗНАЧАЩИЕ ЦИФРЫ~$K$ ($K \bmod M$ НЕ ЗАВИСИТ ОТ ДРУГИХ ЦИФР). рНАЛОГИЧНО,
$M$ НЕ ДОЛЖНО БЫТЬ КРАТНО~$3$, ИБО БУКВЕННЫЕ КЛЮЧИ, ОТЛИЧАЮЩИЕСЯ ДРУГ ОТ
ДРУГА ЛИШЬ ПОРЯДКОМ БУКВ, МОГЛИ БЫ ДАТЬ ЗНАЧЕНИЯ ФУНКЦИИ, РАЗНОСТЬ МЕЖДУ
КОТОРЫМИ КРАТНА~$3$. (яРИЧИНА КРОЕТСЯ В ТОМ,
ЧТО~$10^n \bmod 3= 4^n \bmod 3= 1$.) тООБЩЕ МЫ ХОТЕЛИ БЫ ИЗБЕЖАТЬ
ЗНАЧЕНИЙ~$M$, ДЕЛЯЩИХ~$r^k\pm a$, ГДЕ $k$ И~$a$---НЕБОЛЬШИЕ ЧИСЛА, А
$r$---"ОСНОВАНИЕ СИСТЕМЫ СЧИСЛЕНИЯ" ДЛЯ МНОЖЕСТВА ИСПОЛЬЗУЕМЫХ ЛИТЕР
(ОБЫЧНО $r=64$, 256 И~100), ТАК КАК ОСТАТОК ОТ ДЕЛЕНИЯ НА ТАКИЕ
ЗНАЧЕНИЯ~$M$ ОБЫЧНО ОКАЗЫВАЮТСЯ ПРОСТОЙ СУПЕРПОЗИЦИЕЙ ЦИФР КЛЮЧА. эАШИ
РАССМОТРЕНИЯ ПОДСКАЗЫВАЮТ, ЧТО ЛУЧШЕ ВСЕГО \emph{ВЗЯТЬ В КАЧЕСТВЕ~$M$
ТАКОЕ ПРОСТОЕ ЧИСЛО,} ЧТОБЫ~$r^k\not\equiv \pm a \pmod{M}$ ПРИ
НЕБОЛЬШИХ~$k$ И~$a$. яРАКТИЧЕСКИ ВО ВСЕХ СЛУЧАЯХ,  ЭТОТ ВЫБОР ОКАЗЫВАЕТСЯ
ВПОЛНЕ УДОВЛЕТВОРИТЕЛЬНЫМ.

эАПРИМЕР, НА МАШИНЕ~\MIX\ МОЖНО ПОЛОЖИТЬ~$M=1009$, ВЫЧИСЛЯЯ~$h (K)$
СЛЕДУЮЩИМ ОБРАЗОМ:
$$
\mixcode
LDX  &K      & $|rX|\asg K$.
ENTA &0      & $|rA|\asg 0$.
DIV  &=1009= & $|rA|\asg K \bmod 1009$.
\endmixcode
\eqno(3)
$$

ьУЛЬТИПЛИКАТИВНУЮ СХЕМУ ХЕШИРОВАНИЯ ТАКЖЕ ЛЕГКО РЕАЛИЗОВАТЬ, НО
НЕСКОЛЬКО ТРУДНЕЕ ОПИСАТЬ, ТАК КАК НУЖНО ПРЕДСТАВИТЬ, ЧТО МЫ РАБОТАЕМ С
ДРОБЯМИ, А НЕ С ЦЕЛЫМИ ЧИСЛАМИ. яУСТЬ $w$~ЕСТЬ РАЗМЕР МАШИННОГО СЛОВА
(ДЛЯ \MIX{} ЭТО ЗНАЧЕНИЕ ОБЫЧНО
%%605
РАВНО~$10^{10}$ ИЛИ~$2^{30}$); ЦЕЛОЕ ЧИСЛО~$A$ МОЖНО РАССМАТРИВАТЬ КАК
ДРОБЬ~$A/w$, ЕСЛИ МЫСЛЕННО ПОСТАВИТЬ ДЕСЯТИЧНУЮ (ИЛИ ДВОИЧНУЮ) ТОЧКУ СЛЕВА
ОТ МАШИННОГО СЛОВА, В КОТОРОМ ЗАПИСАНО~$A$. ьЕТОД СОСТОИТ В ТОМ, ЧТОБЫ
ВЫБРАТЬ~$A$ ВЗАИМНО ПРОСТЫМ С~$w$ И ПОЛОЖИТЬ
$$
h(K)=\floor{M\left(\left({A\over w} K\right)\bmod 1\right)}.
\eqno(4)
$$
эА ДВОИЧНОЙ~¤ть  $M$~ОБЫЧНО БЕРУТ РАВНЫМ СТЕПЕНИ ДВОЙКИ, ТАК ЧТО
$h(K)$~СОСТОИТ ИЗ СТАРШИХ БИТОВ ПРАВОЙ ЗНАЧАЩЕЙ ПОЛОВИНЫ ПРОИЗВЕДЕНИЯ~$AK$.

эА ДВОИЧНОЙ ВЕРСИИ МАШИНЫ~\MIX{} ПРИ~$M=2^m$ МУЛЬТИПЛИКАТИВНАЯ
ХЕШ-ФУНКЦИЯ ВЫЧИСЛЯЕТСЯ ТАК:
$$
\mixcode
LDA  & K & $|rA|\asg K$.
MUL & A & $|rAX|\asg AK$.
ENTA& 0 & $|rAX|\asg AK \bmod w$.
SLB   & m & ёДВИГ |rAX| НА $m$~БИТОВ ВЛЕВО.
\endmixcode
\eqno(5)
$$
ЁЕЗУЛЬТАТ ПОЛУЧАЕТСЯ В РЕГИСТРЕ~|A|. \MIX{} ИМЕЕТ ДОВОЛЬНО МЕДЛЕННЫЕ
КОМАНДЫ УМНОЖЕНИЯ И СДВИГА, ПОЭТОМУ~(5) И~(3) ЗАТРАЧИВАЮТ ОДИНАКОВОЕ
ВРЕМЯ; ОДНАКО НА МНОГИХ МАШИНАХ УМНОЖЕНИЕ ЗНАЧИТЕЛЬНО БЫСТРЕЕ ДЕЛЕНИЯ.

т СУЩНОСТИ, ЭТОТ МЕТОД МОЖНО РАССМАТРИВАТЬ КАК ОБОБЩЕНИЕ~(3), ПОСКОЛЬКУ
МЫ МОГЛИ БЫ, НАПРИМЕР, ВЗЯТЬ В КАЧЕСТВЕ~$A$ ПРИБЛИЖЕНИЕ К~$w/1009$;
УМНОЖЕНИЕ НА ОБРАТНУЮ ВЕЛИЧИНУ ЧАСТО ОКАЗЫВАЕТСЯ БЫСТРЕЕ ДЕЛЕНИЯ. чАМЕТИМ,
ЧТО (5)~ПОЧТИ СОВПАДАЕТ С МЕТОДОМ СЕРЕДИНЫ КВАДРАТА, ОДНАКО ИМЕЕТСЯ ОДНО
ВАЖНОЕ ОТЛИЧИЕ: В ДАЛЬНЕЙШЕМ МЫ УВИДИМ, ЧТО УМНОЖЕНИЕ НА
ПОДХОДЯЩУЮ КОНСТАНТУ ИМЕЕТ МНОГО ПОЛЕЗНЫХ СВОЙСТВ.

юДНА ИЗ ПРИВЛЕКАТЕЛЬНЫХ ЧЕРТ МУЛЬТИПЛИКАТИВНОЙ СХЕМЫ СОСТОИТ В ТОМ, ЧТО
В~(5) НЕ ПРОИСХОДИТ ПОТЕРИ ИНФОРМАЦИИ; МЫ МОГЛИ БЫ ВНОВЬ НАЙТИ~$K$, ЗНАЯ
ЛИШЬ СОДЕРЖИМОЕ~$|rAX|$ ПОСЛЕ ВЫПОЛНЕНИЯ ИНСТРУКЦИЙ~(5). фЕЛО В ТОМ, ЧТО
$A$~ВЗАИМНО ПРОСТО С~$w$, И ПРИ ПОМОЩИ АЛГОРИТМА хВКЛИДА МОЖНО НАЙТИ
КОНСТАНТУ~$A'$:~$AA'\bmod w=1$; ОТСЮДА СЛЕДУЕТ,
ЧТО~$K=(A' (AK \bmod w)) \bmod w$. шНЫМИ СЛОВАМИ, ЕСЛИ ОБОЗНАЧИТЬ
ЧЕРЕЗ~$f(K)$ СОДЕРЖИМОЕ РЕГИСТРА~$X$ ПЕРЕД ВЫПОЛНЕНИЕМ ИНСТРУКЦИИ~|SLB|
В~(5), ТО
$$
K_1\ne K_2 \hbox{ ВЛЕЧЕТ } f(K_1)\ne f(K_2).
\eqno(6)
$$
ъОНЕЧНО, $f(K)$~ПРИНИМАЕТ ЗНАЧЕНИЯ В ДИАПАЗОНЕ ОТ~0 ДО~$w-1$ И НЕ ЯВЛЯЕТСЯ
СКОЛЬКО-НИБУДЬ ПОДХОДЯЩЕЙ ХЕШ-ФУНКЦИЕЙ, НО ОНА МОЖЕТ БЫТЬ ОЧЕНЬ ПОЛЕЗНОЙ В
КАЧЕСТВЕ \dfn{РАССЕИВАЮЩЕЙ ФУНКЦИИ}, А ИМЕННО ФУНКЦИИ,
УДОВЛЕТВОРЯЮЩЕЙ~(6) И ОБЫЧНО ПРИВОДЯЩЕЙ К РАНДОМИЗАЦИИ КЛЮЧЕЙ. эАПРИМЕР,
ЕЕ ОЧЕНЬ ХОРОШО ИСПОЛЬЗОВАТЬ В СОЧЕТАНИИ С АЛГОРИТМАМИ ПОИСКА ПО ДЕРЕВУ
ИЗ П.~6.2.2, ЕСЛИ ПОРЯДОК КЛЮЧЕЙ НАМ БЕЗРАЗЛИЧЕН, ТАК КАК ОНА
УСТРАНЯЕТ ОПАСНОСТЬ ВЫРОЖДЕНИЯ ДЕРЕВА ПРИ ПОСТУПЛЕНИИ КЛЮЧЕЙ В ВОЗРАСТАЮЩЕМ
%%606
ПОРЯДКЕ. ЁАССЕИВАЮЩАЯ ФУНКЦИЯ ПОЛЕЗНА ТАКЖЕ В СВЯЗИ С
АЛГОРИТМАМИ ЦИФРОВОГО ПОИСКА ПО ДЕРЕВУ ИЗ \S~6.3, ЕСЛИ БИТЫ ИСТИННЫХ
КЛЮЧЕЙ ИМЕЮТ СМЕЩЕНИЕ.

фРУГАЯ ЧЕРТА МУЛЬТИПЛИКАТИВНОГО МЕТОДА ХЕШИРОВАНИЯ СОСТОИТ В ТОМ, ЧТО ОН
ХОРОШО ИСПОЛЬЗУЕТ НЕСЛУЧАЙНЫЕ СВОЙСТВА, КОТОРЫЕ ОБНАРУЖИВАЮТСЯ ВО МНОГИХ
ФАЙЛАХ. ўАСТО МНОЖЕСТВА ИСТИННЫХ КЛЮЧЕЙ СОДЕРЖАТ АРИФМЕТИЧЕСКИЕ ПРОГРЕССИИ
$\set{K, K+d, K+2d,~\ldots, K+td}$, НАПРИМЕР
ИМЕНА~$\set{|PART1|,\ |PART2|,\ |PART3|}$
ИЛИ~$\set{|TYPEA|,\ |TYPEB|,\ |TYPEC|}$. ьУЛЬТИПЛИКАТИВНЫЙ МЕТОД,
ХЕШИРОВАНИЯ ПРЕОБРАЗУЕТ АРИФМЕТИЧЕСКИЕ ПРОГРЕССИИ В ПРИБЛИЖЕННЫЕ
\picture{ЁИС. 37. ЇИБОНАЧЧИЕВО ХЕШИРОВАНИЕ.}
АРИФМЕТИЧЕСКИЕ ПРОГРЕССИИ~$h(K)$, $h(K+d)$, $h(K+2d)$,~\dots{}
НЕСОВПАДАЮЩИХ ВЕЛИЧИН, УМЕНЬШАЯ ТЕМ САМЫМ ЧИСЛО КОЛЛИЗИЙ ПО СРАВНЕНИЮ СО
СЛУЧАЙНОЙ СИТУАЦИЕЙ. ьЕТОД ДЕЛЕНИЯ ОБЛАДАЕТ ТАКИМ ЖЕ СВОЙСТВОМ.

ЁИСУНОК~37 ИЛЛЮСТРИРУЕТ ЭТОТ АСПЕКТ МУЛЬТИПЛИКАТИВНОГО ХЕШИРОВАНИЯ В
ОСОБЕННО ИНТЕРЕСНОМ СЛУЧАЕ. яРЕДПОЛОЖИМ, ЧТО $A/w$~ПРИБЛИЖЕННО РАВНО
ЗОЛОТОМУ
СЕЧЕНИЮ~$\phi^{-1}=(\sqrt{5}-1)/2=0.6180339887$; ПОВЕДЕНИЕ
ПОСЛЕДОВАТЕЛЬНЫХ ЗНАЧЕНИЙ~$h(K)$, $h(K+1)$, $h(K+2)$,~\dots{} МОЖНО ИЗУЧАТЬ,
РАССМАТРИВАЯ ПОВЕДЕНИЕ ВЕЛИЧИН~$h(0)$, $h(1)$, $h(2)$,~\dots{} ¤ТО НАВОДИТ
НАС НА МЫСЛЬ ПРОВЕСТИ ТАКОЙ ЭКСПЕРИМЕНТ: БЕРЕТСЯ ОТРЕЗОК~$[0, 1]$, НА
КОТОРОМ ПОСЛЕДОВАТЕЛЬНО ОТМЕЧАЮТСЯ ТОЧКИ~$\{\phi^{-1}\}$, $\{2\phi^{-1}\}$,
$\{3\phi^{-1}\}$,~\dots,  ГДЕ $\{x\}$~ОБОЗНАЧАЕТ ДРОБНУЮ ЧАСТЬ
ЧИСЛА~($\{x\}=x-\floor{x}=x\bmod1$). ъАК ПОКАЗАНО НА РИС.~37, ЭТИ ТОЧКИ
РАСПОЛОЖЕНЫ НЕ СЛИШКОМ БЛИЗКО ДРУГ К ДРУГУ; КАЖДАЯ ВНОВЬ ДОБАВЛЯЕМАЯ ТОЧКА
%%607
ПОПАДАЕТ В ОДИН ИЗ НАИБОЛЬШИХ ОСТАВШИХСЯ ИНТЕРВАЛОВ И ДЕЛИТ ЕГО ЗОЛОТЫМ
СЕЧЕНИЕМ! [¤ТО ЯВЛЕНИЕ БЫЛО ВПЕРВЫЕ ЗАМЕЧЕНО ▀.~юДЕРФЕЛЬДОМ И ДОКАЗАНО
ё.~ёВЕРЧКОВСКИ, {\sl Fundamenta Math.,\/} {\bf 46} (1958), 187--189.
тАЖНУЮ РОЛЬ В ДОКАЗАТЕЛЬСТВЕ ИГРАЮТ ЧИСЛА ЇИБОНАЧЧИ.]

¤ТО ЗАМЕЧАТЕЛЬНОЕ СВОЙСТВО ЗОЛОТОГО СЕЧЕНИЯ В ДЕЙСТВИТЕЛЬНОСТИ ЯВЛЯЕТСЯ
ЧАСТНЫМ СЛУЧАЕМ ОЧЕНЬ ОБЩЕЙ ТЕОРЕМЫ, ПРЕДУГАДАННОЙ уУГО °ТЕЙНГАУЗОМ И
ДОКАЗАННОЙ тЕРОЙ ЄУРАН °ОШ [{\sl Acta Math.\ Acad.\ Sci.\ Hung.,\/} {\bf
8} (1957), 461--471;
{\sl Ann.\ Univ.\ Sci.\ Budapest.\ E\"otv\"os Sect. Math.,\/} {\bf 1}
(1958), 127--134]:

\proclaim ЄЕОРЕМА S. яУСТЬ $\theta$---ЛЮБОЕ ИРРАЦИОНАЛЬНОЕ ЧИСЛО. хСЛИ
ПОМЕСТИТЬ НА ОТРЕЗОК~$[0, 1]$ ТОЧКИ~$\{\theta\}$, $\{2\theta\}$,~\dots,
$\{n\theta\}$, ТО ДЛИНЫ ПОЛУЧИВШИХСЯ ОТРЕЗКОВ БУДУТ ВЫРАЖАТЬСЯ НЕ БОЛЕЕ
ЧЕМ ТРЕМЯ РАЗЛИЧНЫМИ ЧИСЛАМИ. ъРОМЕ ТОГО, СЛЕДУЮЩАЯ
ТОЧКА~$\{(n+1)\theta\}$ ПОПАДЕТ В ОДИН ИЗ ОТРЕЗКОВ НАИБОЛЬШЕЙ ДЛИНЫ.\endmark

\noindent ЄАКИМ ОБРАЗОМ, ТОЧКИ~$\{\theta\}$, $\{2\theta\}$,~\dots,
$\{n\theta\}$ РАСПОЛАГАЮТСЯ МЕЖДУ~0 И~1 ОЧЕНЬ РАВНОМЕРНО. ЄЕОРЕМА ВЕРНА И
ДЛЯ РАЦИОНАЛЬНЫХ~$\{\theta\}$, ЕСЛИ ДАТЬ ПОДХОДЯЩУЮ ТРАКТОВКУ ОТРЕЗКОВ
НУЛЕВОЙ ДЛИНЫ, ОБРАЗУЮЩИХСЯ ПРИ~$n$, БОЛЬШЕМ ИЛИ РАВНОМ
ЗНАМЕНАТЕЛЮ~$\{\theta\}$. фОКАЗАТЕЛЬСТВО ТЕОРЕМЫ~S ВМЕСТЕ С ПОДРОБНЫМ
АНАЛИЗОМ ВОЗНИКАЮЩЕЙ СИТУАЦИИ ПРИВОДИТСЯ В УПР.~8. юКАЗЫВАЕТСЯ, ЧТО
ОТРЕЗКИ ДАННОЙ ДЛИНЫ СОЗДАЮТСЯ И РАЗРУШАЮТСЯ В ПОРЯДКЕ
"ПЕРВЫМ ВКЛЮЧАЕТСЯ---ПЕРВЫМ ИСКЛЮЧАЕТСЯ". ъОНЕЧНО, НЕКОТОРЫЕ
ЗНАЧЕНИЯ~$\{\theta\}$ ПРЕДПОЧТИТЕЛЬНЕЕ ДРУГИХ; НАПРИМЕР, ЕСЛИ
ВЗЯТЬ~$\{\theta\}$ БЛИЗКИМ К~0 ИЛИ~1, ТО СНАЧАЛА ОБРАЗУЕТСЯ МНОГО
МАЛЕНЬКИХ ОТРЕЗКОВ И ОДИН БОЛЬШОЙ. т УПР.~9 ПОКАЗАНО, ЧТО ДВА
ЧИСЛА~$\phi^{-1}$ И~$\phi^{-2}=1-\phi^{-1}$ ПРИВОДЯТ К "НАИБОЛЕЕ
РАВНОМЕРНО РАСПРЕДЕЛЕННЫМ" ПОСЛЕДОВАТЕЛЬНОСТЯМ СРЕДИ ВСЕХ~$\{\theta\}$
ОТ~0 ДО~1.

яРИВЕДЕННЫЕ РАССУЖДЕНИЯ ПОДВОДЯТ НАС К \dfn{ФИБОНАЧЧИЕВУ ХЕШИРОВАНИЮ,}
КОГДА В КАЧЕСТВЕ~$A$ БЕРЕТСЯ БЛИЖАЙШЕЕ К~$\phi^{-1}w$ ЦЕЛОЕ ЧИСЛО, ВЗАИМНО
ПРОСТОЕ С~$w$. эАПРИМЕР, ЕСЛИ БЫ \MIX{} БЫЛА ДЕСЯТИЧНОЙ ¤ть, МОЖНО БЫЛО ВЗЯТЬ
\picture{ЁИС. СТР. 607}
¤ТОТ МНОЖИТЕЛЬ ОЧЕНЬ ХОРОШО РАССЕЕТ КЛЮЧИ ВРОДЕ |LIST1|, |LIST2|, |LIST3|.
яОСМОТРИМ, ОДНАКО, ЧТО ПРОИЗОЙДЕТ, ЕСЛИ ВОЗРАСТАНИЕ ПОСЛЕДОВАТЕЛЬНОСТИ
ПРОИСХОДИТ В ЧЕТВЕРТОЙ ПОЗИЦИИ, КАК В КЛЮЧАХ |SUM1\]|~, |SUM2\]|~, |SUM3\]|~:
КАРТИНА БУДЕТ ТАКОЙ, КАК ЕСЛИ БЫ ТЕОРЕМА~S ИСПОЛЬЗОВАЛАСЬ
С~$\theta=\{100A/w\}=0.80339887$ ВМЕСТО~$\theta=0.6180339887=A/w$.
ЁЕЗУЛЬТИРУЮЩЕЕ ПОВЕДЕНИЕ, ОДНАКО, БУДЕТ ДОСТАТОЧНО ХОРОШИМ, НЕСМОТРЯ НА ТО
ЧТО ЭТО ЗНАЧЕНИЕ~$\theta$ ХУЖЕ~$\phi^{-1}$. хСЛИ ЖЕ ВОЗРАСТАНИЕ ПРОИСХОДИТ
%%608
ВО ВТОРОЙ ПОЗИЦИИ, КАК В КЛЮЧАХ |A1\]\]\]|~, |A2\]\]\]|~, |A3\]\]\]|~, ТО
ИСТИННОЕ ЗНАЧЕНИЕ~$\theta=0.9887$; ПОЖАЛУЙ, ЭТО СЛИШКОМ БЛИЗКО
К~1. яОЭТОМУ, МОЖЕТ БЫТЬ, ЛУЧШЕ ВМЕСТО~(7) ВЗЯТЬ В КАЧЕСТВЕ МНОЖИТЕЛЯ
\picture{ЁИС. СТР. 608}
яОДОБНЫЙ МНОЖИТЕЛЬ РАЗДЕЛИТ ПОСЛЕДОВАТЕЛЬНЫЕ КЛЮЧИ, РАЗЛИЧАЮЩИЕСЯ В
\emph{ЛЮБОЙ} ПОЗИЦИИ. ъ СОЖАЛЕНИЮ, ЭТОТ ВЫБОР СТРАДАЕТ ДРУГИМ ПОРОКОМ,
АНАЛОГИЧНЫМ ДЕЛИМОСТИ~$r^k\pm1$: КЛЮЧИ ВРОДЕ~|XY| И~|YX| ПОПАДУТ В ОДНО И
ТО ЖЕ МЕСТО! юДИН ИЗ СПОСОБОВ ПРЕОДОЛЕНИЯ ВОЗНИКАЮЩЕЙ ТРУДНОСТИ СОСТОИТ В
БОЛЕЕ ПРИСТАЛЬНОМ ИЗУЧЕНИИ СИТУАЦИИ, ЛЕЖАЩЕЙ В ОСНОВЕ ТЕОРЕМЫ~S. фЛЯ
КОРОТКИХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ КЛЮЧЕЙ ИМЕЮТ ЗНАЧЕНИЕ ЛИШЬ НЕСКОЛЬКО ПЕРВЫХ
НЕПОЛНЫХ ЧАСТНЫХ РАЗЛОЖЕНИЯ~$\theta$ В НЕПРЕРЫВНУЮ ДРОБЬ; МАЛОСТЬ
НЕПОЛНЫХ ЧАСТНЫХ СООТВЕТСТВУЕТ ХОРОШИМ СВОЙСТВАМ РАСПРЕДЕЛЕНИЯ. яОЭТОМУ
НАИЛУЧШИЕ ЗНАЧЕНИЯ~$\theta$ ВЫБИРАЮТСЯ ИЗ ИНТЕРВАЛОВ
$$
{1\over 4} <\theta<{3\over10},\quad
{1\over 3} <\theta<{3\over7},\quad
{4\over 7} <\theta<{2\over3},\quad
{7\over10} <\theta<{3\over4}.
$$
т КАЧЕСТВЕ~$A$ МОЖНО ВЗЯТЬ ТАКОЕ ЗНАЧЕНИЕ, ЧТОБЫ КАЖДЫЙ ИЗ ЕГО БАЙТОВ
ЛЕЖАЛ В ХОРОШЕМ ДИАПАЗОНЕ И НЕ БЫЛ СЛИШКОМ БЛИЗОК К ЗНАЧЕНИЯМ ДРУГИХ
БАЙТОВ ИЛИ ИХ ДОПОЛНЕНИЯМ, НАПРИМЕР
\picture{ЁИС. СТР. 608}
ЄАКОЙ МНОЖИТЕЛЬ МОЖНО РЕКОМЕНДОВАТЬ. (шЗЛОЖЕННЫЕ ИДЕИ В ОСНОВНОМ
ПРИНАДЛЕЖАТ Ё. ЇЛОЙДУ.)

їОРОШАЯ ХЕШ-ФУНКЦИЯ ДОЛЖНА УДОВЛЕТВОРЯТЬ ДВУМ ТРЕБОВАНИЯМ:
\medskip
\item{a)}~ЕЕ ВЫЧИСЛЕНИЕ ДОЛЖНО БЫТЬ ОЧЕНЬ БЫСТРЫМ;
\item{b)}~ОНА ДОЛЖНА МИНИМИЗИРОВАТЬ ЧИСЛО КОЛЛИЗИЙ.
\medskip
\noindent ёВОЙСТВО~(a) ОТЧАСТИ ЗАВИСИТ ОТ ОСОБЕННОСТЕЙ МАШИНЫ, А
СВОЙСТВО~(b)---ОТ ХАРАКТЕРА ДАННЫХ. хСЛИ БЫ КЛЮЧИ БЫЛИ
ДЕЙСТВИТЕЛЬНО СЛУЧАЙНЫМИ, МОЖНО БЫЛО БЫ ПРОСТО ВЫДЕЛИТЬ НЕСКОЛЬКО БИТОВ И
ИСПОЛЬЗОВАТЬ ИХ ДЛЯ ХЕШ-ФУНКЦИИ, НО НА ПРАКТИКЕ, ЧТОБЫ УДОВЛЕТВОРИТЬ~(b),
ПОЧТИ ВСЕГДА НУЖНА ФУНКЦИЯ, ЗАВИСЯЩАЯ ОТ ВСЕХ БИТОВ.

фО СИХ ПОР МЫ РАССМАТРИВАЛИ ХЕШИРОВАНИЕ КЛЮЧЕЙ, СОСТОЯЩИХ ИЗ ОДНОГО
СЛОВА. ё КЛЮЧАМИ, СОСТОЯЩИМИ ИЗ НЕСКОЛЬКИХ СЛОВ ИЛИ ИМЕЮЩИМИ ПЕРЕМЕННУЮ
ДЛИНУ, МОЖНО РАБОТАТЬ КАК
%%609
С ПРЕДСТАВЛЕННЫМИ С МНОГОКРАТНОЙ ТОЧНОСТЬЮ ЧИСЛАМИ И ПРИМЕНИТЬ К НИМ
РАССМОТРЕННЫЕ МЕТОДЫ. юДНАКО ОБЫЧНО ОКАЗЫВАЕТСЯ ДОСТАТОЧНОЙ БОЛЕЕ БЫСТРАЯ
ПРОЦЕДУРА, КОГДА ОТДЕЛЬНЫЕ СЛОВА СНАЧАЛА КОМБИНИРУЮТСЯ В ОДНО, А ЗАТЕМ
ПРОИЗВОДИТСЯ ЕДИНСТВЕННОЕ УМНОЖЕНИЕ ИЛИ ДЕЛЕНИЕ. фЛЯ КОМБИНИРОВАНИЯ
МОЖНО ИСПОЛЬЗОВАТЬ СЛОЖЕНИЕ ПО МОДУЛЮ~$w$ ИЛИ ОПЕРАЦИЮ "ИСКЛЮЧАЮЩЕЕ ИЛИ"
(НА ДВОИЧНЫХ ¤ть). фОСТОИНСТВОМ ОБЕИХ ОПЕРАЦИЙ ЯВЛЯЕТСЯ ИХ ОБРАТИМОСТЬ,
Т.~Е.~ИХ РЕЗУЛЬТАТ ЗАВИСИТ ОТ ВСЕХ БИТОВ АРГУМЕНТОВ, ПРИЧЕМ "ИСКЛЮЧАЮЩЕЕ
ИЛИ" ИНОГДА ПРЕДПОЧТИТЕЛЬНЕЕ, ТАК КАК НЕ МОЖЕТ ПРИВЕСТИ К
АРИФМЕТИЧЕСКОМУ ПЕРЕПОЛНЕНИЮ. чАМЕТИМ, ЧТО ОБЕ ОПЕРАЦИИ КОММУТАТИВНЫ,
ПОЭТОМУ КЛЮЧИ~$(X, Y)$ И~$(Y, X)$ БУДУТ "БРОШЕНЫ" ПО ОДНОМУ АДРЕСУ. ўТОБЫ
ИЗБЕЖАТЬ ЭТОГО, у.~ф.~ъНОТТ ПРЕДЛОЖИЛ ПРЕДВАРИТЕЛЬНО ДЕЛАТЬ ЦИКЛИЧЕСКИЙ СДВИГ.

сЫЛО ПРИДУМАНО МНОГО ДРУГИХ МЕТОДОВ ХЕШИРОВАНИЯ, НО НИ ОДИН ИЗ НИХ НЕ
ОКАЗАЛСЯ ПРЕДПОЧТИТЕЛЬНЕЕ ОПИСАННЫХ ВЫШЕ ПРОСТЫХ СХЕМ ДЕЛЕНИЯ И УМНОЖЕНИЯ.
юБЗОР НЕКОТОРЫХ МЕТОДОВ И ИХ ПОДРОБНЫЕ СТАТИСТИЧЕСКИЕ ХАРАКТЕРИСТИКИ ПРИ
РАБОТЕ С РЕАЛЬНЫМИ ФАЙЛАМИ МОЖНО НАЙТИ В СТАТЬЕ
[V.~Y.~Lum, Ё.~S.~Є.~Yuen, M.~Dodd, {\sl CACM,\/} {\bf 14} (1971), 228--239].

шЗ ДРУГИХ ИСПЫТАННЫХ МЕТОДОВ ХЕШИРОВАНИЯ, ПОЖАЛУЙ, НАИБОЛЕЕ ИНТЕРЕСНЫМ
ЯВЛЯЕТСЯ СПОСОБ, ОСНОВАННЫЙ НА АЛГЕБРАИЧЕСКОЙ ТЕОРИИ КОДИРОВАНИЯ. шДЕЯ
АНАЛОГИЧНА МЕТОДУ ДЕЛЕНИЯ, ТОЛЬКО ВМЕСТО ДЕЛЕНИЯ НА ЦЕЛОЕ ЧИСЛО
ИСПОЛЬЗУЕТСЯ ДЕЛЕНИЕ НА МНОГОЧЛЕН ПО МОДУЛЮ~2. (ъАК БЫЛО ЗАМЕЧЕНО В \S~4.6,
 ЭТА ОПЕРАЦИЯ ПРЕДСТАВЛЯЕТ СОБОЙ АНАЛОГ ДЕЛЕНИЯ, ТАК ЖЕ КАК
СЛОЖЕНИЕ---АНАЛОГ "ИСКЛЮЧАЮЩЕГО ИЛИ".) фЛЯ ПРЕДЛАГАЕМОГО МЕТОДА $M$~ДОЛЖНО
БЫТЬ СТЕПЕНЬЮ~2: $M=2^m$; КРОМЕ ТОГО, ИСПОЛЬЗУЕТСЯ МНОГОЧЛЕН
$m\hbox{-Й}$~СТЕПЕНИ $P(x)=x^m+p_{m-1}x^{m-1}+\cdots+p_0$. фВОИЧНЫЙ
КЛЮЧ~$K=(k_{n-1}\ldots{}k_1k_0)_2$ МОЖНО РАССМАТРИВАТЬ КАК
МНОГОЧЛЕН~$K(x)=k_{n-1}x^{n-1}+\cdots+k_1x+k_0$, И ВЫЧИСЛИТЬ
ОСТАТОК~$K(x) \bmod P(x) = h_{m-1}x^{m-1}+\cdots+h_1x+h_0$,
ИСПОЛЬЗУЯ ПОЛИНОМИАЛЬНУЮ АРИФМЕТИКУ ПО МОДУЛЮ~2:
$h(K)=(h_{m-1}\ldots{}h_1h_0)_2$. яРИ ПРАВИЛЬНОМ ВЫБОРЕ~$P(x)$ ТАКАЯ
ХЕШ-ФУНКЦИЯ ПОЗВОЛЯЕТ ИЗБЕЖАТЬ КОЛЛИЗИЙ, МЕЖДУ ПОЧТИ РАВНЫМИ КЛЮЧАМИ.
эАПРИМЕР, ЕСЛИ $n=15$, $m=10$ И
$$
P(x)=x^{10}+x^8+x^5=x^4+x^2+x+1,
\eqno(10)
$$
ТО МОЖНО ПОКАЗАТЬ, ЧТО~$h(K_1)\ne h(K_2)$, КОГДА~$K_1\ne K_2$ И~$K_1$
ОТЛИЧАЕТСЯ ОТ~$K_2$ МЕНЕЕ ЧЕМ СЕМЬЮ БИТАМИ. (т УПР.~7 ВЫ НАЙДЕТЕ
ДОПОЛНИТЕЛЬНУЮ ИНФОРМАЦИЮ ОБ ЭТОЙ СХЕМЕ; РАЗУМЕЕТСЯ, ДЛЯ НЕЕ БОЛЬШЕ
ПОДХОДИТ АППАРАТНАЯ ИЛИ МИКРОПРОГРАММНАЯ, А НЕ ПРОГРАММНАЯ РЕАЛИЗАЦИЯ.)

ъАК ПОКАЗАЛ ОПЫТ, ПРИ ОТЛАДКЕ ПРОГРАММ УДОБНО ИСПОЛЬЗОВАТЬ ПОСТОЯННУЮ
ХЕШ-ФУНКЦИЮ~$h(K)=0$; ТАК КАК ВСЕ КЛЮЧИ
%% 610
БУДУТ ХРАНИТЬСЯ ВМЕСТЕ; ЭФФЕКТИВНАЯ~$h(K)$ МОЖЕТ БЫТЬ ВВЕДЕНА ПОЗДНЕЕ.

\section ЁАЗРЕШЕНИЕ КОЛЛИЗИЙ МЕТОДОМ ЦЕПОЧЕК. ьЫ УЖЕ ГОВОРИЛИ,
ЧТО НЕКОТОРЫЕ АДРЕСА МОГУТ ПОРОЖДАТЬСЯ НЕСКОЛЬКИМИ КЛЮЧАМИ. яОЖАЛУЙ,
НАИБОЛЕЕ ОЧЕВИДНЫЙ СПОСОБ РЕШЕНИЯ ПРОБЛЕМЫ СОСТОИТ В ТОМ, ЧТОБЫ
ПОДДЕРЖИВАТЬ $M$~СВЯЗАННЫХ СПИСКОВ, ПО ОДНОМУ НА КАЖДЫЙ ВОЗМОЖНЫЙ
ХЕШ-АДРЕС. тСЕ ЗАПИСИ ДОЛЖНЫ СОДЕРЖАТЬ ПОЛЯ~|LINK|; КРОМЕ ТОГО, НУЖНО
ИМЕТЬ $M$~ГОЛОВНЫХ УЗЛОВ СПИСКОВ~$|HEAD|[i]$, ГДЕ $i$~МЕНЯЕТСЯ ОТ~1
ДО~$M$. яОСЛЕ ХЕШИРОВАНИЯ
\picture{ЁИС.~38.           ЁАЗДЕЛЬНЫЕ ЦЕПОЧКИ.}
КЛЮЧА МЫ ПРОСТО ВЫПОЛНЯЕМ ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК В СПИСКЕ С
НОМЕРОМ~$h(K)+1$. (ёР.~УПР.~6.1-2. ёИТУАЦИЯ АНАЛОГИЧНА СОРТИРОВКЕ
ВСТАВКАМИ В НЕСКОЛЬКО СПИСКОВ---ПРОГРАММА 5.2.1M.)
ЁИСУНОК~38 ИЛЛЮСТРИРУЕТ ЭТОТ ПРОСТОЙ МЕТОД ЦЕПОЧЕК ПРИ~$M=9$ ДЛЯ
ПОСЛЕДОВАТЕЛЬНОСТИ СЕМИ КЛЮЧЕЙ
$$
K=|EN|, |TO|, |TRE|, |FIRE|, |FEM|, |SEKS|, |SYV|
\eqno   (11)
$$
(ТАК НАЗЫВАЮТСЯ ЧИСЛА ОТ~1 ДО~7 ПО-НОРВЕЖСКИ), ИМЕЮЩИХ СООТВЕТСТВЕННЫЕ
ХЕШ-КОДЫ
$$
h(K)+1=3, 1, 4, 1, 5, 9, 2.
\eqno(12)
$$
яЕРВЫЙ СПИСОК СОДЕРЖИТ ДВА ЭЛЕМЕНТА, ТРИ СПИСКА ПУСТЫ.

ьЕТОД ЦЕПОЧЕК ЯВЛЯЕТСЯ ВЕСЬМА БЫСТРЫМ, ПОСКОЛЬКУ СПИСКИ КОРОТКИ. хСЛИ В
ОДНОЙ КОМНАТЕ СОБРАТЬ 365~ЧЕЛОВЕК, ДТО НАЙДЕТСЯ МНОГО ПАР, ИМЕЮЩИХ ОДИН
И ТОТ ЖЕ ДЕНЬ РОЖДЕНИЯ, НО ДАННЫЙ ДЕНЬ РОЖДЕНИЯ В СРЕДНЕМ ИМЕЕТ ЛИШЬ ОДИН
ЧЕЛОВЕК! тООБЩЕ, ЕСЛИ ИМЕЕТСЯ $N$~КЛЮЧЕЙ И $M$~СПИСКОВ, СРЕДНИЙ
РАЗМЕР СПИСКА РАВЕН~$N/M$; ТАКИМ ОБРАЗОМ, ХЕШИРОВАНИЕ УМЕНЬШАЕТ КОЛИЧЕСТВО
РАБОТЫ, ТРЕБУЕМОЕ НА ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК, ПРИМЕРНО В $M$~РАЗ. (ЄОЧНАЯ
ФОРМУЛА ВЫВЕДЕНА В УПР.~34.)

%%611

¤ТОТ МЕТОД ПРЕДСТАВЛЯЕТ СОБОЙ ОЧЕВИДНУЮ КОМБИНАЦИЮ ОБСУЖДАВШИХСЯ РАНЕЕ
МЕТОДОВ, ПОЭТОМУ НЕТ НУЖДЫ ПОДРОБНО ОПИСЫВАТЬ АЛГОРИТМ ДЛЯ РАССЕЯННЫХ
ТАБЛИЦ С ЦЕПОЧКАМИ. ўАСТО ПОЛЕЗНО СОДЕРЖАТЬ ОТДЕЛЬНЫЕ  СПИСКИ
УПОРЯДОЧЕННЫМИ  ПО КЛЮЧАМ;
ЭТО УБЫСТРЯЕТ ВСТАВКИ И НЕУДАЧНЫЙ ПОИСК. ЄАК, ЕСЛИ ДЕЛАТЬ СПИСКИ
ВОЗРАСТАЮЩИМИ, НА РИС.~38 СЛЕДОВАЛО БЫ ПОМЕНЯТЬ МЕСТАМИ УЗЛЫ~|TO| И~|FIRE|,
 А ВСЕ ПУСТЫЕ ССЫЛКИ ЗАМЕНИТЬ НА УКАЗАТЕЛЬ НА ВСПОМОГАТЕЛЬНУЮ ЗАПИСЬ
С~$\infty$ В КАЧЕСТВЕ КЛЮЧА (СМ. АЛГОРИТМ 6.1T). фРУГИМ ВОЗМОЖНЫМ ПОДХОДОМ
ЯВЛЯЕТСЯ ИСПОЛЬЗОВАНИЕ ПОНЯТИЯ "САМООРГАНИЗУЮЩЕГОСЯ ФАЙЛА",
КОТОРОЕ ОБСУЖДАЛОСЬ В \S~6.1; ВМЕСТО УПОРЯДОЧЕНИЯ ПО КЛЮЧАМ ПРОИСХОДИТ
УПОРЯДОЧЕНИЕ ПО ВРЕМЕНИ ПОСЛЕДНЕГО ОБРАЩЕНИЯ К ЗАПИСИ.

т ЦЕЛЯХ ЭКОНОМИИ ВРЕМЕНИ ЖЕЛАТЕЛЬНЫ БОЛЬШИЕ~$M$, НО В ЭТОМ СЛУЧАЕ МНОГИЕ
ССЫЛКИ БУДУТ ПУСТЫМИ, ТАК ЧТО Б\'ОЛЬШАЯ ЧАСТЬ ПРОСТРАНСТВА, ОТВОДИМОГО ПОД
$M$~ГОЛОВНЫХ УЗЛОВ, ПОТРАТИТСЯ ЗРЯ. фЛЯ НЕБОЛЬШИХ ПО РАЗМЕРУ ЗАПИСЕЙ
НАПРАШИВАЕТСЯ ДРУГОЙ ПОДХОД: МОЖНО НАЛОЖИТЬ ПРОСТРАНСТВО ДЛЯ ЗАПИСЕЙ НА
ПРОСТРАНСТВО ДЛЯ ГОЛОВНЫХ УЗЛОВ, ОТВОДЯ В ТАБЛИЦЕ МЕСТО ПОД
$M$~ЗАПИСЕЙ И $M$~ССЫЛОК, А НЕ ПОД $N$~ЗАПИСЕЙ И $M+N$~ССЫЛОК.
шНОГДА МОЖНО СОВЕРШИТЬ ОДИН ПРОХОД ПО ДАННЫМ И ВЫЯСНИТЬ, КАКИЕ ГОЛОВНЫЕ
УЗЛЫ БУДУТ ИСПОЛЬЗОВАТЬСЯ, ВСТАВЛЯЯ НА СЛЕДУЮЩЕМ ПРОХОДЕ "ПЕРЕПОЛНЯЮЩИЕ"
ЗАПИСИ В СВОБОДНЫЕ ЩЕЛИ. ўАСТО, ОДНАКО, ЭТО НЕЖЕЛАТЕЛЬНО ИЛИ НЕВОЗМОЖНО;
НАМ ХОТЕЛОСЬ БЫ ИМЕТЬ МЕТОД, ПРИ КОТОРОМ КАЖДАЯ ЗАПИСЬ ОБРАБАТЫВАЕТСЯ
ЛИШЬ ОДИН РАЗ, ПРИ ПЕРВОМ ПОСТУПЛЕНИИ В СИСТЕМУ. ёЛЕДУЮЩИЙ АЛГОРИТМ,
ПРИНАДЛЕЖАЩИЙ Ї.~єИЛЬЯМСУ [{\sl CACM,\/} {\bf 2}, 6 (June 1959), 21--24],
ЯВЛЯЕТСЯ ОБЩЕПРИНЯТЫМ СПОСОБОМ РЕШЕНИЯ ЭТОЙ ЗАДАЧИ.

\alg C.(яОИСК С ВСТАВКОЙ ПО РАССЕЯННОЙ ТАБЛИЦЕ С ЦЕПОЧКАМИ.) яРЕДЛАГАЕМЫЙ
АЛГОРИТМ ПОЗВОЛЯЕТ ОТЫСКАТЬ В ТАБЛИЦЕ ИЗ $M$~ЭЛЕМЕНТОВ ДАННЫЙ КЛЮЧ~$K$.
хСЛИ $K$~НЕТ В ТАБЛИЦЕ И ОНА НЕ ПОЛНА, $K$ ВСТАВЛЯЕТСЯ В НЕЕ.

¤ЛЕМЕНТЫ ТАБЛИЦЫ ОБОЗНАЧАЮТСЯ ЧЕРЕЗ $|TABLE| [i]$, $0\le i\le M$, И МОГУТ
БЫТЬ ДВУХ РАЗЛИЧНЫХ ТИПОВ: \emph{СВОБОДНЫЙ} И~\emph{ЗАНЯТЫЙ.} чАНЯТЫЙ УЗЕЛ
СОДЕРЖИТ КЛЮЧЕВОЕ ПОЛЕ~$|KEY|[i]$, ПОЛЕ ССЫЛКИ~$|LINK|[i]$ И, ВОЗМОЖНО,
ДРУГИЕ ПОЛЯ.

рЛГОРИТМ ИСПОЛЬЗУЕТ ХЕШ-ФУНКЦИЮ~$h(K)$. фЛЯ ОБЛЕГЧЕНИЯ ПОИСКА СВОБОДНОГО
ПРОСТРАНСТВА ИСПОЛЬЗУЕТСЯ ВСПОМОГАТЕЛЬНАЯ ПЕРЕМЕННАЯ~|R|; ЕСЛИ ТАБЛИЦА
ПУСТА, $|R|=M+1$; ПО МЕРЕ ПРОВЕДЕНИЯ  ВСТАВОК БУДЕТ ОСТАВАТЬСЯ В СИЛЕ
УТВЕРЖДЕНИЕ, ЧТО УЗЛЫ~$|TABLE|[j]$ ЗАНЯТЫ ДЛЯ ВСЕХ~$j$ В ДИАПАЗОНЕ~$|R|\le
j\le M$. єСЛОВИМСЯ, ЧТО УЗЕЛ~$|TABLE|[0]$ ВСЕГДА БУДЕТ СВОБОДЕН.

\st[їЕШИРОВАНИЕ.] єСТАНОВИТЬ~$i\asg h(K)+1$. (ЄЕПЕРЬ~$1\le i\le M$.)
\st[ёПИСОК?] хСЛИ УЗЕЛ~$|TABLE|[i]$ СВОБОДЕН, ТО ПЕРЕЙТИ НА~\stp{6}.
(т ПРОТИВНОМ СЛУЧАЕ  ЭТОТ УЗЕЛ  ЗАНЯТ, И МЫ ПОСЛЕДУЕМ НА ИМЕЮЩИЙСЯ ЗДЕСЬ
СПИСОК ЗАНЯТЫХ УЗЛОВ).

%% 612
\st[ёРАВНЕНИЕ.] хСЛИ $K=|KEY|[i]$, ПОИСК ЗАВЕРШЕН УДАЧНО.

\st[яЕРЕХОД К СЛЕДУЮЩЕМУ.] хСЛИ $|LINK|[i]\ne0$,
УСТАНОВИТЬ~$i\asg|LINK|[i]$ И ВЕРНУТЬСЯ НА~\stp{3}.

\st[эАЙТИ СВОБОДНЫЙ УЗЕЛ.] (яОИСК БЫЛ НЕУДАЧНЫМ, И МЫ ХОТИМ НАЙТИ В
ТАБЛИЦЕ СВОБОДНОЕ МЕСТО.) єМЕНЬШАТЬ~|R| ДО ТЕХ ПОР, ПОКА НЕ БУДЕТ ПОЛУЧЕНО
ТАКОЕ ЗНАЧЕНИЕ, ЧТО УЗЕЛ~$|TABLE|[|R|]$ СВОБОДЕН. хСЛИ~$|R|=0$, АЛГОРИТМ
ЗАКАНЧИВАЕТСЯ ПО ПЕРЕПОЛНЕНИЮ (СВОБОДНЫХ УЗЛОВ БОЛЬШЕ НЕТ); В ПРОТИВНОМ
СЛУЧАЕ УСТАНОВИТЬ~$|LINK|[i]\asg|R|$, $i\asg|R|$.

\st[тСТАВИТЬ НОВЫЙ КЛЮЧ.] яОМЕТИТЬ~$|TABLE|[i]$ КАК ЗАНЯТЫЙ УЗЕЛ
С~$|KEY|[i]\asg K$ И~$|LINK|[i]\asg0$.
\algend

т АЛГОРИТМЕ ДОПУСКАЕТСЯ СРАСТАНИЕ НЕСКОЛЬКИХ СПИСКОВ, ТАК ЧТО ПОСЛЕ
ВСТАВКИ В ТАБЛИЦУ ЗАПИСИ ПЕРЕМЕЩАТЬ НЕ НУЖНО.
\picture{ЁИС. 39.  яОИСК С ВСТАВКОЙ ПО РАССЕЯННОЙ ТАБЛИЦЕ С ЦЕПОЧКАМИ.}
[ёМ., НАПРИМЕР, РИС.~40, ГДЕ |SEKS| ПОПАДАЕТ В СПИСОК, СОДЕРЖАЩИЙ~|TO|
И~|FIRE|, ТАК КАК ПОСЛЕДНИЙ КЛЮЧ УЖЕ БЫЛ ВСТАВЛЕН В ПОЗИЦИЮ~9.]
\picture{ЁИС. 40. ёРОСШИЕСЯ СПИСКИ.}

ўТОБЫ СРАВНИТЬ ДАННЫЙ И ДРУГИЕ АЛГОРИТМЫ ЭТОЙ ГЛАВЫ, НАПИШЕМ СЛЕДУЮЩУЮ
ПРОГРАММУ ДЛЯ \MIX{} (ПРИ СОСТАВЛЕНИИ
%%613
ПРОГРАММЫ УЧИТЫВАЛОСЬ, ЧТО СПИСКИ,  КАК ПРАВИЛО, БУДУТ КОРОТКИМИ).

\prog C.(яОИСК С ВСТАВКОЙ ПО РАССЕЯННОЙ ТАБЛИЦЕ С ЦЕПОЧКАМИ.)
фЛЯ УДОБСТВА БУДЕМ СЧИТАТЬ, ЧТО КЛЮЧИ СОСТОЯТ ИЗ ТРЕХ БАЙТОВ, А УЗЛЫ ИМЕЮТ
СЛЕДУЮЩИЙ ФОРМАТ:
\picture{ЁИС. СТР. 613}
т КАЧЕСТВЕ РАЗМЕРА ТАБЛИЦЫ~$M$ БЕРЕТСЯ ПРОСТОЕ ЧИСЛО;
$|TABLE|[i]$~ХРАНИТСЯ ПО АДРЕСУ~$|TABLE|+i$; $|rI1|\equiv i$,
$|rA|\equiv K$.
\code
KEY   &EQU  & 3:5
LINK  &EQU  & 0:2
START &LDX  & ъ             & 1     & C1. їЕШИРОВАНИЕ.
      &ENTA & 0             & 1
      &DIV  & =M=           & 1
      &STX  & *+1(0:2)      & 1
      &ENT1 & *             & 1     & $i\asg h(K)+1$.
      &INC1 & 1             & 1
      &LDA  & K             & 1
      &LD2  & TABLE, 1(LINK)& 1     & C2. ёПИСОК?
      &J2N  & 6F            & 1     & эА C6, ЕСЛИ В $|TABLE|[i]$ СВОБОДНО.
      &ёьЁр & TABLE, 1(KEY) & A     & C3. ёРАВНЕНИЕ.
      &JE   & SUCCESS       & A     & тЫХОД, ЕСЛИ $K=|KEY|[i]$.
      &J2Z  & 5F            & A-S1  & эА C5, ЕСЛИ $|LINK|[i]=0$.
4H    &ENT1 & 0,2           & C-1   & C4. яЕРЕХОД К СЛЕДУЮЩЕМУ.
      &ёьЁр & TABLE, 1(KEY) & C-1   & C3. ёРАВНЕНИЕ.
      &JE   & SUCCESS       & C-1   & тЫХОД, ЕСЛИ $K=|KEY|[i]$.
      &LD2  & TABLE,1(L1NK) & C-1-S2
      &J2NZ & 4B            & C-1-S2& яРОДВИГАТЬСЯ, ЕСЛИ $|LINK|[i]\ne0$.
5H    &LD2  & R             & A-S    & C5. эАЙТИ СВОБОДНЫЙ УЗЕЛ.
      &DEC2 & 1             & T      & $|R|\asg|R|-1$.
      &LDX  & TABLE,2       & T
      &JXNN & *-2           & Є      & яОВТОРЯТЬ, ПОКА ЗАНЯТ $|TABLE|[|R|]$.
      &J2Z  & OVERFLOW      & A-S    & тЫХОД, ЕСЛИ НЕТ СВОБОДН. УЗЛОВ
      &ST2  & TABLE, 1(LINK)& A-S    & $|LINK|[i]\asg|R|$.
      &ENT1 & 0,2           & A-S    & $i\asg|R|$.
      &ST2  & R             & A-S    & шЗМЕНИТЬ~|R| В ПАМЯТИ.
6H    &STZ  & TABLE, 1(LINK)& 1-S    & C6. тСТАВИТЬ НОВЫЙ КЛЮЧ.
      &STA  & TABLE, 1(KEY) & 1-S    & $|KEY|[i]\asg K$.
\endcode
\progend
тРЕМЯ РАБОТЫ ЭТОЙ ПРОГРАММЫ ОПРЕДЕЛЯЮТ СЛЕДУЮЩИЕ ПАРАМЕТРЫ:

\medskip
\item{$C=$}ЧИСЛО ЭЛЕМЕНТОВ ТАБЛИЦУ, ИССЛЕДУЕМЫХ ВО ВРЕМЯ ПОИСКА;
%%614
\item{$A=$}1, ЕСЛИ ПЕРВЫЙ ИСПРОБОВАННЫЙ УЗЕЛ ОКАЗАЛСЯ ЗАНЯТЫМ;

\item{$S=$}1 ПРИ УДАЧНОМ ПОИСКЕ, 0 ПРИ НЕУДАЧНОМ;

\item{$T=$}ЧИСЛО ЭЛЕМЕНТОВ ТАБЛИЦЫ, ПРОСМАТРИВАЕМЫХ В ПРОЦЕССЕ ПОИСКА
СВОБОДНОГО ПРОСТРАНСТВА.
\medskip
\noindent чДЕСЬ $S=S1+S2$, ГДЕ~$S1=1$, ЕСЛИ ПЕРВАЯ ПРОБА БЫЛА
УДАЧНОЙ. ёУММАРНОЕ ВРЕМЯ РАБОТЫ ФАЗЫ ПОИСКА ПРОГРАММЫ~C
РАВНО~$(7C+4A+17-3S+2S1)u$, ВСТАВКА НОВОГО КЛЮЧА ПРИ~$S=0$ ТРЕБУЕТ
ДОПОЛНИТЕЛЬНОГО ВРЕМЕНИ~$(8A+4T+4)u$.

яРЕДПОЛОЖИМ, ЧТО В НАЧАЛЕ РАБОТЫ ПРОГРАММЫ ТАБЛИЦА СОДЕРЖИТ $N$~КЛЮЧЕЙ,
И ВВЕДЕМ
$$
\alpha=N/M=\hbox{КОЭФФИЦИЕНТ ЗАПОЛНЕНИЯ (ЗАГРУЗКИ) ТАБЛИЦЫ.}
\eqno (14)
$$
ЄОГДА СРЕДНЕЕ ЗНАЧЕНИЕ~$A$ ПРИ НЕУДАЧНОМ ПОИСКЕ, ОЧЕВИДНО,
РАВНО~$\alpha$ (ПРИ СЛУЧАЙНОЙ ФУНКЦИИ ХЕШИРОВАНИЯ); В УПР.~39
ДОКАЗЫВАЕТСЯ, ЧТО СРЕДНЕЕ ЗНАЧЕНИЕ~$C$ ПРИ НЕУДАЧНОМ ПОИСКЕ СОСТАВЛЯЕТ
$$
C'_N=1+{1\over4}\left(\left(1+{2\over M}\right)^N-1-{2N\over M}\right)
\approx 1+{1\over4}(e^{2\alpha}-1-2\alpha).
\eqno(15)
$$

ЄАКИМ ОБРАЗОМ, ЕСЛИ ТАБЛИЦА ЗАПОЛНЕНА НАПОЛОВИНУ, СРЕДНЕЕ ЧИСЛО ПРОБ,
ПРОИЗВОДИМЫХ ВО ВРЕМЯ НЕУДАЧНОГО ПОИСКА,
ПРИБЛИЖЕННО РАВНО~${1\over4}(e+2)\approx 1.18$; ДАЖЕ ЕСЛИ ТАБЛИЦА
ЗАПОЛНЯЕТСЯ ПОЛНОСТЬЮ, СРЕДНЕЕ ЧИСЛО ПРОБ ПРИ ВСТАВКЕ ПОСЛЕДНЕГО ЭЛЕМЕНТА
ДОСТАВЛЯЕТ ЛИШЬ ОКОЛО~${1\over4}(e^2+1)\approx 2.10$. ъАК ДОКАЗЫВАЕТСЯ В
УПР.~40, СРЕДНЕКВАДРАТИЧНОЕ ОТКЛОНЕНИЕ ТАКЖЕ МАЛО. ¤ТИ ВЫКЛАДКИ ПОКАЗЫВАЮТ,
 ЧТО ПРИ СЛУЧАЙНОЙ ФУНКЦИИ ХЕШИРОВАНИЯ \emph{СПИСКИ ОСТАЮТСЯ КОРОТКИМИ,
НЕСМОТРЯ НА ВОЗМОЖНОСТЬ СРАСТАНИЙ.} ЁАЗУМЕЕТСЯ, $C$~МОЖЕТ СТАТЬ РАВНЫМ~$N$,
 ЕСЛИ ХЕШ-ФУНКЦИЯ ПЛОХА ИЛИ ЕСЛИ НАМ ЗДОРОВО НЕ ПОВЕЗЛО.

фЛЯ УДАЧНОГО ПОИСКА $A$~ВСЕГДА РАВНО~1. ёРЕДНЕЕ ЧИСЛО ПРОБ МОЖНО ВЫЧИСЛИТЬ,
 ПРОСУММИРОВАВ ВЕЛИЧИНЫ~$C+A$ ПО ПЕРВЫМ~$N$ НЕУДАЧНЫМ ПОИСКАМ И ПОДЕЛИВ
НА~$N$. яРЕДПОЛАГАЕТСЯ, ЧТО ВСЕ КЛЮЧИ РАВНОВЕРОЯТНЫ. шМЕЕМ
$$
\eqalignno{
C_N&={1\over N}\sum_{0\le k<N}\left(C'_k+{k\over M}\right)
=1+{1\over8}{M\over N}
\left(\left(1+{2\over M}\right)^N-1-{2N\over M}\right)
+{1\over4}{N-1\over M}\approx&\cr
&\approx 1+{1\over 8\alpha}(e^{2\alpha}-1-2\alpha)+{1\over4}\alpha.& (16)\cr
}
$$
фАЖЕ В СЛУЧАЕ ЗАПОЛНЕННОЙ ТАБЛИЦЫ В СРЕДНЕМ ДЛЯ НАХОЖДЕНИЯ ЭЛЕМЕНТА
ПОНАДОБИТСЯ ЛИШЬ ОКОЛО $1.80$~ПРОБЫ! рНАЛОГИЧНО (СМ.~УПР.~42) СРЕДНЕЕ
ЗНАЧЕНИЕ~$S1$ ОКАЗЫВАЕТСЯ РАВНЫМ
$$
S1_N=1-{1\over2}((N-1)/M)\approx 1-{1\over2}\alpha.
\eqno(17)
$$
%%615
эА ПЕРВЫЙ ВЗГЛЯД ШАГ~C5 МОЖЕТ ПОКАЗАТЬСЯ НЕЭФФЕКТИВНЫМ, ТАК КАК В НЕМ
ПОИСК СВОБОДНОЙ ПОЗИЦИИ ПРОИЗВОДИТСЯ ПОСЛЕДОВАТЕЛЬНО. эО В
ДЕЙСТВИТЕЛЬНОСТИ В ПРОЦЕССЕ ЗАПОЛНЕНИЯ ТАБЛИЦЫ СУММАРНОЕ ЧИСЛО ПРОБ В
ШАГЕ~C5 НЕ ПРЕВЫШАЕТ КОЛИЧЕСТВА ЭЛЕМЕНТОВ В ТАБЛИЦЕ; ЗНАЧИТ, В СРЕДНЕМ НА
КАЖДУЮ ВСТАВКУ ТРАТИТСЯ НЕ БОЛЕЕ ОДНОЙ ТАКОЙ ПРОБЫ! т УПР.~41 ДОКАЗЫВАЕТСЯ,
ЧТО ДЛЯ СЛУЧАЙНОГО НЕУДАЧИОГО ПОИСКА~$T\approx \alpha e^\alpha$.

ьОЖНО БЫЛО БЫ ИЗБЕЖАТЬ СРАСТАНИЯ СПИСКОВ, СООТВЕТСТВУЮЩИМ ОБРАЗОМ
МОДИФИЦИРОВАВ АЛГОРИТМ~C, НО ТОГДА ПРИШЛОСЬ БЫ ПРИБЕГНУТЬ К ПЕРЕМЕЩЕНИЮ
ЗАПИСЕЙ. ЁАССМОТРИМ, НАПРИМЕР, ЧТО ПРОИСХОДИТ ПРИ ПОПЫТКЕ ВСТАВИТЬ~|SEKS|
В ПОЗИЦИЮ~9 (СМ.~РИС.~40). ўТОБЫ СПИСКИ ОСТАВАЛИСЬ РАЗДЕЛЬНЫМИ, НУЖНО
ПЕРЕМЕСТИТЬ~|FIRE|; ПРИ ЭТОМ НЕОБХОДИМО НАЙТИ УЗЕЛ, СОДЕРЖАЩИЙ ССЫЛКУ
НА~|FIRE|. фЛЯ РЕШЕНИЯ ЭТОЙ ЗАДАЧИ МОЖНО, КАК ПРЕДЛОЖИЛ рЛЛЕН эЬЮЭЛЛ
В~1962~Г., ВМЕСТО ДВУХСВЯЗЕВЫХ ИСПОЛЬЗОВАТЬ КОЛЬЦЕВЫЕ СПИСКИ, ТАК КАК В
КАЖДОМ СПИСКЕ НЕМНОГО ЭЛЕМЕНТОВ. юДНАКО ЭТО, ВЕРОЯТНО, ЗАМЕДЛИТ ГЛАВНЫЙ
ЦИКЛ ПОИСКА, ПОСКОЛЬКУ ШАГ~C4 СТАНОВИТСЯ СЛОЖНЕЕ. т УПР.~34 ПОКАЗАНО,
ЧТО В СЛУЧАЕ НЕПЕРЕСЕКАЮЩИХСЯ СПИСКОВ СРЕДНЕЕ ЧИСЛО ПРОБ УМЕНЬШАЕТСЯ ДО
$$
\eqalignno{
C'_N&=\left(1-{1\over M}\right)^N+{N\over M}\approx e^{-\alpha}+\alpha
\qquad\hbox{(НЕУДАЧНЫЙ ПОИСК);} & (18)\cr
C_N&=1+{N-1\over 2M}\approx 1+{1\over2}\alpha
\qquad\hbox{(УДАЧНЫЙ ПОИСК).} & (19) \cr
}
$$
тРЯД ЛИ СТОИТ РАДИ ТАКОГО УЛУЧШЕНИЯ ИЗМЕНЯТЬ АЛГОРИТМ.

ё ДРУГОЙ СТОРОНЫ, сАТЛЕР ыЭМПСОН ЗАМЕТИЛ, ЧТО БОЛЬШАЯ ЧАСТЬ ПРОСТРАНСТВА,
В ДЕЙСТВИТЕЛЬНОСТИ ЗАНЯТОГО ССЫЛКАМИ, МОЖЕТ БЫТЬ СЭКОНОМЛЕНА В МЕТОДЕ
ЦЕПОЧЕК, ЕСЛИ ИЗБАВИТЬСЯ ОТ СРАСТАНИЯ СПИСКОВ. ¤ТО ПРИВОДИТ К ИНТЕРЕСНОМУ
АЛГОРИТМУ, ОБСУЖДАЮЩЕМУСЯ В УПР.~13.

чАМЕТИМ, ЧТО МЕТОД ЦЕПОЧЕК МОЖНО ИСПОЛЬЗОВАТЬ И ПРИ~$N>M$, ТАК ЧТО
ПЕРЕПОЛНЕНИЕ НЕ ПРЕДСТАВЛЯЕТ СЕРЬЕЗНОЙ ПРОБЛЕМЫ. хСЛИ ИСПОЛЬЗУЮТСЯ
РАЗДЕЛЬНЫЕ СПИСКИ, ФОРМУЛЫ~(18) И~(19) СПРАВЕДЛИВЫ ДЛЯ~$\alpha>1$. ъОГДА
ЖЕ СПИСКИ СРАСТАЮТСЯ, КАК В АЛГОРИТМЕ~C, МОЖНО ПОМЕЩАТЬ ПЕРЕПОЛНЯЮЩИЕ
ЭЛЕМЕНТЫ ВО ВСПОМОГАТЕЛЬНЫЙ ПУЛ ПАМЯТИ. ъАК ДОКАЗАЛ ы.~уЮИБА, В
ЭТОМ СЛУЧАЕ СРЕДНЕЕ ЧИСЛО ПРОБ ПРИ ВСТАВКЕ $(M+L+1)\hbox{-ГО}$~ЭЛЕМЕНТА
СОСТАВЛЯЕТ~$\left(L/2M+{1\over4}\right)((1+2/M)^M-1)+{1\over2}$.

\section ЁАЗРЕШЕНИЕ КОЛЛИЗИЙ "ОТКРЫТОЙ АДРЕСАЦИЕЙ". фРУГОЙ СПОСОБ РЕШЕНИЯ
ПРОБЛЕМЫ КОЛЛИЗИЙ СОСТОИТ В ТОМ, ЧТОБЫ ПОЛНОСТЬЮ ОТКАЗАТЬСЯ ОТ ССЫЛОК И
ПРОСТО ПРОСМАТРИВАТЬ ОДИН ЗА ДРУГИМ РАЗЛИЧНЫЕ ЭЛЕМЕНТЫ ТАБЛИЦЫ, ПОКА НЕ
БУДУТ НАЙДЕНЫ КЛЮЧ~$K$ ИЛИ СВОБОДНАЯ ПОЗИЦИЯ. эЕ ПЛОХО БЫЛО БЫ ИМЕТЬ
ПРАВИЛО, СОГЛАСНО КОТОРОМУ КАЖДЫЙ КЛЮЧ~$K$ ОПРЕДЕЛЯЕТ ПОСЛЕДОВАТЕЛЬНОСТЬ
%%616
ПРОБ, Т.~Е.~ПОСЛЕДОВАТЕЛЬНОСТЬ ПОЗИЦИЙ В ТАБЛИЦЕ, КОТОРЫЕ НУЖНО
ПРОСМАТРИВАТЬ ВСЯКИЙ РАЗ ПРИ ВСТАВКЕ ИЛИ ПОИСКЕ~$K$. хСЛИ МЫ, ИСПОЛЬЗУЯ
ОПРЕДЕЛЯЕМУЮ~$K$ ПОСЛЕДОВАТЕЛЬНОСТЬ ПРОБ, НАТОЛКНЕМСЯ НА СВОБОДНУЮ ПОЗИЦИЮ,
 ТО МОЖНО СДЕЛАТЬ ВЫВОД, ЧТО $K$~НЕТ В ТАБЛИЦЕ, ТАК КАК ТА ЖЕ
ПОСЛЕДОВАТЕЛЬНОСТЬ ПРОБ ВЫПОЛНЯЕТСЯ КАЖДЫЙ РАЗ ПРИ ОБРАБОТКЕ ДАННОГО КЛЮЧА.
 ¤ТОТ ОБЩИЙ КЛАСС МЕТОДОВ є.~яЕТЕРСОН НАЗВАЛ \dfn{ОТКРЫТОЙ
АДРЕСАЦИЕЙ} [{\sl IBM J.~Research \& Development,\/} {\bf 1} (1957), 130--146].

яРОСТЕЙШАЯ СХЕМА ОТКРЫТОЙ АДРЕСАЦИИ, ИЗВЕСТНАЯ КАК \dfn{ЛИНЕЙНОЕ
ОПРОБОВАНИЕ,} ИСПОЛЬЗУЕТ ЦИКЛИЧЕСКУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ
$$
h(K), h(K)-1, \ldots, 0, M-1, M-2, \ldots, h(K)+1
\eqno(20)
$$
И ОПИСЫВАЕТСЯ СЛЕДУЮЩИМ ОБРАЗОМ.

\alg L.(яОИСК С ВСТАВКОЙ ПО ОТКРЫТОЙ РАССЕЯННОЙ ТАБЛИЦЕ.)
рЛГОРИТМ ПОЗВОЛЯЕТ РАЗЫСКАТЬ ДАННЫЙ КЛЮЧ~$K$ В ТАБЛИЦЕ ИЗ $M$~УЗЛОВ.
хСЛИ $K$~НЕТ В ТАБЛИЦЕ И ОНА НЕ ПОЛНА, КЛЮЧ~$K$ ВСТАВЛЯЕТСЯ.

єЗЛЫ ТАБЛИЦЫ ОБОЗНАЧАЮТСЯ ЧЕРЕЗ~$|TABLE|[i]$, $0\le i<M$, И ПРИНАДЛЕЖАТ
ДВУМ РАЗЛИЧНЫМ ТИПАМ УЗЛОВ---\emph{СВОБОДНЫХ} И~\emph{ЗАНЯТЫХ}. чАНЯТЫЙ УЗЕЛ
СОДЕРЖИТ КЛЮЧ~$|KEY|[i]$ И, ВОЗМОЖНО, ДРУГИЕ ПОЛЯ. чНАЧЕНИЕ ВСПОМОГАТЕЛЬНОЙ
ПЕРЕМЕННОЙ~|N| РАВНО ЧИСЛУ ЗАНЯТЫХ УЗЛОВ; ЭТА ПЕРЕМЕННАЯ РАССМАТРИВАЕТСЯ
КАК ЧАСТЬ ТАБЛИЦЫ, И ПРИ ВСТАВКЕ НОВОГО КЛЮЧА ЕЕ ЗНАЧЕНИЕ УВЕЛИЧИВАЕТСЯ НА~1.

фАННЫЙ АЛГОРИТМ ИСПОЛЬЗУЕТ ХЕШ-ФУНКЦИЮ~$h(K)$ И ЛИНЕЙНУЮ
ПОСЛЕДОВАТЕЛЬНОСТЬ ПРОБ~(20) ДЛЯ АДРЕСАЦИИ. ьОДИФИКАЦИИ ЭТОЙ
ПОСЛЕДОВАТЕЛЬНОСТИ ОБСУЖДАЮТСЯ НИЖЕ.

\st[їЕШИРОВАНИЕ.] єСТАНОВИТЬ $i\asg h(K)$. (ЄЕПЕРЬ $0\le i< M$.)

\st[ёРАВНИТЬ.] хСЛИ УЗЕЛ~$|TABLE|[i]$ СВОБОДЕН, ТО ПЕРЕЙТИ НА~\stp{4}. т
ПРОТИВНОМ СЛУЧАЕ, ЕСЛИ~$|KEY|[i]=K$, АЛГОРИТМ ЗАКАНЧИВАЕТСЯ УДАЧНО.

\st[яЕРЕЙТИ К СЛЕДУЮЩЕМУ.] єСТАНОВИТЬ~$i\asg i-1$; ЕСЛИ ТЕПЕРЬ $i<0$,
УСТАНОВИТЬ~$i\asg i+M$. тЕРНУТЬСЯ НА~\stp{2}.

\st[тСТАВИТЬ.] (яОИСК БЫЛ НЕУДАЧНЫМ.) хСЛИ~$|N|=M-1$, АЛГОРИТМ
ЗАКАНЧИВАЕТСЯ ПО ПЕРЕПОЛНЕНИЮ. (т ДАННОМ АЛГОРИТМЕ СЧИТАЕТСЯ, ЧТО
ТАБЛИЦА ПОЛНА ПРИ~$|N|=M-1$, А НЕ ПРИ~$|N|=M$; СМ.~УПР.~15.) т ПРОТИВНОМ
СЛУЧАЕ УСТАНОВИТЬ~$|N|\asg|N|+1$, ОТМЕТИТЬ, ЧТО УЗЕЛ~$|TABLE|[i]$ ЗАНЯТ И
УСТАНОВИТЬ~$|KEY|[i]\asg K$.
\algend

эА РИС.~41 ПОКАЗАНО, ЧТО ПРОИСХОДИТ ПРИ ВСТАВКЕ С ПОМОЩЬЮ АЛГОРИТМА~L СЕМИ
"НОРВЕЖСКИХ" КЛЮЧЕЙ~(11), ИМЕЮЩИХ КОДЫ ХЕШИРОВАНИЯ 2, 7, 1, 8, 2, 8, 1
СООТВЕТСТВЕННО. яОСЛЕДНИЕ ТРИ КЛЮЧА---|FEM|, |SEKS| И~|SYV|---СМЕЩЕНЫ ПО
СРАВНЕНИЮ СО СВОИМИ НАЧАЛЬНЫМИ АДРЕСАМИ~$h(K)$.
%%617

\picture{ЁИС. 41. ыИНЕЙНАЯ ОТКРЫТАЯ АДРЕСАЦИЯ.}
\prog L.(яОИСК С ВСТАВКОЙ ПО ОТКРЫТОЙ РАССЕЯННОЙ ТАБЛИЦЕ.)
яРОГРАММА РАБОТАЕТ С КЛЮЧАМИ, ЗАНИМАЮЩИМИ ПОЛНОЕ СЛОВО; ОДНАКО НУЛЕВОЙ
КЛЮЧ ИСПОЛЬЗОВАТЬ НЕЛЬЗЯ, ТАК КАК НУЛЬ ОБОЗНАЧАЕТ СВОБОДНУЮ ПОЗИЦИЮ В
ТАБЛИЦЕ. (фРУГАЯ ВОЗМОЖНОСТЬ СОСТОИТ В ТОМ, ЧТОБЫ НАЛОЖИТЬ УСЛОВИЕ
НЕОТРИЦАТЕЛЬНОСТИ КЛЮЧЕЙ, А В СВОБОДНЫЕ ПОЗИЦИИ ЗАПИСАТЬ~$-1$.)
яРЕДПОЛАГАЕТСЯ, ЧТО РАЗМЕР ТАБЛИЦЫ~$M$---ПРОСТОЕ ЧИСЛО И ЧТО
УЗЕЛ~$|TABLE|[i]$ ИМЕЕТ АДРЕС~$|TABLE|+i$, $0\le i < M$. фЛЯ УСКОРЕНИЯ
ВНУТРЕННЕГО ЦИКЛА В ЯЧЕЙКУ~$|TABLE|-1$ ПОМЕЩЕН~0.
▀ЧЕЙКА~|VACANCIES| СОДЕРЖИТ ЗНАЧЕНИЕ~$M-1-N$; $|rA|\equiv K$, $|rI1|\equiv i$.

ЄАКЖЕ ДЛЯ УСКОРЕНИЯ ВНУТРЕННЕГО ЦИКЛА ПРОГРАММЫ ИЗ НЕГО ВЫНЕСЕНА
ПРОВЕРКА~"$i<0$", ТАК ЧТО В НЕМ ОСТАЛИСЬ ЛИШЬ СУЩЕСТВЕННЫЕ ЧАСТИ
ШАГОВ~\stp{2} И~\stp{3}. яОИСКОВАЯ ФАЗА ДЛИТСЯ $(7C+9E+21-4S)u$, А ВСТАВКА
ПОСЛЕ НЕУДАЧНОГО ПОИСКА ТРЕБУЕТ ДОПОЛНИТЕЛЬНО~$9u$.
\code
START & LDX & K         & 1    & L1. їЕШИРОВАНИЕ.
      & ENTA& 0         & 1
      & DIV & =M=       & 1
      & STX & *+1(0:2)  & 1
      & ENT1& *         & 1    & $i\asg h(K)$.
      & LDA & K         & 1
      & JMP & 2F        & 1
8H    & INC1& M+1       & E    & L3. яЕРЕЙТИ К СЛЕДУЮЩЕМУ.
3H    & DEC1& 1         & C+E-1& $i\asg i-1$.
2H    & CMPA& TABLE,1   & C+E  & L2. ёРАВНИТЬ.
      & JE  & SUCCESS   & C+E  & тЫХОД, ЕСЛИ $K=|KEY|[i]$.
      & LDX & TABLE,1   & C+E-S
      & JXNZ& 3B        & C+E-S& эА L3, ЕСЛИ В $|TABLE|[i]$ ЗАНЯТО.
      & J1N & 8B        & E+1-S& Ha L3 С $i\asg M$, ЕСЛИ~$i=-1$.
4H    & LDX & VACANCIES & 1-S  & L4. тСТАВИТЬ,
      & JXZ & OVERFLOW  & 1-S  & тЫХОД ПО ПЕРЕПОЛН., ЕСЛИ $N=M-1$.
      & DECX& 1         & 1-S
      & STX & VACANCIES & 1-S  & єВЕЛИЧИТЬ $N$ НА~1.
      & STA & TABLE, 1  & 1-S  & $|TABLE|[i]\asg K$.
\endcode
\progend
%% 618
ъАК И В ПРОГРАММЕ~C, ПО ПЕРЕМЕННОЙ~$C$ МЫ СУДИМ О КОЛИЧЕСТВЕ  ПРОБ, ПО
ПЕРЕМЕННОЙ~$S$---БЫЛ ЛИ ПОИСК УДАЧНЫМ. яЕРЕМЕННОЙ~$E$  МОЖНО ПРЕНЕБРЕЧЬ, ТАК
КАК ОНА РАВНА~1, ЛИШЬ ЕСЛИ ПРОИЗВОДИЛАСЬ ПРОБА ФИКТИВНОГО
УЗЛА~$|TABLE|[-1]$; ЕЕ СРЕДНЕЕ ЗНАЧЕНИЕ РАВНО~$(C-1)/M$.

¤КСПЕРИМЕНТЫ С ЛИНЕЙНЫМ ОПРОБОВАНИЕМ ПОКАЗЫВАЮТ, ЧТО ЭТОТ МЕТОД РАБОТАЕТ
ПРЕКРАСНО, ПОКА ТАБЛИЦА НЕ СЛИШКОМ ЗАПОЛНЕНА, НО В КОНЦЕ КОНЦОВ ПРОЦЕСС
ЗАМЕДЛЯЕТСЯ, ДЛИННЫЕ СЕРИИ ПРОБ СТАНОВЯТСЯ ВСЕ БОЛЕЕ ЧАСТЫМИ. яРИЧИНУ
ТАКОГО ПОВЕДЕНИЯ МОЖНО ПОНЯТЬ, РАССМОТРЕВ СЛЕДУЮЩУЮ
ГИПОТЕТИЧЕСКУЮ РАССЕЯННУЮ ТАБЛИЦУ ($M=19$, $N= 9$):
\picture{ЁИС. СТР. 618}
чАШТРИХОВАНЫЕ КВАДРАТЫ ОБОЗНАЧАЮТ ЗАНЯТЫЕ ПОЗИЦИИ. ъЛЮЧ~$K$,  КОТОРЫЙ
ДОЛЖЕН БЫТЬ ВСТАВЛЕН В ТАБЛИЦУ СЛЕДУЮЩИМ, ПОПАДЕТ  В ОДНУ ИЗ ДЕСЯТИ
СВОБОДНЫХ ПОЗИЦИЙ, НО НЕ С РАВНЫМИ ВЕРОЯТНОСТЯМИ. т САМОМ ДЕЛЕ, $K$ БУДЕТ
ВСТАВЛЕН В ПОЗИЦИЮ~$11$, ЕСЛИ  $11\le h(K)\le 15$, А В ПОЗИЦИЮ~8 ОН
ПОПАДЕТ ЛИШЬ ПРИ~$h(K)=8$.  ёЛЕДОВАТЕЛЬНО, ВЕРОЯТНОСТЬ ПОПАСТЬ В
ПОЗИЦИЮ~11 В ПЯТЬ РАЗ
БОЛЬШЕ, ЧЕМ В ПОЗИЦИЮ~8; ДЛИННЫЕ СПИСКИ СТРЕМЯТСЯ СТАТЬ ЕЩ╕
ДЛИННЕЕ.

эО ЭТО ЯВЛЕНИЕ САМО ПО СЕБЕ НЕ ОБоЯСНЯЕТ ОТНОСИТЕЛЬНО ПЛОХОГО ПОВЕДЕНИЯ
ЛИНЕЙНОГО ОПРОБОВАНИЯ, ТАК КАК АНАЛОГИЧНЫЙ ФАКТ СПРАВЕДЛИВ И ДЛЯ
АЛГОРИТМА~C. (ЁОСТ СПИСКА ИЗ ЧЕТЫРЕХ ЭЛЕМЕНТОВ ВЧЕТВЕРО ВЕРОЯТНЕЕ РОСТА
СПИСКА ИЗ ОДНОГО ЭЛЕМЕНТА.) эАСТОЯЩИЕ ТРУДНОСТИ ВОЗНИКАЮТ ПРИ ВСТАВКЕ В
ЯЧЕЙКУ ВРОДЕ~4 ИЛИ~16 (СМ.~(21)); ДВА РАЗЛИЧНЫХ СПИСКА ОБоЕДИНЯЮТСЯ.
чАМЕТИМ, ЧТО В АЛГОРИТМЕ~C СПИСКИ УДЛИНЯЮТСЯ НЕ БОЛЕЕ ЧЕМ НА ОДИН ЭЛЕМЕНТ.
ёЛЕДОВАТЕЛЬНО, ХАРАКТЕРИСТИКИ ЛИНЕЙНОГО ОПРОБОВАНИЯ РЕЗКО УХУДШАЮТСЯ,
КОГДА $N$~ПРИБЛИЖАЕТСЯ К~$M$.

фАЛЕЕ В ЭТОМ ПАРАГРАФЕ МЫ ДОКАЖЕМ, ЧТО СРЕДНЕЕ ЧИСЛО ПРОБ, ПРОИЗВОДИМЫХ
АЛГОРИТМОМ~L, ПРИБЛИЖЕННО РАВНО
$$
\eqalignno{
C'_N&\approx {1\over 2}\left(1+\left({1\over 1-\alpha}\right)^2\right)
\rem{(НЕУДАЧНЫЙ ПОИСК);} & (22) \cr
C_N&\approx {1\over 2}\left(1+{1\over 1-\alpha}\right)
\rem{(УДАЧНЫЙ ПОИСК),} & (23)\cr
}
$$
ГДЕ $\alpha=N/M$~ЕСТЬ КОЭФФИЦИЕНТ ЗАПОЛНЕНИЯ ТАБЛИЦЫ. ЄАК ЧТО, ЕСЛИ
ТАБЛИЦА ЗАПОЛНЕНА МЕНЬШЕ ЧЕМ НА~75\%, ПРОГРАММА~L РАБОТАЕТ ПОЧТИ ТАК ЖЕ
БЫСТРО, КАК И ПРОГРАММА~C, ХОТЯ ПОСЛЕДНЯЯ И РАБОТАЕТ С НЕПРАВДОПОДОБНО
КОРОТКИМИ КЛЮЧАМИ. ё ДРУГОЙ СТОРОНЫ, КОГДА $\alpha$~ПРИБЛИЖАЕТСЯ К~1,
ЛУЧШЕЕ, ЧТО МОЖНО СКАЗАТЬ О ПРОГРАММЕ~L, ЭТО ТО, ЧТО ОНА РАБОТАЕТ МЕДЛЕННО,
НО ВЕРНО.

%%619
т САМОМ ДЕЛЕ, ЕСЛИ~$N=M-1$, В ТАБЛИЦЕ ИМЕЕТСЯ ЛИШЬ ОДНО ВАКАНТНОЕ МЕСТО,
ПОЭТОМУ СРЕДНЕЕ ЧИСЛО ПРОБ ДЛЯ НЕУДАЧНОГО ПОИСКА РАВНО~$(M+1)/2$; МЫ
ДОКАЖЕМ, ЧТО СРЕДНЕЕ ЧИСЛО ПРОБ ДЛЯ УДАЧНОГО ПОИСКА В ЗАПОЛНЕННОЙ ТАБЛИЦЕ
ПРИБЛИЖЕННО РАВНО~$\sqrt{\pi M/8}$.

▀ВЛЕНИЕ СКУЧИВАНИЯ, КОТОРОЕ ДЕЛАЕТ ЛИНЕЙНОЕ ОПРОБОВАНИЕ ДОРОГОСТОЯЩИМ В
СЛУЧАЕ ПОЧТИ ЗАПОЛНЕННЫХ ТАБЛИЦ, УСУГУБЛЯЕТСЯ ПРИ ИСПОЛЬЗОВАНИИ
ХЕШИРОВАНИЯ ДЕЛЕНИЕМ, ЕСЛИ ВПОЛНЕ ВЕРОЯТНА ПОЯВЛЕНИЕ ПОСЛЕДОВАТЕЛЬНЫХ
ЗНАЧЕНИЙ
КЛЮЧЕЙ~$\set{K, K+1, K+2,~\ldots}$, ТАК КАК ЭТИ КЛЮЧИ БУДУТ ИМЕТЬ
ПОСЛЕДОВАТЕЛЬНЫЕ ХЕШ-КОДЫ. їЕШИРОВАНИЕ УМНОЖЕНИЕМ РАССЕЕТ ТАКИЕ ГРУППЫ
ДОСТАТОЧНО ХОРОШО.

фРУГОЙ СПОСОБ РАЗРЕШЕНИЯ ПРОБЛЕМЫ ПОСЛЕДОВАТЕЛЬНЫХ КОДОВ ХЕШИРОВАНИЯ
СОСТОИТ В ТОМ, ЧТОБЫ В ШАГЕ~L3 ВМЕСТО~$i\asg i-1$ УСТАНОВИТЬ~$i\asg i-c$.
уОДИТСЯ ЛЮБАЯ ПОЛОЖИТЕЛЬНАЯ ВЕЛИЧИНА~$c$, \emph{ВЗАИМНО ПРОСТАЯ С~$M$},
ТАК КАК МЫ ПРОВЕРИМ ВСЕ ПОЗИЦИИ ТАБЛИЦЫ. ¤ТО ИЗМЕНЕНИЕ СДЕЛАЕТ
ПРОГРАММУ~L НЕСКОЛЬКО МЕДЛЕННЕЕ И НЕ РАЗРЕШИТ ПРОБЛЕМЫ СКУЧИВАНИЯ, ТАК
КАК ПО-ПРЕЖНЕМУ БУДУТ ОБРАЗОВЫВАТЬСЯ ГРУППЫ ЗАПИСЕЙ, УДАЛЕННЫХ ДРУГ ОТ
ДРУГА НА~$c$; ФОРМУЛЫ~(22) И~(23) ОСТАНУТСЯ В СИЛЕ. яРАВДА,
ТЕПЕРЬ ПОЯВЛЕНИЕ ПОСЛЕДОВАТЕЛЬНЫХ КЛЮЧЕЙ~$\set{K, K+1, K+2,~\ldots}$
ИЗ ПОМЕХИ ПРЕВРАТИТСЯ В ПОМОЩЬ.

їОТЯ ФИКСИРОВАННОЕ ЗНАЧЕНИЕ~$c$ НЕ УСТРАНЯЕТ СКУЧИВАНИЯ, МОЖНО СУЩЕСТВЕННО
УЛУЧШИТЬ СИТУАЦИЮ, ЕСЛИ СДЕЛАТЬ~$c$ ЗАВИСЯЩИМ ОТ~$K$. ¤ТА ИДЕЯ ПРИВОДИТ
К ВАЖНОМУ ИЗМЕНЕНИЮ АЛГОРИТМА~L, КОТОРОЕ ВПЕРВЫЕ ОТКРЫЛ уЮИ ДЕ~сАЛЬБИН
[ДОКТОРСКАЯ ДИССЕРТАЦИЯ, Calif. Inst. of Technology (1968), 149--150].
\alg D.(юТКРЫТАЯ АДРЕСАЦИЯ С ДВОЙНЫМ ХЕШИРОВАНИЕМ.)
¤ТОТ АЛГОРИТМ ПОЧТИ СОВПАДАЕТ С АЛГОРИТМОМ~L, НО ИСПОЛЬЗУЕТ НЕСКОЛЬКО ИНУЮ
ПОСЛЕДОВАТЕЛЬНОСТЬ ПРОБ, ВЫЧИСЛЯЯ ДВЕ ХЕШ-ФУНКЦИИ~$h_1(K)$  И~$h_2(K)$.
ъАК ОБЫЧНО, $h_1(K)$~ПОРОЖДАЕТ ВЕЛИЧИНЫ ОТ~0 ДО~$M-1$ ВКЛЮЧИТЕЛЬНО; НО
ЗНАЧЕНИЯ~$h_2(K)$ ДОЛЖНЫ ЛЕЖАТЬ ОТ~1 ДО~$M-1$ И БЫТЬ \emph{ВЗАИМНО ПРОСТЫ
С~$M$}. (эАПРИМЕР, ЕСЛИ $M$---ПРОСТОЕ ЧИСЛО, ТО $h_2(K)$~МОЖЕТ БЫТЬ
\emph{ЛЮБОЙ} ВЕЛИЧИНОЙ ОТ~1 ДО~$M-1$ ВКЛЮЧИТЕЛЬНО, ИЛИ, ЕСЛИ~$M=2^m$,
ТО~$h_2(K)$ МОЖЕТ БЫТЬ ЛЮБЫМ \emph{НЕЧЕТНЫМ} ЧИСЛОМ МЕЖДУ~1 И~$2^m-1$.)

\st[яЕРВОЕ ХЕШИРОВАНИЕ.] єСТАНОВИТЬ~$i\asg h_1(K)$.
\st[яЕРВАЯ ПРОБА.] хСЛИ УЗЕЛ~$|TABLE|[i]$ СВОБОДЕН, ТО ПЕРЕЙТИ
НА~\stp{6}. т ПРОТИВНОМ СЛУЧАЕ, ЕСЛИ~$|KEY|[i]=K$, АЛГОРИТМ
ЗАКАНЧИВАЕТСЯ УДАЧНО.

\st[тТОРОЕ ХЕШИРОВАНИЕ.] єСТАНОВИТЬ~$c\asg h_2(K)$.
\st[яЕРЕЙТИ К СЛЕДУЮЩЕМУ.] єСТАНОВИТЬ~$i\asg i-c$; ЕСЛИ ТЕПЕРЬ~$i<0$,
УСТАНОВИТЬ~$i\asg i+M$.
\st[ёРАВНЕНИЕ.] хСЛИ УЗЕЛ~$|TABLE|[i]$ СВОБОДЕН, ТО ПЕРЕЙТИ
%%620
НА~\stp{6}. т ПРОТИВНОМ СЛУЧАЕ, ЕСЛИ~$|KEY|[i]=K$, АЛГОРИТМ ЗАКАНЧИВАЕТСЯ
УДАЧНО; В ПРОТИВНОМ СЛУЧАЕ ВЕРНУТЬСЯ НА~\stp{4}.
\st[тСТАВКА.] хСЛИ~$|N|=M-1$, АЛГОРИТМ ЗАКАНЧИВАЕТСЯ ПО ПЕРЕПОЛНЕНИЮ. т
ПРОТИВНОМ СЛУЧАЕ УСТАНОВИТЬ~$|N|\asg |N|+1$, ПОМЕТИТЬ УЗЕЛ~$|TABLE|[i]$
КАК ЗАНЯТЫЙ И УСТАНОВИТЬ~$|KEY|[i]\asg K$.
\algend

фЛЯ ВЫЧИСЛЕНИЯ~$h_2(K)$ БЫЛО ПРЕДЛОЖЕНО НЕСКОЛЬКО СПОСОБОВ:
хСЛИ $M$---ПРОСТОЕ ЧИСЛО И~$h_1(K)=K \bmod M$, МОЖНО ПОЛОЖИТЬ~$h_2(K)=1+(K
\bmod (M-1))$; НО ТАК КАК $M-1$~ЧЕТНО, БЫЛО БЫ ЛУЧШЕ ПОЛОЖИТЬ~$h_2(K)=1+(K
\bmod (M-2))$. ¤ТО НАВОДИТ НА МЫСЛЬ О ТАКОМ ВЫБОРЕ~$M$, ЧТОБЫ~$M$ И~$M-2$
БЫЛИ ПРОСТЫМИ ЧИСЛАМИ-БЛИЗНЕЦАМИ, НАПРИМЕР~1021 И~1019. ьОЖНО
ВЗЯТЬ~$h_2(K)=1+(\floor{K/M} \bmod (M-2))$, ИБО ЧАСТНОЕ~$\floor{K/M}$
МОЖНО ПОЛУЧИТЬ В РЕГИСТРЕ КАК ПОБОЧНЫЙ ПРОДУКТ ВЫЧИСЛЕНИЯ~$h_1(K)$.

хСЛИ~$M=2^m$ И ИСПОЛЬЗУЕТСЯ ХЕШИРОВАНИЕ УМНОЖЕНИЕМ, $h_2(K)$~МОЖНО
ПОЛУЧИТЬ, ПРОИЗВОДЯ СДВИГ ЕЩЕ НА $m$~БИТОВ ВЛЕВО И ВЫПОЛНЯЯ ОПЕРАЦИЮ "ИЛИ"
С~1, ТАК ЧТО К ПОСЛЕДОВАТЕЛЬНОСТИ КОМАНД~(5) НУЖНО ДОБАВИТЬ
$$
\mixcode
ENTA  & 0   &  юЧИСТИТЬ |rA|.
SLB   & m   &  ёДВИГ |rAX| НА $m$~БИТОВ ВЛЕВО.
ORR   & =1= &  $|rA|\asg |rA|\lor 1$.
\endmixcode
\eqno(24)
$$
¤ТО БЫСТРЕЕ МЕТОДА ДЕЛЕНИЯ.

т КАЖДОМ ИЗ ПРЕДЛОЖЕННЫХ ВЫШЕ МЕТОДОВ $h_1(K)$ И~$h_2(K)$ ЯВЛЯЮТСЯ
"НЕЗАВИСИМЫМИ" В ТОМ СМЫСЛЕ, ЧТО НА РАЗЛИЧНЫХ КЛЮЧАХ ЗНАЧЕНИЯ ОБЕИХ
ФУНКЦИЙ~$h_1$  И~$h_2$ СОВПАДАЮТ С ВЕРОЯТНОСТЬЮ~$O(1/M^2)$, А НЕ С
ВЕРОЯТНОСТЬЮ~$O(1/M)$. ¤МПИРИЧЕСКИЕ ПРОВЕРКИ ПОКАЗЫВАЮТ, ЧТО ЧИСЛО ПРОБ В
АЛГОРИТМЕ~D ПРИ НЕЗАВИСИМЫХ ХЕШ-ФУНКЦИЯХ, В СУЩНОСТИ, НЕ ОТЛИЧИМО ОТ ЧИСЛА
ПРОБ, КОТОРОЕ ПОТРЕБОВАЛОСЬ, ЕСЛИ БЫ КЛЮЧИ ВСТАВЛЯЛИСЬ В ТАБЛИЦУ
СЛУЧАЙНО; "ОКУЧИВАНИЯ", ИМЕЮЩЕГО МЕСТО В АЛГОРИТМЕ~L, ЗДЕСЬ ПРАКТИЧЕСКИ НЕТ.

ьОЖНО ТАКЖЕ ДОПУСТИТЬ ЗАВИСИМОСТЬ~$h_2(K)$ ОТ~$h_1(K)$ (КАК ПРЕДЛОЖИЛ В
1968~Г.\ у.~ъНОТТ); НАПРИМЕР, ЕСЛИ $M$---ПРОСТОЕ ЧИСЛО, ПОЛОЖИМ
$$
h_2(K)=\cases{
1, & ЕСЛИ $h_1(K)=0$;\cr
M-h_1(K), & ЕСЛИ $h_1(K)>0$.\cr
}
\eqno(25)
$$
¤ТОТ МЕТОД БЫСТРЕЕ ПОВТОРНОГО ДЕЛЕНИЯ, НО ОН ВСЕ ЖЕ ПРИВОДИТ К
\emph{ВТОРИЧНОМУ ОКУЧИВАНИЮ,} ТРЕБУЯ НЕСКОЛЬКО БОЛЬШЕ ПРОБ ИЗ-ЗА
УВЕЛИЧЕНИЯ ВЕРОЯТНОСТИ ТОГО, ЧТО ДВА ИЛИ БОЛЕЕ КЛЮЧЕЙ ПОСЛЕДУЮТ ОДНИМ И
ТЕМ ЖЕ ПУТЕМ. ЇОРМУЛЫ, ВЫВЕДЕННЫЕ НИЖЕ, МОЖНО ИСПОЛЬЗОВАТЬ, ЧТОБЫ
ОПРЕДЕЛИТЬ, ПЕРЕВЕШИВАЕТ ЛИ ВЫИГРЫШ ВО ВРЕМЕНИ ХЕШИРОВАНИЯ ПОТЕРИ НА ПРОБАХ.

%% 621

рЛГОРИТМЫ~L И~D ОЧЕНЬ ПОХОЖИ, НО ИМЕЮТ И ДОСТАТОЧНО РАЗЛИЧИЙ, ПОЭТОМУ
ПОЛЕЗНО СРАВНИТЬ ВРЕМЕНА РАБОТЫ СООТВЕТСТВУЮЩИХ ПРОГРАММ ДЛЯ~\MIX.

     
\prog D.(юТКРЫТАЯ АДРЕСАЦИЯ С ДВОЙНЫМ ХЕШИРОВАНИЕМ.)
ЄАК КАК ЭТА ПРОГРАММА ВЕСЬМА НАПОМИНАЕТ ПРОГРАММУ~L, ОНА ПРИВОДИТСЯ БЕЗ
КОММЕНТАРИЕВ. чДЕСЬ~$|rI2|\equiv c-1$.

\code
START&LDX &K        &1
     &ENTA&0        &1
     &DIV &=M=      &1
     &STX &*+1(0:2) &1
     &ENT1&*        &1
     &LDX &TABLE,1  &1
     &ёьЁї&K        &1
     &JE  &SUCCESS  &1
     &JXZ &4F       &1-S1
     &SRAX&5        &A-S1
     &DIV &=M-2=    &A-S1
     &STX &*+1(0:2) &A-S1
     &ENT2&*        &A-S1
     &LDA &K        &A-S1
3H   &DEC1&1,2      &C-1
     &J1NN&*+2      &C-1
     &INC1&M        &B
     &CMPA&TABLE,1  &C-1
     &JE  &SUCCESS  &C-1
     &LDX &TABLE,1  &C-1-S2
     &JXNZ&3B       &C-1-S2
4H   &LDX &VACANCIES&1-S
     &JXZ &OVERFLOW &1-S
     &DECX&1        &1-S
     &STX &VACANCIES&1-S
     &LDA &K        &1-S
     &STA &TABLE,1  &1-S
\endcode
\progend
ёЧЕТЧИКИ ЧАСТОТ~$A$, $C$, $S1$, $S2$ ИМЕЮТ ТОТ ЖЕ СМЫСЛ, ЧТО И
В ПРОГРАММЕ~C. ёРЕДНЕЕ ЗНАЧЕНИЕ ПЕРЕМЕННОЙ~$B$ ПРИМЕРНО РАВНО~$(C-1)/2$.
(хСЛИ СУЗИТЬ ДИАПАЗОН~$h_2(K)$, СКАЖЕМ,
ДО~$1\le h_2(K)\le {1\over2} M$,
ЗНАЧЕНИЕ~$B$ СОСТАВИЛО БЫ ЛИШЬ~$(C-1)/4$, ВЕРОЯТНО, УВЕЛИЧЕНИЕ ЧИСЛА ПРОБ
НЕ СВЕДЕТ НА НЕТ ЭТО УВЕЛИЧЕНИЕ СКОРОСТИ.) хСЛИ В ТАБЛИЦЕ $N=\alpha M$~КЛЮЧЕЙ,
СРЕДНЕЕ ЗНАЧЕНИЕ~$A$, РАЗУМЕЕТСЯ, РАВНО~$\alpha$ ДЛЯ НЕУДАЧНОГО
ПОИСКА И~1 ДЛЯ УДАЧНОГО. ъАК И В АЛГОРИТМЕ~C, СРЕДНЕЕ ЗНАЧЕНИЕ~$S1$ ДЛЯ
НЕУДАЧНОГО ПОИСКА СОСТАВЛЯЕТ~$1-{1\over2}((N-1)/M)\approx
1-{1\over2}\alpha$. ЄРУДНО ТОЧНО ОПРЕДЕЛИТЬ СРЕДНЕЕ ЧИСЛО ПРОБ, ОДНАКО
ЭМПИРИЧЕСКИЕ ПРОВЕРКИ ПОКАЗЫВАЮТ ХОРОШЕЕ СОГЛАСИЕ С ВЫВЕДЕННЫМИ НИЖЕ
ФОРМУЛАМИ ДЛЯ "РАВНОМЕРНОГО ОПРОБОВАНИЯ":
$$
\eqalignno{
C'_N&={M+1\over M+1-N}\approx(1-\alpha)^{-1} \rem{(НЕУДАЧНЫЙ ПОИСК)};&(26)\cr
C_N&={M+1\over N}(H_{M+1}-H_{M+1-N}) \approx-\alpha^{-1}\ln (1-\alpha)
\rem{(УДАЧНЫЙ ПОИСК)},&(27)\cr
}
$$
ЕСЛИ~$h_1(K)$ И~$h_2(K)$ НЕЗАВИСИМЫ. ъОГДА ЖЕ $h_2(K)$~ЗАВИСИТ ОТ~$h_1(K)$,
 КАК В~(25), ВТОРИЧНОЕ ОКУЧИВАНИЕ ВЫЗЫВАЕТ УВЕЛИЧЕНИЕ СРЕДНИХ
%%622
ЗНАЧЕНИЙ ДО
$$
\eqalignno{
C'_N &={M+1\over M+1-N}-{N\over M+1}+H_{M+1}-H_{M+1-N}+O(M)^{-1}\approx\cr
&\approx(1-\alpha)^{-1}-\alpha-\ln(1-\alpha);&(28)\cr
C_N&=1+H_{M+1}-H_{M+1-N}-{N\over 2(M+1)}
-(H_{M+1}-H_{M+1-N})/N+O(N^{-1})\approx\cr
&\approx 1-\ln(1-\alpha)-{1\over2}\alpha. &(29) \cr
}
$$
(ёМ.~УПР.~44.) чАМЕТИМ, ЧТО, КОГДА ТАБЛИЦА ЗАПОЛНЯЕТСЯ, Т.~Е.~КОГДА $N
$~СТРЕМИТСЯ К~$M$, ЗНАЧЕНИЕ~$C_N$ ПРИБЛИЖАЕТСЯ К~$H_{M+1}-1$,
А~$C'_N$---К~$H_{M+1}-{1\over2}$; ЭТО МНОГО ЛУЧШЕ, ЧЕМ В СЛУЧАЕ АЛГОРИТМА~L,
НО НЕ СТОЛЬ ХОРОШО, КАК В МЕТОДАХ ЦЕПОЧЕК.

яОСКОЛЬКУ В АЛГОРИТМЕ~L ПРОБЫ ЗАНИМАЮТ НЕСКОЛЬКО МЕНЬШЕ ВРЕМЕНИ, ДВОЙНОЕ
ХЕШИРОВАНИЕ ПРЕДПОЧТИТЕЛЬНО ЛИШЬ ПРИ ЗАПОЛНЕННОЙ ТАБЛИЦЕ. эА РИС.~42
СРАВНИВАЮТСЯ СРЕДНИЕ ВРЕМЕНА РАБОТЫ ПРОГРАММ~L, D И МОДИФИЦИРОВАННОЙ
ПРОГРАММЫ~D (ПРИЧЕМ ЭТА МОДИФИКАЦИЯ ВЛЕЧЕТ ЗА СОБОЙ ВТОРИЧНОЕ СКУЧИВАНИЕ):
МЫ ЗАМЕНЯЕМ ДОВОЛЬНО МЕДЛЕННОЕ ВЫЧИСЛЕНИЕ~$h_2(K)$ В СТРОКАХ~10--13 НА ТРИ
КОМАНДЫ
$$
\mixcode
ENN2  & -M-1, 1 & $c\asg M-i$.
J1NZ  & *+2
ENT2  & 0       & хСЛИ $i=0$, $c\asg 1$.
\endmixcode
\eqno(30)
$$
\picture{ЁИС. 42.  тРЕМЯ УДАЧНОГО ПОИСКА ДЛЯ ТРЕХ СХЕМ ОТКРЫТОЙ АДРЕСАЦИИ.}
%%623
т ДАННОМ СЛУЧАЕ ВТОРИЧНОЕ СКУЧИВАНИЕ ЛУЧШЕ НЕЗАВИСИМОГО ПОВТОРНОГО ХЕШИРОВАНИЯ.

эА ДВОИЧНОЙ ¤ть МЫ МОГЛИ БЫ ИНЫМ СПОСОБОМ УСКОРИТЬ ВЫЧИСЛЕНИЕ~$h_2(K)$,
ЗАМЕНИВ СТРОКИ~10--13, СКАЖЕМ, НА
$$
\mixcode
AND  & =511=   & $|rA|\asg |rA| \bmod 512$.
STA  & *+1(0:2)
ENT2 & *       & $c\asg |rA|+1$.
\endmixcode
\eqno(31)
$$
ЕСЛИ $M$---ПРОСТОЕ ЧИСЛО, БОЛЬШЕЕ~512. ¤ТА ИДЕЯ, ПРЕДЛОЖЕННАЯ сЕЛЛОМ И
ъАМ\'А [{\sl CACM,\/} {\bf 13} (1970), 675--677], НЕЗАВИСИМО ПРИДУМАВШИМИ
АЛГОРИТМ~D, ПОЗВОЛЯЕТ ИЗБЕЖАТЬ ВТОРИЧНОГО СКУЧИВАНИЯ БЕЗ ЗАТРАТ НА
ПОВТОРНОЕ ДЕЛЕНИЕ.

сЫЛО ПРЕДЛОЖЕНО МНОГО ДРУГИХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ПРОБ В КАЧЕСТВЕ УЛУЧШЕНИЙ
АЛГОРИТМА~L, НО, ПО-ВИДИМОМУ, НИ ОДНА ИЗ НИХ НЕ ЛУЧШЕ АЛГОРИТМА~D. (сЫТЬ
МОЖЕТ, ИСКЛЮЧЕНИЕ СОСТАВЛЯЕТ МЕТОД, ОПИСАННЫЙ В УПР.~20.)
\picture{ ЁИС. 43. ёКОЛЬКО РАЗ КОМПИЛЯТОР ИЩЕТ ИМЕНА ПЕРЕМЕННЫХ В ТИПИЧНОМ
СЛУЧАЕ. шМЕНА ВЫПИСАНЫ СЛЕВА НАПРАВО В ПОРЯДКЕ ИХ ПЕРВОГО  ПОЯВЛЕНИЯ.}
\section шЗМЕНЕНИЕ, ПРЕДЛОЖЕННОЕ сРЕНТОМ. ЁИЧАРД сРЕНТ НАШЕЛ ТАКОЙ СПОСОБ
ИЗМЕНЕНИЯ АЛГОРИТМА~D, ЧТОБЫ СРЕДНЕЕ ВРЕМЯ УДАЧНОГО ПОИСКА ОСТАВАЛОСЬ
ОГРАНИЧЕННЫМ ПО МЕРЕ ЗАПОЛНЕНИЯ ТАБЛИЦЫ. хГО МЕТОД ОСНОВАН НА ТОМ ФАКТЕ,
ЧТО ВО МНОГИХ ПРИЛОЖЕНИЯХ
%%624
УДАЧНЫЙ ПОИСК ПРОИЗВОДИТСЯ ГОРАЗДО ЧАЩЕ ВСТАВОК; ПОЭТОМУ ОН ПРЕДЛАГАЕТ
ДЕЛАТЬ БОЛЬШЕ РАБОТЫ ПРИ ВСТАВКЕ ЭЛЕМЕНТА, nepeМЕЩАЯ ЗАПИСИ, ЧТОБЫ
УМЕНЬШИТЬ ОЖИДАЕМОЕ ВРЕМЯ ВЫБОРКИ.
[{\sl CACM,\/} {\bf 16} (1973), 105--109.]

эАПРИМЕР, НА РИС.~43 ПОКАЗАНО, СКОЛЬКО РАЗ ТОТ ИЛИ ИНОЙ ИДЕНТИФИКАТОР
ВСТРЕЧАЛСЯ В ТИПИЧНОЙ ПРОЦЕДУРЕ НА~PL/1. ёУДЯ ПО ЭТИМ ДАННЫМ, КОМПИЛЯТОР
С~PL/1, ИСПОЛЬЗУЮЩИЙ РАССЕЯННУЮ ТАБЛИЦУ ДЛЯ ХРАНЕНИЯ ИМЕН ПЕРЕМЕННЫХ,
БУДЕТ ИСКАТЬ МНОГИЕ ИМЕНА ПЯТЬ ИЛИ БОЛЕЕ РАЗ, А ВСТАВЛЯТЬ ИХ ЛИШЬ ОДНАЖДЫ.
 рНАЛОГИЧНО сЕЛЛ И~ъАМ\'А ОБНАРУЖИЛИ, ЧТО КОМПИЛЯТОР С~ъОБОЛА ИСПОЛЬЗОВАЛ
СВОЙ АЛГОРИТМ ТАБЛИЦ СИМВОЛОВ $10988$~РАЗ ВО ВРЕМЯ КОМПИЛЯЦИИ ПРОГРАММЫ И
СОВЕРШИЛ ЛИШЬ $735$~ВСТАВОК, Т.~Е.~НА ОДИН НЕУДАЧНЫЙ ПОИСК ПРИХОДИЛОСЬ
ПРИМЕРНО 14~УДАЧНЫХ.
шНОГДА ТАБЛИЦА СОЗДАЕТСЯ ТОЛЬКО ОДИН РАЗ (НАПРИМЕР, ТАБЛИЦА СИМВОЛИЧЕСКИХ
КОДОВ ОПЕРАЦИЙ В АВТОКОДЕ) И ИСПОЛЬЗУЕТСЯ ПОСЛЕ ЭТОГО ИСКЛЮЧИТЕЛЬНО ДЛЯ
ВЫБОРКИ.

сРЕНТ ПРЕДЛОЖИЛ СЛЕДУЮЩИМ ОБРАЗОМ ИЗМЕНИТЬ ПРОЦЕСС ВСТАВКИ В АЛГОРИТМЕ~D.
яРЕДПОЛОЖИМ, ЧТО ПРИ НЕУДАЧНОМ ПОИСКЕ БЫЛИ ОПРОБОВАНЫ ЯЧЕЙКИ
$$
p_0, p_1,~\ldots, p_{t-1}, p_t,
$$
ГДЕ~$p_j=(h_1(K)-jh_2(K))\bmod M$ И УЗЕЛ~$|TABLE|[p_t]$ ПУСТ. хСЛИ~$t\le
1$, МЫ, КАК ОБЫЧНО, ВСТАВЛЯЕМ~$K$ В ПОЗИЦИЮ~$p_t$, НО ЕСЛИ~$t\ge2$,
ВЫЧИСЛЯЕМ~$c_0=h_2(K_0)$, ГДЕ~$K_0=|KEY|[p_0]$, И СМОТРИМ, СВОБОДНО ЛИ
В~$|TABLE| [(p_0-c_0)\bmod M$]. хСЛИ УСЛОВИЕ ВЫПОЛНЕНО, ПОМЕЩАЕМ В ДАННЫЙ
УЗЕЛ СОДЕРЖИМОЕ ЯЧЕЙКИ~$|TABLE|[p_0]$ И ВСТАВЛЯЕМ~$K$ В ПОЗИЦИЮ~$p_0$. ¤ТО
УВЕЛИЧИВАЕТ ВРЕМЯ ВЫБОРКИ $K_0$ НА ОДИН ШАГ, НО УМЕНЬШАЕТ ВРЕМЯ
ВЫБОРКИ~$K$ НА $t\ge2$~ШАГОВ.  тЫИГРЫШ НАЛИЦО. рНАЛОГИЧНО, ЕСЛИ
В~$|TABLE|[(p_0-c_0)\bmod M]$ ЗАНЯТО И~$t\ge3$, МЫ ПРОБУЕМ ЯЧЕЙКУ~$|TABLE|
[(p_0-2c_0)\bmod M]$;
ЕСЛИ И ТАМ ЗАНЯТО, ВЫЧИСЛЯЕМ~$c_1=h_2(|KEY|[p_1])$ И ПРОБУЕМ
$|TABLE|[(p_1-c_1)\bmod M]$ И~Т.~Д. тООБЩЕ,
ПУСТЬ~$c_j=h_2(|KEY|[p_j])$ И~$p_{j,k}=(p_j-kc_j)\bmod M$; ЕСЛИ
ПОЗИЦИИ~$|TABLE|[p_{j,k}]$ ОКАЗАЛИСЬ ЗАНЯТЫМИ ПРИ ВСЕХ~$j, k$, ТАКИХ,
ЧТО~$j+k<r$, И ЕСЛИ~$t\ge r+1$, ПРОСМАТРИВАЕМ   УЗЛЫ~$|TABLE|[p_{0,r}]$,
$|TABLE|[p_{1, r-1}]$,~\dots, $|TABLE|[p_{r-1, 1}]$. хСЛИ ПЕРВОЙ СВОБОДНОЙ
ОКАЗАЛАСЬ ПОЗИЦИЯ~$p_{j,r-j}$,
УСТАНАВЛИВАЕМ~$|TABLE|[p_{j, r-j}]\asg |TABLE|[p_j]$ И
ВСТАВЛЯЕМ~$K$ В ПОЗИЦИЮ~$p_j$.

ъАК ЯВСТВУЕТ ИЗ АНАЛИЗА сРЕНТА, СРЕДНЕЕ ЧИСЛО ПРОБ В ПРОЦЕССЕ УДАЧНОГО
ПОИСКА УМЕНЬШИЛОСЬ (СМ.~РИС.~44) И ЕГО МАКСИМАЛЬНОЕ ЗНАЧЕНИЕ ПРИБЛИЖЕННО
РАВНО~$2.49$.

ўИСЛО~$t+1$ ПРОБ ПРИ НЕУДАЧНОМ ПОИСКЕ В РЕЗУЛЬТАТЕ ПРЕДЛОЖЕННОГО ИЗМЕНЕНИЯ
НЕ УМЕНЬШИЛОСЬ; ОНО ОСТАЛОСЬ НА УРОВНЕ,  УКАЗАННОМ ФОРМУЛОЙ~(26), И
ДОСТИГАЕТ~$(M+1)/2$ ДЛЯ ЗАПОЛНЕННОЙ  ТАБЛИЦЫ. яРИ ВСТАВКЕ ФУНКЦИЮ~$h_2$
ПРИХОДИТСЯ В СРЕДНЕМ ВЫЧИСЛЯТЬ
%%625
$\alpha^2+\alpha^5+{1\over3}\alpha^6+\ldots$~РАЗ. ёОГЛАСНО АНАЛИЗУ
сРЕНТА, ПРИ~$\alpha\to 1$, ЭТА ВЕЛИЧИНА ИМЕЕТ ПОРЯДОК~$\sqrt{M}$. эАКОНЕЦ,
КОГДА МЫ РЕШАЕМ, КАК ПРОИЗВЕСТИ ВСТАВКУ, СОВЕРШАЕТСЯ ОКОЛО
$\alpha^2+\alpha^4+{4\over3}\alpha^5+\alpha^6+\ldots$~ДОПОЛНИТЕЛЬНЫХ ПРОБ.

\section єДАЛЕНИЯ. ьНОГИЕ ПРОГРАММИСТЫ СВЯТО ВЕРЯТ В АЛГОРИТМЫ И
ОЧЕНЬ УДИВЛЯЮТСЯ, ОБНАРУЖИВ, ЧТО \emph{ОЧЕВИДНЫЙ СПОСОБ УДАЛЕНИЯ ЗАПИСЕЙ
ИЗ РАССЕЯННОЙ ТАБЛИЦЫ НЕ РАБОТАЕТ.} эАПРИМЕР, ПРИ ПОПЫТКЕ УДАЛИТЬ
КЛЮЧ~|EN| (СМ.~РИС.~41) НЕЛЬЗЯ ПРОСТО ПОМЕТИТЬ ЭТУ ПОЗИЦИЮ В ТАБЛИЦЕ КАК
СВОБОДНУЮ, ИБО ДРУГОЙ КЛЮЧ~|FEM| ВНЕЗАПНО ОКАЖЕТСЯ ПОТЕРЯННЫМ! (тСПОМНИМ,
ЧТО EN И FEM ИМЕЮТ ОДИНАКОВЫЕ ХЕШ-КОДЫ. яРИ ПОИСКЕ~|FEM| МЫ НАТКНЕМСЯ НА
СВОБОДНЫЙ УЗЕЛ, ЧТО СВИДЕТЕЛЬСТВУЕТ О ТОМ, ЧТО ПОИСК НЕУДАЧЕН.)
рНАЛОГИЧНОЕ СООБРАЖЕНИЕ СПРАВЕДЛИВО ДЛЯ АЛГОРИТМА~C, В КОТОРОМ ИМЕЕТ
МЕСТО СРАСТАНИЕ СПИСКОВ; ПРЕДСТАВЬТЕ СЕБЕ УДАЛЕНИЕ КЛЮЧЕЙ~|TO| И~|FIRE|
(СМ.~РИС.~40).

тООБЩЕ ГОВОРЯ, МОЖНО ПРОИЗВОДИТЬ УДАЛЕНИЯ, ПОМЕЩАЯ В СООТВЕТСТВУЮЩУЮ
ЯЧЕЙКУ СПЕЦИАЛЬНОЕ ЗНАЧЕНИЕ, Т.~Е.~ИМЕЯ ТРИ ТИПА ПОЗИЦИЙ В ТАБЛИЦЕ:
СВОБОДНЫЕ, ЗАНЯТЫЕ И УДАЛЕННЫЕ. яРИ ПОИСКЕ КЛЮЧА УДАЛЕННЫЕ ПОЗИЦИИ НУЖНО
ТРАКТОВАТЬ КАК ЗАНЯТЫЕ. т СЛУЧАЕ НЕУДАЧНОГО ПОИСКА КЛЮЧ МОЖНО ВСТАВИТЬ В
ПЕРВУЮ ВСТРЕЧЕННУЮ УДАЛЕННУЮ ИЛИ СВОБОДНУЮ ПОЗИЦИЮ.

юДНАКО ЭТА ИДЕЯ ПРИМЕНИМА ТОЛЬКО ПРИ ОЧЕНЬ РЕДКИХ УДАЛЕНИЯХ, ПОТОМУ ЧТО
ОДНАЖДЫ ЗАНЯТАЯ ПОЗИЦИЯ НЕ МОЖЕТ СНОВА СТАТЬ СВОБОДНОЙ. яОСЛЕ ДЛИННОЙ
ПОСЛЕДОВАТЕЛЬНОСТИ ВСТАВОК И УДАЛЕНИЙ ВСЕ СВОБОДНОЕ ПРОСТРАНСТВО В КОНЦЕ
КОНЦОВ ИСЧЕЗНЕТ И КАЖДЫЙ НЕУДАЧНЫЙ ПОИСК БУДЕТ ТРЕБОВАТЬ $M$~ПРОБ!
ъРОМЕ ТОГО, ПРОБЫ ПОТРЕБУЮТ БОЛЬШЕ ВРЕМЕНИ, ТАК КАК В ШАГЕ~D4         
НЕОБХОДИМО ПРОВЕРЯТЬ, НЕ ВЕРНУЛОСЬ ЛИ~$i$ К СВОЕМУ НАЧАЛЬНОМУ ЗНАЧЕНИЮ, А
ЧИСЛО ПРОБ ПРИ УДАЧНОМ ПОИСКЕ ВОЗРАСТЕТ С~$C_N$ ДО~$C'_N$.
         
хСЛИ ИСПОЛЬЗУЕТСЯ ЛИНЕЙНОЕ ОПРОБОВАНИЕ (Т.~Е.~АЛГОРИТМ~L), МОЖНО
ДЕЙСТВОВАТЬ РАЦИОНАЛЬНЕЕ, ПРИ УСЛОВИИ ЧТО МЫ СОГЛАСНЫ ПОТРАТИТЬ НЕКОТОРЫЕ
ДОПОЛНИТЕЛЬНЫЕ УСИЛИЯ НА УДАЛЕНИЯ.

\alg R.(єДАЛЕНИЕ ПРИ ЛИНЕЙНОМ ОПРОБОВАНИИ.)
эАСТОЯЩИЙ АЛГОРИТМ УДАЛЯЕТ ЗАПИСЬ ИЗ ДАННОЙ ПОЗИЦИИ~$|TABLE| [i]$
ОТКРЫТОЙ РАССЕЯННОЙ ТАБЛИЦЫ, ПОСТРОЕННОЙ С ПОМОЩЬЮ АЛГОРИТМА~L.

\st[юСВОБОДИТЬ ЯЧЕЙКУ.] юТМЕТИТЬ ЯЧЕЙКУ~$|TABLE|[i]$ КАК СВОБОДНУЮ И
УСТАНОВИТЬ~$j\asg i$.

\st[єМЕНЬШИТЬ~$i$.] єСТАНОВИТЬ~$i\asg i-1$ И, ЕСЛИ ЗНАЧЕНИЕ~$i$ СТАЛО
ОТРИЦАТЕЛЬНЫМ, УСТАНОВИТЬ~$i\asg i+M$.

\st[яРОВЕРИТЬ~$|TABLE|[i]$.] хСЛИ В~$|TABLE|[i]$ СВОБОДНО, АЛГОРИТМ
ЗАВЕРШАЕТСЯ.  т ПРОТИВНОМ СЛУЧАЕ УСТАНОВИТЬ
%% 626
$r\asg h(|KEY| [i])$---ПЕРВОНАЧАЛЬНЫЙ ХЕШ-КОД КЛЮЧА, ХРАНЯЩЕГОСЯ ТЕПЕРЬ В
ПОЗИЦИИ~$i$. хСЛИ~$i\le r<j$, ИЛИ~$r<j<i$, ИЛИ~$j<i\le r$ (ДРУГИМИ
СЛОВАМИ, ЕСЛИ $r$~ЛЕЖИТ ЦИКЛИЧЕСКИ МЕЖДУ~$i$ И~$j$), ВЕРНУТЬСЯ НА~\stp{2}.

\st[яЕРЕМЕСТИТЬ ЗАПИСЬ.] єСТАНОВИТЬ~$|TABLE| [j]\asg |TABLE| [i]$ И
ВЕРНУТЬСЯ НА~\stp{1}.
\algend

т УПР.~22 ПОКАЗАНО, ЧТО ЭТОТ АЛГОРИТМ НЕ ВЫЗЫВАЕТ УХУДШЕНИЯ
ХАРАКТЕРИСТИК, Т.Е.~СРЕДНЕЕ ЧИСЛО ПРОБ, ПРЕДСКАЗАННОЕ ФОРМУЛАМИ~(22)
И~(23), ОСТАЕТСЯ ПРЕЖНИМ. (сОЛЕЕ СЛАБЫЙ РЕЗУЛЬТАТ ДЛЯ УДАЛЕНИЯ ИЗ ДЕРЕВА
БЫЛ ДОКАЗАН В ТЕОРЕМЕ~6.2.2H.) юДНАКО СПРАВЕДЛИВОСТЬ АЛГОРИТМА~R СИЛЬНО
ЗАВИСИТ ОТ ТОГО ФАКТА, ЧТО ИСПОЛЬЗУЕТСЯ ЛИНЕЙНОЕ ОПРОБОВАНИЕ; В СЛУЧАЕ
АЛГОРИТМА~D НЕ СУЩЕСТВУЕТ АНАЛОГИЧНОЙ ПРОЦЕДУРЫ УДАЛЕНИЯ.

ЁАЗУМЕЕТСЯ, ЕСЛИ ИСПОЛЬЗУЕТСЯ МЕТОД ЦЕПОЧЕК И ДЛЯ КАЖДОГО ХЕШ-КОДА ИМЕЕТСЯ
ОТДЕЛЬНЫЙ СПИСОК, УДАЛЕНИЕ НЕ ЯВЛЯЕТСЯ ПРОБЛЕМОЙ, ТАК КАК СВОДИТСЯ ПРОСТО
К УДАЛЕНИЮ ИЗ СВЯЗАННОГО ЛИНЕЙНОГО СПИСКА. єДАЛЕНИЯ ДЛЯ АЛГОРИТМА~C
ОБСУЖДАЮТСЯ В УПР.~23.

\section *рНАЛИЗ АЛГОРИТМОВ. яРИ ХЕШИРОВАНИИ МЫ ПОЛАГАЕМСЯ НА
ВЕРОЯТНОСТНЫЕ ЗАКОНЫ, ПОЭТОМУ ОСОБЕННО ВАЖНО ЗНАТЬ ПОВЕДЕНИЕ МЕТОДОВ
ХЕШИРОВАНИЯ В СРЕДНЕМ. эАИХУДШИЙ СЛУЧАЙ В ЭТИХ АЛГОРИТМАХ ПОЧТИ
НЕМЫСЛИМО ПЛОХ, ТАК ЧТО НАМ НЕОБХОДИМА УВЕРЕННОСТЬ В ТОМ, ЧТО ПОВЕДЕНИЕ В
СРЕДНЕМ ЯВЛЯЕТСЯ ОЧЕНЬ ХОРОШИМ.

яРЕЖДЕ ЧЕМ ПРИСТУПИТЬ К АНАЛИЗУ ЛИНЕЙНОГО ОПРОБОВАНИЯ И~Т.~П., РАССМОТРИМ
ВЕСЬМА ПРИБЛИЖЕННУЮ МОДЕЛЬ ДАННОЙ СИТУАЦИИ, КОТОРУЮ МОЖНО НАЗВАТЬ
\dfn{РАВНОМЕРНЫМ ХЕШИРОВАНИЕМ} (СР.~С~W.~W.~Peterson, {\sl IBM J.~Research
\& Development,\/} {\bf 1} (1957), 135--136). т ДАННОЙ МОДЕЛИ
ПРЕДПОЛАГАЕТСЯ, ЧТО КЛЮЧИ ПОПАДАЮТ
В СЛУЧАЙНЫЕ ПОЗИЦИИ ТАБЛИЦЫ, ТАК ЧТО ВСЕ $\perm{M}{N}$~ВОЗМОЖНЫХ
КОНФИГУРАЦИЙ ИЗ $N$~ЗАНЯТЫХ И~$M-N$~СВОБОДНЫХ ЯЧЕЕК РАВНОВЕРОЯТНЫ. ¤ТА
МОДЕЛЬ СОВЕРШЕННО НЕ УЧИТЫВАЕТ ВЛИЯНИЯ ПЕРВИЧНОГО ИЛИ ВТОРИЧНОГО
ОКУЧИВАНИЯ; В СУЩНОСТИ, ПРЕДПОЛАГАЕТСЯ, ЧТО ЗАНЯТОСТЬ ЛЮБОЙ ЯЧЕЙКИ НЕ
ЗАВИСИТ ОТ. ЗАНЯТОСТИ ДРУГИХ. фЛЯ РАССМАТРИВАЕМОЙ МОДЕЛИ ВЕРОЯТНОСТЬ ТОГО,
ЧТО ДЛЯ ВСТАВКИ $(N+1)\hbox{-ГО}$~ЭЛЕМЕНТА ТРЕБУЕТСЯ РОВНО $r$~ПРОБ,
РАВНА ЧИСЛУ КОНФИГУРАЦИЙ, В КОТОРЫХ ЗАНЯТО $r-1$~ДАННЫХ ЯЧЕЕК, А
ЕЩЕ ОДНА ДАННАЯ ЯЧЕЙКА СВОБОДНА, ДЕЛЕННОМУ НА~$\perm{M}{N}$, Т.~Е.
$$
P_r=\perm{M-r}{N-r+1}\bigg/\perm{M}{N};
$$
СЛЕДОВАТЕЛЬНО, СРЕДНЕЕ ЧИСЛО ПРОБ ДЛЯ РАВНОМЕРНОГО ХЕШИРОВАНИЯ
%%627
СОСТАВЛЯЕТ
$$
\eqalignno{
C'_N &= \sum_{1\le r\le M} rP_r
=M+1-\sum_{1\le r\le M}(M+1-r)P_r=\cr
&=M+1-\sum_{1\le r\le M} (M+1-r)\perm{M-r}{M-N-1}\bigg/\perm{M}{N}=\cr
&=M+1-\sum_{1\le r\le M}(M-N)\perm{M+1-r}{M-N}\bigg/\perm{M}{N}=\cr
&=M+1-(M-N)\perm{M+1}{M-N+1}\bigg/\perm{M}{N}=\cr
&=M+1-(M-N){M+1\over M-N+1}={M+1\over M-N+1},
\qquad 1\le N\le M. & (32)\cr
}
$$
(ьЫ УЖЕ РЕШАЛИ, В СУЩНОСТИ, ТУ ЖЕ ЗАДАЧУ, ВОЗНИКАЮЩУЮ В СВЯЗИ СО СЛУЧАЙНОЙ
ВЫБОРКОЙ; УПР.~3.4.2-5.) яОЛАГАЯ~$\alpha=N/M$, ТОЧНУЮ ФОРМУЛУ ДЛЯ~$C'_N$
МОЖНО ПРИБЛИЖЕННО ЗАМЕНИТЬ НА
$$
{1\over 1-\alpha}=1+\alpha+\alpha^2+\alpha^3+\ldots\,.
\eqno(33)
$$
¤ТОМУ РЯДУ МОЖНО ДАТЬ ГРУБУЮ ИНТУИТИВНУЮ ИНТЕРПРЕТАЦИЮ:
С ВЕРОЯТНОСТЬЮ~$\alpha$ НУЖНА БОЛЕЕ ЧЕМ ОДНА ПРОБА, С
ВЕРОЯТНОСТЬЮ~$\alpha^2$---БОЛЕЕ ЧЕМ ДВЕ И~Т.~Д. ёООТВЕТСТВУЮЩЕЕ СРЕДНЕЕ
ЧИСЛО ПРОБ ПРИ УДАЧНОМ ПОИСКЕ РАВНО
$$
\eqalignno{
C_N&={1\over N}\sum_{0\le k<N}C'_k
={M+1\over N}\left({1\over M+1}+{1\over M}+\cdots+{1\over M-N+2}\right)=\cr
&={M+1\over N}(H_{M+1}-H_{M-N+1})
\approx {1\over \alpha}\log{1\over1-\alpha}. & (34)\cr
}
$$
ъАК ОТМЕЧАЛОСЬ ВЫШЕ, МНОГОЧИСЛЕННЫЕ ТЕСТЫ ПОКАЗАЛИ, ЧТО АЛГОРИТМ~D С
ДВУМЯ НЕЗАВИСИМЫМИ ХЕШ-ФУНКЦИЯМИ ВЕДЕТ СЕБЯ,  ПО СУЩЕСТВУ, КАК РАВНОМЕРНОЕ
ХЕШИРОВАНИЕ, И ДЛЯ ВСЕХ ПРАКТИЧЕСКИХ НУЖД МОЖНО ИСПОЛЬЗОВАТЬ
ФОРМУЛЫ~(32)--(34). эА САМОМ ДЕЛЕ ы.~уЮИБА И ¤.~ёЕМЕРЕДИ УДАЛОСЬ ДОКАЗАТЬ
ТРУДНУЮ ТЕОРЕМУ О ТОМ, ЧТО ДВОЙНОЕ ХЕШИРОВАНИЕ АСИМПТОТИЧЕСКИ
(ПРИ~$M\to\infty$) ЭКВИВАЛЕНТНО РАВНОМЕРНОМУ [БУДЕТ ОПУБЛИКОВАНО].

эА ЭТОМ АНАЛИЗ РАВНОМЕРНОГО ХЕШИРОВАНИЯ ЗАВЕРШАЕТСЯ. ўТОБЫ ИЗУЧАТЬ
ЛИНЕЙНОЕ ОПРОБОВАНИЕ И ДРУГИЕ СПОСОБЫ РАЗРЕШЕНИЯ КОЛЛИЗИИ, НУЖНО СТРОИТЬ
ТЕОРИЮ ИНЫМ, БОЛЕЕ РЕАЛИСТИЧЕСКИМ СПОСОБОМ. т ВЕРОЯТНОСТНОЙ МОДЕЛИ,
КОТОРУЮ МЫ БУДЕМ ИСПОЛЬЗОВАТЬ ДЛЯ ЭТОЙ ЦЕЛИ, ПРЕДПОЛАГАЕТСЯ, ЧТО ВСЕ
$M^N$~ВОЗМОЖНЫХ ХЕШ-ПОСЛЕДОВАТЕЛЬНОСТЕЙ
$$
a_1\ a_2\ \ldots\ a_N, \qquad 0\le a_j <M,
\eqno(35)
$$
РАВНОВЕРОЯТНЫ. чДЕСЬ $a_j$~ОБОЗНАЧАЕТ ПЕРВОНАЧАЛЬНЫЙ ХЕШ-АДРЕС КЛЮЧА,
ВСТАВЛЕННОГО В ТАБЛИЦУ В ПОЗИЦИЮ~$j$, ъАК И ВЫШЕ, СРЕДНЕЕ
%%628
ЧИСЛО ПРОБ В СЛУЧАЕ УДАЧНОГО ПОИСКА ПРИ ЛЮБОМ ДАННОМ АЛГОРИТМЕ
ОБОЗНАЧИМ ЧЕРЕЗ~$C_N$. ¤ТО ЕСТЬ СРЕДНЕЕ ЧИСЛО ПРОБ, НУЖНЫХ ДЛЯ НАХОЖДЕНИЯ
$k\hbox{-ГО}$~КЛЮЧА, УСРЕДНЕННОЕ ПО~$1\le k\le N$ ПРИ РАВНОВЕРОЯТНЫХ
КЛЮЧАХ И ПО ВСЕМ ХЕШ-ПОСЛЕДОВАТЕЛЬНОСТЯМ~(35), КОТОРЫЕ ТАКЖЕ СЧИТАЮТСЯ
РАВНОВЕРОЯТНЫМИ. рНАЛОГИЧНО, СРЕДНЕЕ ЧИСЛО ПРОБ, НЕОБХОДИМЫХ ДЛЯ ВСТАВКИ
$N\hbox{-ГО}$~КЛЮЧА, ПРИ УСЛОВИИ ЧТО ВСЕ ПОСЛЕДОВАТЕЛЬНОСТИ~(35)
РАВНОВЕРОЯТНЫ, ОБОЗНАЧИМ ЧЕРЕЗ~$C'_{N-1}$; ЭТО ЕСТЬ СРЕДНЕЕ ЧИСЛО ПРОБ В
НЕУДАЧНОМ ПОИСКЕ, ЕСЛИ В ТАБЛИЦЕ $N-1$~ЭЛЕМЕНТОВ. хСЛИ ИСПОЛЬЗУЕТСЯ
ОТКРЫТАЯ АДРЕСАЦИЯ, ТО
$$
C_N={1\over N}\sum_{0\le k < N} C'_k,
\eqno (36)
$$
ТАК ЧТО, ЗНАЯ ОДНУ ВЕЛИЧИНУ, МОЖНО ПОЛУЧИТЬ ДРУГУЮ, КАК БЫЛО СДЕЛАНО В~(34).

ёТРОГО ГОВОРЯ, ДАЖЕ ЭТА БОЛЕЕ ПРАВИЛЬНАЯ МОДЕЛЬ ИМЕЕТ ДВА НЕДОСТАТКА.
тО-ПЕРВЫХ, НЕ ВСЕ ХЕШ-ПОСЛЕДОВАТЕЛЬНОСТИ РАВНОВЕРОЯТНЫ, ПОТОМУ ЧТО САМИ
КЛЮЧИ ЯВЛЯЮТСЯ РАЗЛИЧНЫМИ. ¤ТО ДЕЛАЕТ ВЕРОЯТНОСТЬ РАВЕНСТВА~$a_1=a_2$
НЕСКОЛЬКО МЕНЬШЕЙ, ЧЕМ~$1/M$, ОДНАКО РАЗНОСТЬЮ ОБЫЧНО МОЖНО ПРЕНЕБРЕЧЬ,
ТАК КАК КОЛИЧЕСТВО ВСЕХ ВОЗМОЖНЫХ КЛЮЧЕЙ В ТИПИЧНОМ СЛУЧАЕ МНОГО
БОЛЬШЕ~$M$. (ёМ.~УПР.~24.) фАЛЕЕ, ХОРОШАЯ ХЕШ-ФУНКЦИЯ БУДЕТ
ИСПОЛЬЗОВАТЬ НЕСЛУЧАЙНОСТЬ ОБЫЧНЫХ ДАННЫХ, ДЕЛАЯ РАВЕНСТВО~$a_1=a_2$
ЕЩЕ МЕНЕЕ ВЕРОЯТНЫМ; В РЕЗУЛЬТАТЕ НАШИ ОЦЕНКИ ЧИСЛА ПРОБ БУДУТ,
 ПЕССИМИСТИЧЕСКИМИ. фРУГАЯ НЕТОЧНОСТЬ ДАННОЙ МОДЕЛИ УКАЗАНА НА РИС.~43:
КЛЮЧИ, ПОЯВИВШИЕСЯ РАНЕЕ (ЗА НЕКОТОРЫМИ ИСКЛЮЧЕНИЯМИ), РАЗЫСКИВАЮТСЯ
ЧАЩЕ. ёЛЕДОВАТЕЛЬНО, НАШИ ОЦЕНКИ~$C_N$ БУДУТ ВДВОЙНЕ ПЕССИМИСТИЧЕСКИМИ, А
АЛГОРИТМЫ НА ПРАКТИКЕ ДОЛЖНЫ РАБОТАТЬ НЕСКОЛЬКО ЛУЧШЕ, ЧЕМ ПРЕДСКАЗЫВАЕТ
НАШ АНАЛИЗ.

яОСЛЕ ЭТОЙ ПРЕАМБУЛЫ МЫ ГОТОВЫ ВЫПОЛНИТЬ "ТОЧНЫЙ" АНАЛИЗ ЛИНЕЙНОГО ОПРОБОВАНИЯ%
\note{1}%
{чДЕСЬ АВТОР НЕ МОЖЕТ УДЕРЖАТЬСЯ ОТ БИОГРАФИЧЕСКОГО ЗАМЕЧАНИЯ.
тПЕРВЫЕ ПРЕДЛАГАЕМЫЙ ВЫВОД БЫЛ СФОРМУЛИРОВАН МНОЮ В 1962~Г., ВСКОРЕ
ПОСЛЕ НАЧАЛА РАБОТЫ НАД "шСКУССТВОМ ПРОГРАММИРОВАНИЯ ДЛЯ ¤ть". ьОЙ
ПЕРВЫЙ УСПЕШНЫЙ АНАЛИЗ НЕТРИВИАЛЬНОГО АЛГОРИТМА ОКАЗАЛ СИЛЬНОЕ ВЛИЯНИЕ НА
СТРУКТУРУ ЭТИХ КНИГ. ьОГ ЛИ Я ДУМАТЬ, ЧТО ПРОЙДЕТ БОЛЕЕ ДЕСЯТИ ЛЕТ,
ПРЕЖДЕ ЧЕМ ЭТОТ ВЫВОД ПОПАДЕТ В ПЕЧАТЬ!
}.
 ўЕРЕЗ~$f(M,N)$ ОБОЗНАЧИМ ЧИСЛО ХЕШ-ПОСЛЕДОВАТЕЛЬНОСТЕЙ~(35), ТАКИХ, ЧТО
ПОЗИЦИЯ~0 ТАБЛИЦЫ БУДЕТ СВОБОДНА ПОСЛЕ ВСТАВКИ КЛЮЧЕЙ С ПОМОЩЬЮ
АЛГОРИТМА~L. шЗ КРУГОВОЙ СИММЕТРИИ ЛИНЕЙНОГО ОПРОБОВАНИЯ СЛЕДУЕТ, ЧТО
ПОЗИЦИЯ~0 СВОБОДНА С ТОЙ ЖЕ ВЕРОЯТНОСТЬЮ, ЧТО И ЛЮБАЯ ДРУГАЯ ПОЗИЦИЯ,
Т.~Е.~С ВЕРОЯТНОСТЬЮ~$1-N/M$; ИНЫМИ СЛОВАМИ,
$$
f(M,N)=\left(1-{N\over M}\right)M^N.
\eqno(37)
$$
%%629
яО ОПРЕДЕЛЕНИЮ ПОЛАГАЕМ~$f(0,0)=1$. ўЕРЕЗ~$g(M, N, k)$ ОБОЗНАЧИМ ЧИСЛО
ХЕШ-ПОСЛЕДОВАТЕЛЬНОСТЕЙ~(35), ТАКИХ, ЧТО АЛГОРИТМ ОСТАВЛЯЕТ ПОЗИЦИЮ~0
СВОБОДНОЙ, ПОЗИЦИИ С~1 ПО~$k$ ЗАНЯТЫМИ, А ПОЗИЦИЮ~$k+1$ СВОБОДНОЙ. шМЕЕМ
$$
g(M, N, k)=\perm{N}{k}f(k+1, k)f(M-k-1, N-k),
\eqno (38)
$$
ИБО ВСЕ ТАКИЕ ПОСЛЕДОВАТЕЛЬНОСТИ СОСТОЯТ ИЗ ДВУХ ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ.
юДНА (СОДЕРЖАЩАЯ $k$~ЭЛЕМЕНТОВ~$a_i\le k$) ОСТАВЛЯЕТ ПОЗИЦИЮ~0 СВОБОДНОЙ И
ПОЗИЦИИ С~1 ПО~$k$ ЗАНЯТЫМИ, А ДРУГАЯ (СОДЕРЖАЩАЯ
$N-k$~ЭЛЕМЕНТОВ~$a_j\ge k+1$) ОСТАВЛЯЕТ ПОЗИЦИЮ~$k+1$ СВОБОДНОЙ. ёУЩЕСТВУЕТ
$f(k+1, k)$~ПОСЛЕДОВАТЕЛЬНОСТЕЙ ПЕРВОГО
ТИПА И $f(M-k-1, N-k)$~ВТОРОГО И $\perm{N}{k}$~СПОСОБОВ СМЕШАТЬ ДВЕ
ТАКИЕ ПОДПОСЛЕДОВАТЕЛЬНОСТИ. эАКОНЕЦ, ПОЛОЖИМ~$P_k$ РАВНЫМ ВЕРОЯТНОСТИ
ТОГО, ЧТО ПРИ ВСТАВКЕ $(N+1)\hbox{-ГО}$~ЭЛЕМЕНТА ПОНАДОБИТСЯ РОВНО
$(k+1)$~ПРОБ; МОЖНО ПОКАЗАТЬ (СМ.~УПР.~25), ЧТО
$$
P_k=M^{-N}(g(M, N, k)+g(M, N, k+1)+\cdots+g(M, N, N)).
\eqno(39)
$$
ЄЕПЕРЬ $C'_N=\sum_{0\le k\le N} (k+1)P_k$; ПОДСТАНОВКА
СООТНОШЕНИЙ~(36)--(39) И УПРОЩЕНИЯ ДАЮТ СЛЕДУЮЩИЙ РЕЗУЛЬТАТ.

\proclaim ЄЕОРЕМА ъ. ёРЕДНЕЕ ЧИСЛО ПРОБ, НУЖНЫХ ПРИ ИСПОЛЬЗОВАНИИ
АЛГОРИТМА~L (ЕСЛИ СЧИТАТЬ, ЧТО ВСЕ~$M^N$
ХЕШ-ПОСЛЕДОВАТЕЛЬНОСТЕЙ~(35) РАВНОВЕРОЯТНЫ), РАВНО
$$
\eqalignno{
C_N&={1\over2}(1+Q_0(M, N-1))  \rem{(УДАЧНЫЙ ПОИСК);} & (40)\cr
C'_N&={1\over2}(1+Q_1(M, N))     \rem{(НЕУДАЧНЫЙ ПОИСК),} & (41)\cr
}
$$
ГДЕ
$$
\eqalignno{
Q_r(M,N)&=\perm{r}{0}+\perm{r+1}{1}{N\over M}+\perm{r+2}{2}{N(N-1)\over M^2}+\cdots=\cr
&=\sum_{k\ge0}\perm{r+k}{k}{N\over M}{N-1\over M}\cdots{N-k+1\over M}. &
(42) \cr
}
$$

\proof яОДРОБНЫЕ ВЫЧИСЛЕНИЯ ПРОВЕДЕНЫ В УПР.~27.\endmark

яОЯВЛЯЮЩАЯСЯ В ТЕОРЕМЕ ФУНКЦИЯ~$Q_r(M, N)$ ВЫГЛЯДИТ НЕ ОЧЕНЬ ИЗЯЩНО, НО В
ДЕЙСТВИТЕЛЬНОСТИ РАБОТАТЬ С НЕЙ МОЖНО. шМЕЕМ
$$
N^k-\perm{k}{2}N^{k-1}\le N(N-1)\ldots(N-k+1)\le N^k;
$$
%%630
СЛЕДОВАТЕЛЬНО, ЕСЛИ~$N/M=\alpha$, ТО
$$
\eqalign{
&\sum_{k\ge0}\perm{r+k}{r}\left(N^k-\perm{k}{2}N^{k-1}\right)
\bigg/M^k\le Q_r(M,N)\le \sum_{k\ge0}\perm{r+k}{k}N^k/M^k,\cr
&\sum_{k\ge0}\perm{r+k}{k}\alpha^k-{\alpha\over M}
\sum_{k\ge0}\perm{r+k}{k}\perm{k}{2}\alpha^{k-2}\le
Q_r(M, \alpha M)\le \sum_{k\ge 0}\perm{r+k}{k}\alpha^k,\cr
}
$$
Т.~Е.
$$
{1\over (1-\alpha)^{r+1}}-{1\over M}\perm{r+2}{2}
{\alpha\over(1-\alpha)^{r+3}}\le Q_r(M, \alpha M)\le {1\over (1-\alpha)^{r+1}}.
\eqno(43)
$$
¤ТО СООТНОШЕНИЕ ДАЕТ НАМ ХОРОШУЮ ОЦЕНКУ~$a_r(M, N)$, КОГДА $M$~ВЕЛИКО
И~$\alpha$ НЕ СЛИШКОМ БЛИЗКО К~1. (эИЖНЯЯ ОЦЕНКА БЛИЖЕ К ИСТИНЕ, ЧЕМ
ВЕРХНЯЯ.) хСЛИ~$\alpha$ ПРИБЛИЖАЕТСЯ К~1, ФОРМУЛА~(43) СТАНОВИТСЯ
БЕСПОЛЕЗНОЙ, НО, К СЧАСТЬЮ, $a_0(M, M-1)$ ЕСТЬ ФУНКЦИЯ~$a(M)$,
АСИМПТОТИЧЕСКОЕ ПОВЕДЕНИЕ КОТОРОЙ МЫ ДЕТАЛЬНО ИЗУЧИЛИ В П.~1.2.11.3;
А~$a_1(M, M-1)$ ПРОСТО РАВНО~$M$ (УПР.~50).

у.~°АЙ~МЛ.\ И~т.~ёПРУТ ИЗБРАЛИ ДРУГОЙ ПОДХОД К АНАЛИЗУ ЛИНЕЙНОГО
ОПРОБОВАНИЯ [{\sl CACM,\/} {\bf 5} (1962), 459--462]. їОТЯ ИХ МЕТОД ДАЕТ
ЛИШЬ ПРИБЛИЖЕНИЕ К ТОЧНЫМ ФОРМУЛАМ ТЕОРЕМЫ~K, ОН ПРОЛИВАЕТ ДОПОЛНИТЕЛЬНЫЙ
СВЕТ НА АЛГОРИТМ, ПОЭТОМУ МЫ КРАТКО ИЗЛОЖИМ ЕГО. ёНАЧАЛА РАССМОТРИМ
УДИВИТЕЛЬНОЕ СВОЙСТВО ЛИНЕЙНОГО ОПРОБОВАНИЯ, ВПЕРВЫЕ ОТМЕЧЕННОЕ
є.~яЕТЕРСОНОМ В 1957~Г.

\proclaim ЄЕОРЕМА P. ёРЕДНЕЕ ЧИСЛО ПРОБ ПРИ УДАЧНОМ ПОИСКЕ С
ПОМОЩЬЮ АЛГОРИТМА~L НЕ ЗАВИСИТ ОТ ПОРЯДКА, В КОТОРОМ КЛЮЧИ БЫЛИ
ВСТАВЛЕНЫ, А ЗАВИСИТ ЛИШЬ ОТ ТОГО, СКОЛЬКО КЛЮЧЕЙ ИМЕЮТ ТОТ ИЛИ ИНОЙ ХЕШ-АДРЕС.

шНЫМИ СЛОВАМИ, ЛЮБОЕ ПЕРЕУПОРЯДОЧЕНИЕ ХЕШ-ПОСЛЕДОВАТЕЛЬНОСТИ~$a_1$
$a_2$~\dots $a_N$ ДАЕТ ПОСЛЕДОВАТЕЛЬНОСТЬ С ТЕМ ЖЕ СРЕДНИМ СМЕЩЕНИЕМ
КЛЮЧЕЙ ОТ ИХ ХЕШ-АДРЕСОВ. (ъАК УКАЗАНО ВЫШЕ, МЫ ПРЕДПОЛАГАЕМ, ЧТО ВСЕ
КЛЮЧИ В ТАБЛИЦЕ ИМЕЮТ ОДИНАКОВУЮ ВАЖНОСТЬ. хСЛИ К НЕКОТОРЫМ ИЗ НИХ
ПРОИСХОДЯТ БОЛЕЕ ЧАСТЫЕ ОБРАЩЕНИЯ, МЕТОДОМ, АНАЛОГИЧНЫМ ИСПОЛЬЗОВАННОМУ
В ТЕОРЕМЕ~6.1S, МОЖНО ДОКАЗАТЬ, ЧТО РАСПОЛОЖЕНИЕ КЛЮЧЕЙ ОПТИМАЛЬНО,
ЕСЛИ ОНИ ВСТАВЛЯЛИСЬ В ПОРЯДКЕ УБЫВАНИЯ ЧАСТОТ.)

\proof фОСТАТОЧНО ПОКАЗАТЬ, ЧТО ОБЩЕЕ ЧИСЛО ПРОБ, НЕОБХОДИМЫХ ПРИ ВСТАВКЕ
КЛЮЧЕЙ ДЛЯ ХЕШ-ПОСЛЕДОВАТЕЛЬНОСТИ~$a_1$ $a_2$~\dots $a_N$, РАВНО ЧИСЛУ
ПРОБ ДЛЯ ПОСЛЕДОВАТЕЛЬНОСТИ~$a_1$~\dots $a_{i-1}$ $a_{i+1}$ $a_i$
$a_{i+2}$~\dots $a_N$, $1\le i<N$. юЧЕВИДНО, НУЖНО РАССМОТРЕТЬ ЛИШЬ СЛУЧАЙ,
 КОГДА $(i+1)\hbox{-Й}$~КЛЮЧ ВО ВТОРОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ПОПАЛ В ПОЗИЦИЮ,
ЗАНИМАЕМУЮ $i\hbox{-М}$~КЛЮЧОМ
%%631
В ПЕРВОЙ ПОСЛЕДОВАТЕЛЬНОСТИ. эО ЕСЛИ $i\hbox{-Й}$
И~$(i+1)\hbox{-Й}$~ЭЛЕМЕНТЫ ПРОСТО ПОМЕНЯЛИСЬ МЕСТАМИ, ТО ЧИСЛО ПРОБ ДЛЯ
$(i+1)\hbox{-ГО}$~КЛЮЧА УМЕНЬШИЛОСЬ НА СТОЛЬКО, НА СКОЛЬКО УВЕЛИЧИЛОСЬ
ЧИСЛО ПРОБ ДЛЯ $i\hbox{-ГО}$.
\proofend

ЄЕОРЕМА~P ГЛАСИТ, ЧТО СРЕДНЮЮ ДЛИНУ ПОИСКА ДЛЯ
ХЕШ-ПОСЛЕДОВАТЕЛЬНОСТИ~$a_1$ $a_2$~\dots $a_N$ МОЖНО НАЙТИ, ЗНАЯ
ЧИСЛА~$b_0$ $b_1$~\dots $b_{M-1}$, ГДЕ $b_j$~ЕСТЬ КОЛИЧЕСТВО
ЭЛЕМЕНТОВ~$a_i$, РАВНЫХ~$j$. яО ЭТОЙ ПОСЛЕДОВАТЕЛЬНОСТИ МОЖНО ОПРЕДЕЛИТЬ
"ПОСЛЕДОВАТЕЛЬНОСТЬ ПЕРЕНОСОВ"~$c_0$ $c_1$~\dots $c_{M-1}$, ГДЕ $c_j$---ЧИСЛО
КЛЮЧЕЙ, ПРИ ВСТАВКЕ КОТОРЫХ ОПРОБОВАЛИСЬ ОБЕ ПОЗИЦИИ~$j$ И~$j-1$. ¤ТА
ПОСЛЕДОВАТЕЛЬНОСТЬ ОПРЕДЕЛЯЕТСЯ ПРАВИЛОМ
$$
c_j=\cases{
0, & ЕСЛИ $b_j=c_{(j+1)\bmod M}=0$;\cr
b_j+c_{(j+1)\bmod M}-1 & В ПРОТИВНОМ СЛУЧАЕ.\cr
}
\eqno(44)
$$
яУСТЬ, НАПРИМЕР, $M=10$, $N=8$
И~$b_0\ldots{}b_9=0\ 3\ 2\ 0\ 1\ 0\ 0\ 0\ 2$;
ТОГДА~$c_0\ldots{}c_9=2\ 3\ 1\ 0\ 0\ 0\ 0\ 1\ 2\ 3$, ТАК КАК ОДИН КЛЮЧ
НУЖНО ПЕРЕНЕСТИ ИЗ ПОЗИЦИИ~2 В ПОЗИЦИЮ~1, ТРИ---ИЗ ПОЗИЦИИ~1 В ПОЗИЦИЮ~0,
ДВА---ИЗ ПОЗИЦИИ~0 В ПОЗИЦИЮ~9 И~Т.~Д. шМЕЕМ~$b_0+b_1+\cdots+b_{M-1}=N$, А
СРЕДНЕЕ ЧИСЛО ПРОБ, ТРЕБУЮЩИХСЯ ДЛЯ ВЫБОРКИ ЭТИХ $N$~КЛЮЧЕЙ, РАВНО
$$
1+(c_0+c_1+\cdots+c_{M-1})/N.
\eqno (45)
$$
ъАЖЕТСЯ, ЧТО ПРАВИЛО~(44) ЦИКЛИЧЕСКИ ОПРЕДЕЛЯЕТ ЧИСЛА~$c$ ЧЕРЕЗ САМИХ СЕБЯ,
 НО В ДЕЙСТВИТЕЛЬНОСТИ ПРИ ЛЮБОМ~$N<M$ СИСТЕМА ИМЕЕТ ЕДИНСТВЕННОЕ РЕШЕНИЕ (СМ.~УПР.~32).

у.~°АЙ И~т.~ёПРУТ ИСПОЛЬЗОВАЛИ ЭТУ ИДЕЮ ДЛЯ ОПРЕДЕЛЕНИЯ ВЕРОЯТНОСТЕЙ~$q_k$
(ВЕРОЯТНОСТИ ТОГО, ЧТО~$c_j=k$) ЧЕРЕЗ ВЕРОЯТНОСТИ~$p_k$ (ВЕРОЯТНОСТИ ТОГО,
ЧТО~$b_j=k$). (¤ТИ ВЕРОЯТНОСТИ НЕ ЗАВИСЯТ ОТ~$j$.) ЄАК,
$$
\eqalign{
q_0&=p_0q_0+p_1q_0+p_0q_1,\cr
q_1&=p_2q_0+p_1q_1+p_0q_2,\cr
q_2&=p_3q_0+p_2q_1+p_1q_2+p_0q_3\cr
}
\eqno(46)
$$
И~Т.~Д., ПОСКОЛЬКУ, НАПРИМЕР, ВЕРОЯТНОСТЬ ТОГО, ЧТО~$c_j=2$,
ЕСТЬ ВЕРОЯТНОСТЬ ТОГО, ЧТО~$b_j+c_{(j+1)\bmod M}=3$.
яУСТЬ~$B(z)=\sum p_kz_k$ И~$C(z)=\sum q_kz^k$---ПРОИЗВОДЯЩИЕ ФУНКЦИИ ДЛЯ
РАССМАТРИВАЕМЫХ ВЕРОЯТНОСТНЫХ РАСПРЕДЕЛЕНИЙ; УРАВНЕНИЯ~(46) ЭКВИВАЛЕНТНЫ СООТНОШЕНИЮ
$$
B(z)C(z)=p_0q_0+(q_0-p_0q_0)z+q_1z^2+\cdots=p_0q_0(1-z)+zC(z).
$$
ЄАК КАК~$B(1)=1$, МОЖНО НАПИСАТЬ~$B(z)=1+(z-1)D(z)$. юТСЮДА ВЫТЕКАЕТ, ЧТО
$$
C(z)={p_0q_0\over 1-D(z)}={1-D(1)\over 1-D(z)},
\eqno(47)
$$
%%632
ПОСКОЛЬКУ~$C(1)=1$. ёЛЕДОВАТЕЛЬНО, СРЕДНЕЕ ЧИСЛО ПРОБ, НЕОБХОДИМЫХ ДЛЯ
ВЫБОРКИ, В СООТВЕТСТВИИ С~(45) СОСТАВИТ
$$
1+{M\over N}C'(1)=1+{M\over N}{D'(1)\over 1-D(1)}
=1+{M\over 2N}{B''(1)\over 1-B'(1)}.
\eqno(48)
$$
т СИЛУ ПРЕДПОЛОЖЕНИЯ О РАВНОВЕРОЯТНОСТИ ВСЕХ ХЕШ-ПОСЛЕДОВАТЕЛЬНОСТЕЙ ИМЕЕМ
$$
\eqalignno{
p_k &= \hbox{(тЕРОЯТНОСТЬ ТОГО, ЧТО ДЛЯ ФИКСИРОВАННОГО~$j$ В ТОЧНОСТИ
$k$~ЧИСЕЛ~$a_i$ РАВНО~$j$)}=\cr
&=\perm{N}{k}\left({1\over M}^k\right)\left(1-{1\over M}\right)^{N-k}; &(49)\cr
}
$$
ПОЭТОМУ
$$
B(z)=\left(1+{z-1\over M}\right)^N, \quad
B'(1)={N\over M},\quad
B''(1)={N(N-1)\over M^2}
\eqno (50)
$$
И СРЕДНЕЕ ЧИСЛО ПРОБ, СОГЛАСНО~(48), СОСТАВИТ
$$
C_N={1\over2}\left(1+{M-1\over M-N}\right).
\eqno(51)
$$
яОНЯТНО ЛИ ЧИТАТЕЛЮ, ПОЧЕМУ ЭТОТ ОТВЕТ ОТЛИЧАЕТСЯ ОТ РЕЗУЛЬТАТА
ТЕОРЕМЫ~K? (ёР.~С~УПР.~33.)

\section *шССЛЕДОВАНИЕ ОПТИМАЛЬНОСТИ. ьЫ ИЗУЧИЛИ НЕСКОЛЬКО
ПОСЛЕДОВАТЕЛЬНОСТЕЙ ПРОБ ДЛЯ ОТКРЫТОЙ АДРЕСАЦИИ, И ЕСТЕСТВЕННО СПРОСИТЬ,
КАКАЯ ИЗ НИХ ЯВЛЯЕТСЯ "НАИЛУЧШЕЙ ИЗ ВОЗМОЖНЫХ" В НЕКОТОРОМ РАЗУМНОМ СМЫСЛЕ.
 шНТЕРЕСНУЮ ПОСТАНОВКУ ЭТОЙ ЗАДАЧИ ПРЕДЛОЖИЛ фЖ.~єЛЬМАН [{\sl JACM,\/}
{\bf 19} (1972), 569--575]:
ВМЕСТО ВЫЧИСЛЕНИЯ "ХЕШ-АДРЕСА"~$h(K)$ МОЖНО ОТОБРАЗИТЬ КАЖДЫЙ КЛЮЧ~$K$ В
ЦЕЛУЮ ПЕРЕСТАНОВКУ МНОЖЕСТВА~$\set{0, 1,~\ldots, M-1}$, ПРЕДСТАВЛЯЮЩУЮ
СОБОЙ ПОСЛЕДОВАТЕЛЬНОСТЬ ПРОБ ПРИ ИСПОЛЬЗОВАНИИ~$K$. ъАЖДОЙ ИЗ
$M!$~ПЕРЕСТАНОВОК ПРИПИСЫВАЕТСЯ ВЕРОЯТНОСТЬ, И ПРЕДПОЛАГАЕТСЯ, ЧТО
ОБОБЩЕННАЯ ХЕШ-ФУНКЦИЯ ВЫБИРАЕТ КАЖДУЮ ПЕРЕСТАНОВКУ С ЭТОЙ ВЕРОЯТНОСТЬЮ.
тОПРОС СТАВИТСЯ ТАК: "ъАК НУЖНО ПРИПИСАТЬ ПЕРЕСТАНОВКАМ ВЕРОЯТНОСТИ,
ЧТОБЫ ПОЛУЧИТЬ НАИЛУЧШИЕ ХАРАКТЕРИСТИКИ, Т.~Е.~ЧТОБЫ СООТВЕТСТВУЮЩЕЕ
СРЕДНЕЕ ЧИСЛО ПРОБ~$C_N$ ИЛИ~$C'_N$ БЫЛО МИНИМАЛЬНЫМ?"

хСЛИ, НАПРИМЕР, ПРИПИСАТЬ КАЖДОЙ ПЕРЕСТАНОВКЕ ВЕРОЯТНОСТЬ~$1/M!$, ТО,
КАК ЛЕГКО ВИДЕТЬ, ПОЛУЧИТСЯ В ТОЧНОСТИ ПОВЕДЕНИЕ  \emph{РАВНОМЕРНОГО
ХЕШИРОВАНИЯ} (СМ.~(32), (34)). юДНАКО єЛЬМАН
ПОСТРОИЛ ПРИМЕР С~$M=4$ И~$N=2$, В КОТОРОМ~$C'_N$ МЕНЬШЕ~${5\over3}$
(ЭТО ЗНАЧЕНИЕ ПОЛУЧАЕТСЯ ПРИ РАВНОМЕРНОМ ХЕШИРОВАНИИ). юН ПРИПИСАЛ
НЕНУЛЕВЫЕ ВЕРОЯТНОСТИ ЛИШЬ СЛЕДУЮЩИМ ШЕСТИ ПЕРЕСТАНОВКАМ:
%%633
$$
\matrix{
\hbox{яЕРЕСТАНОВКА} & \hbox{тЕРОЯТНОСТЬ} & \hbox{яЕРЕСТАНОВКА} & \hbox{тЕРОЯТНОСТЬ}\cr
0\ 1\ 2\ 3 &   (1+2\epsilon)/6  &1\ 0\ 3\ 2 & (1+2\epsilon)/6\cr
2\ 0\ 1\ 3 &   (1- \epsilon)/6  &2\ 1\ 0\ 3 & (1- \epsilon)/6\cr
3\ 0\ 1\ 2 &   (1- \epsilon)/6  &3\ 1\ 0\ 2 & (1- \epsilon)/6\cr
}
\eqno(52)
$$
уРУБО ГОВОРЯ, НА ПЕРВОМ ШАГЕ МЫ ПРЕДПОЧИТАЕМ~2 И~3, А НА ВТОРОМ---0 И~1.
ёРЕДНЕЕ ЧИСЛО ПРОБ, НЕОБХОДИМЫХ ДЛЯ ВСТАВКИ
ТРЕТЬЕГО ЭЛЕМЕНТА, ОКАЗЫВАЕТСЯ
РАВНЫМ~${5\over3}-{1\over9}\varepsilon+O(\varepsilon^2)$, ЧТО
МЕНЬШЕ~${5\over3}$ ПРИ МАЛОМ ПОЛОЖИТЕЛЬНОМ~$\varepsilon$.

юДНАКО ПРИ ТАКОМ РАСПРЕДЕЛЕНИИ
ВЕРОЯТНОСТЕЙ~$C'_1={23\over18}+O(\varepsilon)$,
А ЭТО БОЛЬШЕ~${5\over4}$ (ЗНАЧЕНИЕ~$C'_1$ ДЛЯ РАВНОМЕРНОГО ХЕШИРОВАНИЯ).
єЛЬМАН ДОКАЗАЛ, ЧТО ПРИ ЛЮБОМ СПОСОБЕ ПРИПИСЫВАНИЯ ВЕРОЯТНОСТЕЙ, ТАКОМ,
ЧТО~$C'_N<(M+1)/(M+1-N)$ ПРИ НЕКОТОРОМ~$N$, ВСЕГДА СУЩЕСТВУЕТ~$n<N$, ТАКОЕ,
 ЧТО~$C'_n > (M+1)/(M+1-n)$;
НЕЛЬЗЯ ВСЕ ВРЕМЯ ПОБЕЖДАТЬ РАВНОМЕРНОЕ ХЕШИРОВАНИЕ.

т ДЕЙСТВИТЕЛЬНОСТИ В КАЧЕСТВЕ МЕРЫ ЛУЧШЕ ПОДХОДИТ НЕ~$C'_N$, А ЧИСЛО ПРОБ
ПРИ \emph{УДАЧНОМ} ПОИСКЕ~$C_N$. яЕРЕСТАНОВКИ~(52) НЕ ДАЮТ УЛУЧШЕНИЯ~$C_N$
НИ ПРИ КАКОМ~$N$, И КАЖЕТСЯ ВЕСЬМА РАЗУМНЫМ ПРЕДПОЛОЖИТЬ, ЧТО НИКАКОЕ
ПРИПИСЫВАНИЕ ПЕРЕСТАНОВКАМ ВЕРОЯТНОСТЕЙ НЕ МОЖЕТ СДЕЛАТЬ~$C_N$ МЕНЬШЕ
"РАВНОМЕРНОГО" ЗНАЧЕНИЯ~$((M+1)/N) (H_{M+1}-H_{M+1-N})$.

ъАК ОКАЗЫВАЕТСЯ, ЭТО УТВЕРЖДЕНИЕ ОЧЕНЬ ТРУДНО ДОКАЗАТЬ ГЛАВНЫМ ОБРАЗОМ
ПОТОМУ, ЧТО ПОЛУЧИТЬ ЭФФЕКТ РАВНОМЕРНОГО ХЕШИРОВАНИЯ МОЖНО МНОГИМИ
СПОСОБАМИ; МЫ НЕ ОБЯЗАНЫ ПРИПИСЫВАТЬ КАЖДОЙ ПЕРЕСТАНОВКЕ ВЕРОЯТНОСТЬ~$1/M!$.
эАПРИМЕР, СЛЕДУЮЩЕЕ РАСПРЕДЕЛЕНИЕ ПРИ~$M=4$ ЭКВИВАЛЕНТНО РАВНОМЕРНОМУ ХЕШИРОВАНИЮ:
$$
\matrix{
\hbox{яЕРЕСТАНОВКА} & \hbox{тЕРОЯТНОСТЬ} & \hbox{яЕРЕСТАНОВКА} & \hbox{тЕРОЯТНОСТЬ}\cr
0\ 1\ 2\ 3 &   1/6  &0\ 2\ 1\ 3 & 1/12\cr
1\ 2\ 3\ 0 &   1/6  &1\ 3\ 2\ 0 & 1/12\cr
2\ 3\ 0\ 1 &   1/6  &2\ 0\ 3\ 1 & 1/12\cr
}
\eqno(53)
$$
(ОСТАЛЬНЫМ 16~ПЕРЕСТАНОВКАМ ПРИПИСЫВАЕТСЯ НУЛЕВАЯ ВЕРОЯТНОСТЬ).

ёЛЕДУЮЩАЯ ТЕОРЕМА ХАРАКТЕРИЗУЕТ \emph{ВСЕ} РАСПРЕДЕЛЕНИЯ ВЕРОЯТНОСТЕЙ,
КОТОРЫЕ ДАЮТ ПОВЕДЕНИЕ РАВНОМЕРНОГО ХЕШИРОВАНИЯ:

\proclaim ЄЕОРЕМА~U. яРИПИСЫВАНИЕ ПЕРЕСТАНОВКАМ ВЕРОЯТНОСТЕЙ СДЕЛАЕТ ВСЕ
$\perm{M}{N}$~КОНФИГУРАЦИЙ ЗАНЯТЫХ И СВОБОДНЫХ ЯЧЕЕК ПОСЛЕ N~ВСТАВОК
РАВНОВЕРОЯТНЫМИ ДЛЯ~$0<N<M$ ТОГДА И ТОЛЬКО ТОГДА, КОГДА
%%634
СУММА ВЕРОЯТНОСТЕЙ, ПРИПИСАННЫХ ВСЕМ ПЕРЕСТАНОВКАМ, ПЕРВЫЕ $N$~ЭЛЕМЕНТОВ
КОТОРЫХ ПРИНАДЛЕЖАТ ДАННОМУ $N\hbox{-ЭЛЕМЕНТНОМУ}$ МНОЖЕСТВУ,
РАВНА~$1\big/\perm{M}{N}$ ДЛЯ ВСЕХ~$N$ И ВСЕХ $N\hbox{-ЭЛЕМЕНТНЫХ}$ МНОЖЕСТВ.

эАПРИМЕР, СУММА ВЕРОЯТНОСТЕЙ, ПРИПИСАННЫХ КАЖДОЙ ИЗ
$3!(M-3)!$~ПЕРЕСТАНОВОК, НАЧИНАЮЩИХСЯ С ЧИСЕЛ~$\set{0, 1,2}$, СТОЯЩИХ В
НЕКОТОРОМ ПОРЯДКЕ, ДОЛЖНА СОСТАВЛЯТЬ~$1\big/\perm{M}{3}=3!(M-3)!/M!$.
чАМЕТЬТЕ, ЧТО (53)~УДОВЛЕТВОРЯЕТ УСЛОВИЮ ТЕОРЕМЫ.

\proof яУСТЬ~$A\le \set{0, 1,~\ldots, M-1}$, И ПУСТЬ~$\Pi(A)$ ЕСТЬ
МНОЖЕСТВО ВСЕХ ПЕРЕСТАНОВОК, ПЕРВЫЕ $\Abs{A}$~ЭЛЕМЕНТОВ КОТОРЫХ
ПРИНАДЛЕЖАТ~$A$. ёУММУ ВЕРОЯТНОСТЕЙ, ПРИПИСАННЫХ ЭТИМ  ПЕРЕСТАНОВКАМ,
ОБОЗНАЧИМ ЧЕРЕЗ~$S(A)$. ёИМВОЛОМ~$P_k(A)$ ОБОЗНАЧИМ ВЕРОЯТНОСТЬ ТОГО,
ЧТО ПЕРВЫЕ $\Abs{A}$~КЛЮЧЕЙ, ВСТАВЛЕННЫХ ПРОЦЕДУРОЙ ОТКРЫТОЙ АДРЕСАЦИИ,
ЗАЙМУТ ЯЧЕЙКИ, ОПРЕДЕЛЕННЫЕ МНОЖЕСТВОМ~$A$, И ЧТО ПОСЛЕДНЯЯ ВСТАВКА
ПОТРЕБУЕТ РОВНО $k$~ПРОБ;
ПОЛОЖИМ~$P(A)=P_1(A)+P_2(A)+\cdots$. фОКАЗАТЕЛЬСТВО ПРОВОДИТСЯ ИНДУКЦИЕЙ
ПО~$N\ge 1$; ПРЕДПОЛАГАЕТСЯ, ЧТО
$$
P(A)=S(A)=1\bigg/\perm{M}{n}
$$
ДЛЯ ВСЕХ МНОЖЕСТВ~$A$ С~$\Abs{A}=n<N$. яУСТЬ $B$ ЕСТЬ
$N\hbox{-ЭЛЕМЕНТНОЕ}$ МНОЖЕСТВО. ЄОГДА
$$
P_k(B)=\sum_{\scriptstyle A\subseteq B \atop \scriptstyle \Abs{A}=k }
\sum_{\pi\in\Pi(A)}\Pr(\pi)P(B\setminus\set{\pi_k}),
$$
ГДЕ $\Pr(\pi)$~ЕСТЬ ВЕРОЯТНОСТЬ, ПРИПИСАННАЯ ПЕРЕСТАНОВКЕ~$\pi$, a
 $\pi_k$---ЕЕ $k\hbox{-Й}$~ЭЛЕМЕНТ. т СИЛУ ИНДУКТИВНОГО ПРЕДПОЛОЖЕНИЯ
$$
P_k(B)=\sum_{\scriptstyle A\subseteq B \atop \scriptstyle\Abs{A}=k}{1\over\perm{M}{N-1}}
\sum_{\pi\in\Pi(A)}\Pr(\pi),
$$
ЧТО РАВНЯЕТСЯ
$$
\perm{N}{k}\bigg/\perm{M}{N-1}\perm{M}{k},
\rem{ЕСЛИ $k<N$;}
$$
СЛЕДОВАТЕЛЬНО,
$$
P(B)={1\over\perm{M}{N-1}}
\left(S(B)+\sum_{1\le k<N}{\perm{N}{k}\over\perm{M}{k}}\right),
$$
%%635
А ЭТО РАВНЯЕТСЯ~$1\big/\perm{M}{N}$ ТОГДА И ТОЛЬКО ТОГДА, КОГДА
$S(B)$~ИМЕЕТ ТРЕБУЕМОЕ ЗНАЧЕНИЕ.
\proofend

\section тНЕШНИЙ ПОИСК. ьЕТОДЫ ХЕШИРОВАНИЯ ВПОЛНЕ ПОДХОДЯТ ДЛЯ ВНЕШНЕГО
ПОИСКА НА ЗАПОМИНАЮЩИХ УСТРОЙСТВАХ С ПРЯМЫМ ДОСТУПОМ ТИПА ДИСКОВ ИЛИ
БАРАБАНОВ. фЛЯ ТАКИХ ПРИЛОЖЕНИЙ, КАК И В П.~6.2.4, МЫ ХОТИМ МИНИМИЗИРОВАТЬ
ЧИСЛО ОБРАЩЕНИЙ К ФАЙЛУ, И ЭТО ДВОЯКО ВЛИЯЕТ НА ВЫБОР АЛГОРИТМОВ:

\enumerate
\li ЁАЗУМНО ПОТРАТИТЬ БОЛЬШЕ ВРЕМЕНИ НА ВЫЧИСЛЕНИЕ ХЕШ-ФУНКЦИИ, ПОТОМУ
ЧТО РАСПЛАТА ЗА ПЛОХОЕ ХЕШИРОВАНИЕ МНОГО БОЛЬШЕ СТОИМОСТИ ДОПОЛНИТЕЛЬНОГО
ВРЕМЕНИ, НУЖНОГО ДЛЯ АККУРАТНОЙ РАБОТЫ.

\li чАПИСИ ОБЫЧНО СГРУППИРОВАНЫ В БЛОКИ, ЧТОБЫ ЗА ОДИН РАЗ ИЗВЛЕКАТЬ ИЗ
ВНЕШНЕЙ ПАМЯТИ НЕСКОЛЬКО ЗАПИСЕЙ.
\enumend

юБЫЧНО ФАЙЛ ДЕЛИТСЯ НА $M$~БЛОКОВ ПО $b$~ЗАПИСЕЙ В КАЖДОМ. ъОЛЛИЗИИ НЕ
ВЫЗЫВАЮТ ЗАТРУДНЕНИЙ, ПОКА НЕ ПОЯВИТСЯ БОЛЕЕ $b$~КЛЮЧЕЙ С ДАННЫМ
ХЕШ-АДРЕСОМ. яО-ВИДИМОМУ, НАИЛУЧШИМИ БУДУТ СЛЕДУЮЩИЕ ТРИ ПОДХОДА К
РАЗРЕШЕНИЮ КОЛЛИЗИЙ.

A) {\sl ЁАЗДЕЛЬНЫЕ ЦЕПОЧКИ.\/} хСЛИ В ОДИН И ТОТ ЖЕ БЛОК ПОПАДАЕТ БОЛЬШЕ
$b$~ЗАПИСЕЙ, В КОНЦЕ ПЕРВОГО БЛОКА МОЖНО ВСТАВИТЬ ССЫЛКУ НА
"ПЕРЕПОЛНЯЮЩУЮ" ЗАПИСЬ. яЕРЕПОЛНЯЮЩИЕ ЗАПИСИ ХРАНЯТСЯ В СПЕЦИАЛЬНОЙ
ОБЛАСТИ. юБЫЧНО НЕТ СМЫСЛА ИМЕТЬ БЛОКИ В ОБЛАСТИ ПЕРЕПОЛНЕНИЯ, ТАК КАК
ВОЗНИКАЕТ СРАВНИТЕЛЬНО МАЛО ПЕРЕПОЛНЕНИИ; ТАКИМ ОБРАЗОМ, ДОБАВЛЯЮЩИЕСЯ
ЗАПИСИ ОБЫЧНО СВЯЗЫВАЮТСЯ ДРУГ С ДРУГОМ, И НА $(b+k)\hbox{-Ю}$~ЗАПИСЬ
СПИСКА ТРАТИТСЯ $1+k$~ОБРАЩЕНИЙ К ВНЕШНЕМУ УСТРОЙСТВУ. ўАСТО ПОЛЕЗНО
ОСТАВИТЬ НЕКОТОРОЕ ПРОСТРАНСТВО НА КАЖДОМ "ЦИЛИНДРЕ" ДИСКОВОГО ФАЙЛА,
ЧТОБЫ БОЛЬШИНСТВО ОБРАЩЕНИЙ ПРОИСХОДИЛО К ОДНОМУ И ТОМУ ЖЕ ЦИЛИНДРУ.

їОТЯ ТАКОЙ МЕТОД ОБРАБОТКИ ПЕРЕПОЛНЕНИИ КАЖЕТСЯ НЕЭФФЕКТИВНЫМ, ЧИСЛО
ПЕРЕПОЛНЕНИИ СТАТИСТИЧЕСКИ ДОСТАТОЧНО МАЛО, И СРЕДНЕЕ ВРЕМЯ ПОИСКА
ОКАЗЫВАЕТСЯ ОЧЕНЬ ХОРОШИМ. т ТАБЛ.~2 И~3 ПРИВОДИТСЯ СРЕДНЕЕ ЧИСЛО
ОБРАЩЕНИЙ КАК ФУНКЦИЯ ОТ КОЭФФИЦИЕНТА  ЗАПОЛНЕНИЯ
$$
\alpha=N/Mb,
\eqno(54)
$$
ГДЕ $\alpha$~ФИКСИРОВАНО И $ь, N\to\infty$. ъАК НИ СТРАННО, НО
ПРИ~$\alpha=1$ АСИМПТОТИЧЕСКОЕ ЧИСЛО ОБРАЩЕНИЙ В СЛУЧАЕ НЕУДАЧНОГО ПОИСКА
РАСТЕТ С РОСТОМ~$b$.

B) {\sl ёРАСТАЮЩИЕСЯ ЦЕПОЧКИ.\/} тМЕСТО ОТВЕДЕНИЯ ОТДЕЛЬНОЙ
ОБЛАСТИ ПЕРЕПОЛНЕНИЯ, МОЖНО ПРИСПОСОБИТЬ АЛГОРИТМ~C ДЛЯ РАБОТЫ С ВНЕШНИМИ
ФАЙЛАМИ. хЩЕ НЕ ЗАПОЛНЕННЫЕ БЛОКИ МОЖНО СВЯЗАТЬ В ДВУХСВЯЗЕВЫЙ СПИСОК
СВОБОДНОГО ПРОСТРАНСТВА. ёОГЛАСНО
%%636
\htable{ЄАБЛИЦА 2}%
{ёРЕДНЕЕ ЧИСЛО ОБРАЩЕНИЙ ПРИ НЕУДАЧНОМ ПОИСКЕ С ПОМОЩЬЮ РАЗДЕЛЬНЫХ ЦЕПОЧЕК}%
{\hfill#\bskip&&\hfill\bskip$#$\bskip\hfill\cr
\noalign{\hrule}
 &\multispan{10}\hfill\hbox{ъОЭФФИЦИЕНТ ЗАПОЛНЕНИЯ, $\alpha$}\hfill\cr
ЁАЗМЕР БЛОКА~$b$
&10\%&20\%&30\%&40\%&50\%&60\%&70\%&80\%&90\%&95\%\cr
\noalign{\hrule}
  1&1.0048&1.0187&1.0408&1.0703&1.1065&1.1488&1.197&1.249&1.307&1.3\cr
 2&1.0012&1.0088&1.0269&1.0581&1.1036&1.1638&1.238&1.327&1.428&1.5\cr
 3&1.0003&1.0038&1.0162&1.0433&1.0898&1.1588&1.252&1.369&1.509&1.6\cr
 4&1.0001&1.0016&1.0095&1.0314&1.0751&1.1476&1.253&1.394&1.571&1.7\cr
 5&1.0000&1.0007&1.0056&1.0225&1.0619&1.1346&1.249&1.410&1.620&1.7\cr
10&1.0000&1.0000&1.0004&1.0041&1.0222&1.0773&1.201&1.426&1.773&2.0\cr
20&1.0000&1.0000&1.0000&1.0001&1.0028&1.0234&1.113&1.367&1.898&2.3\cr
50&1.0000&1.0000&1.0000&1.0000&1.0000&1.0007&1.018&1.182&1.920&2.7\cr
\noalign{\hrule}}%
ЭТОЙ СХЕМЕ, КАЖДЫЙ БЛОК СОДЕРЖИТ СЧЕТЧИК ЧИСЛА СВОБОДНЫХ ПОЗИЦИЙ; БЛОК
УДАЛЯЕТСЯ ИЗ СПИСКА, ЛИШЬ ЕСЛИ ЭТОТ СЧЕТЧИК ОБРАЩАЕТСЯ В~0. ьОЖНО
ИСПОЛЬЗОВАТЬ "БЛУЖДАЮЩИЙ УКАЗАТЕЛЬ" ДЛЯ РАСПРЕДЕЛЕНИЯ ПЕРЕПОЛНЕНИИ
(СР.~С УПР.~2.5-6), ЧТОБЫ В РАЗЛИЧНЫХ СПИСКАХ ПО ВОЗМОЖНОСТИ ФИГУРИРОВАЛИ
РАЗЛИЧНЫЕ БЛОКИ ПЕРЕПОЛНЕНИЯ. тЕРОЯТНО, ПОЛЕЗНО ИМЕТЬ ОТДЕЛЬНЫЕ СПИСКИ
СВОБОДНОГО ПРОСТРАНСТВА ДЛЯ БЛОКОВ НА КАЖДОМ ЦИЛИНДРЕ ДИСКОВОГО ФАЙЛА.

¤ТОТ МЕТОД ЕЩЕ НЕ ПРОАНАЛИЗИРОВАН, НО ОН ДОЛЖЕН ОКАЗАТЬСЯ ВЕСЬМА ПОЛЕЗНЫМ.

\htable{ЄАБЛИЦА 3}%
{ёРЕДНЕЕ ЧИСЛО ОБРАЩЕНИИ ПРИ УДАЧНОМ ПОИСКЕ С ПОМОЩЬЮ РАЗДЕЛЬНЫХ ЦЕПОЧЕК}%
{\hfill#\bskip&&\hfill\bskip$#$\bskip\hfill\cr
\noalign{\hrule}
 &\multispan{10}\hfill\hbox{ъОЭФФИЦИЕНТ ЗАПОЛНЕНИЯ, $\alpha$}\hfill\cr
ЁАЗМЕР БЛОКА~$b$
&10\%&20\%&30\%&40\%&50\%&60\%&70\%&80\%&90\%&95\%\cr
\noalign{\hrule}
 1&1.0500&1.1000&1.1500&1.2000&1.2500&1.3000&1.350&1.400&1.450&1.5\cr
 2&1.0063&1.0242&1.0520&1.0883&1.1321&1.1823&1.238&1.299&1.364&1.4\cr
 3&1.0010&1.0071&1.0216&1.0458&1.0806&1.1259&1.181&1.246&1.319&1.4\cr
 4&1.0002&1.0023&1.0097&1.0257&1.0527&1.0922&1.145&1.211&1.290&1.3\cr
 5&1.0000&1.0008&1.0046&1.0151&1.0358&1.0699&1.119&1.186&1.286&1.3\cr
10&1.0000&1.0000&1.0002&1.0015&1.0070&1.0226&1.056&1.115&1.206&1.3\cr
20&1.0000&1.0000&1.0000&1.0000&1.0005&1.0038&1.018&1.059&1.150&1.2\cr
50&1.0000&1.0000&1.0000&1.0000&1.0000&1.0000&1.001&1.015&1.083&1.2\cr
\noalign{\hrule}}

C)~{\sl юТКРЫТАЯ АДРЕСАЦИЯ.\/} ьОЖНО ОБОЙТИСЬ И БЕЗ ССЫЛОК, ИСПОЛЬЗУЯ
"ОТКРЫТЫЙ" МЕТОД. фЛЯ ВНЕШНЕГО ПОИСКА ЛИНЕЙНОЕ ОПРОБОВАНИЕ, ВЕРОЯТНО,
ЛУЧШЕ СЛУЧАЙНОГО, ИБО ВЕЛИЧИНУ~$c$ МОЖНО ВЫБРАТЬ ТАК, ЧТОБЫ МИНИМИЗИРОВАТЬ
СКРЫТЫЕ ЗАДЕРЖКИ МЕЖДУ ПОСЛЕДОВАТЕЛЬНЫМИ ОБРАЩЕНИЯМИ. яОСТРОЕННАЯ ВЫШЕ
ПРИБЛИЖЕННАЯ ТЕОРЕТИЧЕСКАЯ МОДЕЛЬ ЛИНЕЙНОГО ОПРОБОВАНИЯ МОЖЕТ БЫТЬ
ОБОБЩЕНА ДЛЯ УЧЕТА ВЛИЯНИЯ БЛОКОВ; ОНА ПОКАЗЫВАЕТ, ЧТО
%%637
\htable{ЄАБЛИЦА 4}%
{ёРЕДНЕЕ ЧИСЛО ОБРАЩЕНИЙ ПРИ УДАЧНОМ ПОИСКЕ С ПОМОЩЬЮ ЛИНЕЙНОГО ОПРОБОВАНИЯ}%
{\hfill#\bskip&&\hfill\bskip$#$\bskip\hfill\cr
\noalign{\hrule}
 &\multispan{10}\hfill\hbox{ъОЭФФИЦИЕНТ ЗАПОЛНЕНИЯ, $\alpha$}\hfill\cr
ЁАЗМЕР БЛОКА~$b$
&10\%&20\%&30\%&40\%&50\%&60\%&70\%&80\%&90\%&95\%\cr
\noalign{\hrule}
 1&1.0556&1.1250&1.2143&1.3333&1.5000&1.7500&2.167&3.000&5.500&10.5\cr
 2&1.0062&1.0242&1.0553&1.1033&1.1767&1.2930&1.494&1.903&3.147&5.6\cr
 3&1.0009&1.0066&1.0201&1.0450&1.0872&1.1584&1.286&1.554&2.378&4.0\cr
 4&1.0001&1.0021&1.0085&1.0227&1.0497&1.0984&1.190&1.386&2.000&3.2\cr
 5&1.0000&1.0007&1.0039&1.0124&1.0307&1.0661&1.136&1.289&1.777&2.7\cr
10&1.0000&1.0000&1.0001&1.0011&1.0047&1.0154&1.042&1.110&1.345&1.8\cr
20&1.0000&1.0000&1.0000&1.0000&1.0003&1.0020&1.010&1.036&1.144&1.4\cr
50&1.0000&1.0000&1.0000&1.0000&1.0000&1.0000&1.001&1.005&1.040&1.1\cr
\noalign{\hrule}}%
ЛИНЕЙНОЕ ОПРОБОВАНИЕ ДЕЙСТВИТЕЛЬНО УДОВЛЕТВОРИТЕЛЬНО, ПОКА ТАБЛИЦА НЕ
СЛИШКОМ ПОЛНА. шЗ ТАБЛ.~4 ВИДНО, ЧТО ПРИ~$\alpha=90\%$ И~$b=50$ СРЕДНЕЕ
ЧИСЛО ОБРАЩЕНИЙ ДЛЯ УДАЧНОГО ПОИСКА СОСТАВЛЯЕТ ЛИШЬ~$1.04$. ¤ТО ДАЖЕ
\emph{ЛУЧШЕ,} ЧЕМ $1.08$~ОБРАЩЕНИЯ, КОТОРОЕ ТРЕБУЕТСЯ В МЕТОДЕ ЦЕПОЧЕК~(A)
С ТЕМ ЖЕ РАЗМЕРОМ БЛОКА!

рНАЛИЗ МЕТОДОВ~(A) И~(C) ВЕСЬМА ИНТЕРЕСЕН И С МАТЕМАТИЧЕСКОЙ ТОЧКИ
ЗРЕНИЯ; МЫ ПРИВЕДЕМ ЗДЕСЬ ЛИШЬ РЕЗУЛЬТАТЫ, ПОСКОЛЬКУ ДЕТАЛЬНОМУ
ИССЛЕДОВАНИЮ ПОСВЯЩЕНЫ УПР.~49 И~55. ЇОРМУЛЫ СОДЕРЖАТ ДВЕ ФУНКЦИИ, ТЕСНО
СВЯЗАННЫЕ С $Q\hbox{-ФУНКЦИЯМИ}$ ТЕОРЕМЫ~$K$:
$$
R(\alpha, n)={n\over n+1}+{n^2\alpha\over (n+1)(n+2)}
+{n^3\alpha^2\over (n+1)(n+2)(n+3)}+\cdots
\eqno(55)
$$
И
$$
\eqalignno{
t_n(\alpha)&=e^{-n\alpha}\left({(\alpha n)^n \over (n+1)!}
+2{(\alpha n)^{n+1}\over (n+2)!}+3{(\alpha n)^{n+2}\over (n+3)!}+\cdots\right)=\cr
&={e^{-n\alpha} n^n \alpha^n \over n!} (1-(1-\alpha)R(\alpha, n)). & (56)\cr
}
$$
ё ПОМОЩЬЮ ЭТИХ ФУНКЦИЙ МОЖНО ВЫРАЗИТЬ СРЕДНЕЕ ЧИСЛО ОБРАЩЕНИЙ,
НЕОБХОДИМЫХ ПРИ НЕУДАЧНОМ ПОИСКЕ С ПОМОЩЬЮ МЕТОДА~(A)
$$
C'_N=1+\alpha b t_b(\alpha)+O\left({1\over M})\right)
\eqno(57)
$$
($M, N\to\infty$), И СООТВЕТСТВУЮЩЕЕ ЧИСЛО ПРИ УДАЧНОМ
ПОИСКЕ
$$
C_N=1+((e^{-b\alpha}
b^b\alpha^b)/2b!)(2+(\alpha-1)b+(\alpha^2+(\alpha-1)^2(b-1))\times
R(\alpha, b))+O(1/M).
\eqno (58)
$$
¤ТО СОГЛАСУЕТСЯ С ДАННЫМИ ТАБЛ.~2 И~3.

яОСКОЛЬКУ МЕТОД ЦЕПОЧЕК~(A) ТРЕБУЕТ ОТДЕЛЬНОЙ ОБЛАСТИ ПЕРЕПОЛНЕНИЯ,
СЛЕДУЕТ ОЦЕНИТЬ ВОЗМОЖНОЕ КОЛИЧЕСТВО ПЕРЕПОЛНЕНИЙ. шХ СРЕДНЕЕ ЧИСЛО
СОСТАВЛЯЕТ~$M(C_n'-1)=N t_b(\alpha)$, ТАК КАК
%%638
$C'_N-1$~ЕСТЬ ЧИСЛО ПЕРЕПОЛНЕНИЙ В ЛЮБОМ ДАННОМ СПИСКЕ. яОЭТОМУ ТАБЛ.~2
МОЖНО ПОЛЬЗОВАТЬСЯ ДЛЯ НАХОЖДЕНИЯ РАЗМЕРА ЭТОЙ ОБЛАСТИ. яРИ
ФИКСИРОВАННОМ~$\alpha$ И~$M\to\infty$ СРЕДНЕКВАДРАТИЧНОЕ ОТКЛОНЕНИЕ ОБЩЕГО
ЧИСЛА ПЕРЕПОЛНЕНИЙ БУДЕТ ПРИБЛИЗИТЕЛЬНО ПРОПОРЦИОНАЛЬНО~$\sqrt{M}$.

рСИМПТОТИЧЕСКИЕ ЗНАЧЕНИЯ~$C'_N$ И~$C_N$ ПРИВЕДЕНЫ В УПР.~53, НО ЭТИ
ПРИБЛИЖЕНИЯ НЕ ОЧЕНЬ ХОРОШИ ПРИ МАЛЫХ~$b$ ИЛИ БОЛЬШИХ~$\alpha$; К
СЧАСТЬЮ, РЯД ДЛЯ~$R(\alpha, n)$ СХОДИТСЯ ОЧЕНЬ БЫСТРО ДАЖЕ ПРИ
БОЛЬШИХ~$\alpha$, ТАК ЧТО МОЖНО БЕЗ БОЛЬШОГО ТРУДА ОПЕРИРОВАТЬ ТОЧНЫМИ
ФОРМУЛАМИ. ьАКСИМУМ~$C_N$ И~$C'_N$ ДОСТИГАЕТСЯ ПРИ~$\alpha=1$ И ВЫРАЖАЕТСЯ
ПРИ~$b\to\infty$ КАК
$$
\eqalignno{
\max C'_N &=1+{e^{-b}b^{b+1}\over b!}=\sqrt{{b\over 2\pi}}+1+O(b^{-1/2}), &(59)\cr
\max C_N &=1+{e^{-b}b^b\over 2b!} (R(b)+1)={5\over4}+\sqrt{{2\over 9\pi
b}}+O(b^{-1}) &(60) \cr
}
$$
СОГЛАСНО ПРИБЛИЖЕНИЮ ёТИРЛИНГА И АНАЛИЗУ ФУНКЦИИ~$R(n)=R(1,n)-1$,
ПРОВЕДЕННОМУ В П.~1.2.11.3.

ёРЕДНЕЕ ЧИСЛО ОБРАЩЕНИЙ ПРИ УДАЧНОМ ПОИСКЕ С ПОМОЩЬЮ \emph{ЛИНЕЙНОГО}
ОПРОБОВАНИЯ ИМЕЕТ УДИВИТЕЛЬНО ПРОСТОЙ ВИД:
$$
C_N\approx 1+t_b(\alpha)+t_{2b}(\alpha)+t_{3b}(\alpha)+\ldots\,.
\eqno(61)
$$
¤ТО СООТНОШЕНИЕ МОЖНО ПОЯСНИТЬ СЛЕДУЮЩИМ ОБРАЗОМ: СРЕДНЕЕ ЧИСЛО ОБРАЩЕНИЙ
ПРИ ПОИСКЕ ВСЕХ $N$~КЛЮЧЕЙ РАВНО~$NC_N$, А ЭТО ЕСТЬ~$N+T_1+T_2+\ldots$,
ГДЕ $T_k$~ОБОЗНАЧАЕТ СРЕДНЕЕ ЧИСЛО КЛЮЧЕЙ, ПОИСК КОТОРЫХ ТРЕБУЕТ БОЛЕЕ
$k$~ОБРАЩЕНИЙ. ЄЕОРЕМА~P ГЛАСИТ, ЧТО, НЕ ИЗМЕНЯЯ~$C_N$, КЛЮЧИ МОЖНО
ВСТАВЛЯТЬ В ЛЮБОМ ПОРЯДКЕ; ОТСЮДА СЛЕДУЕТ, ЧТО $T_k$~РАВНО СРЕДНЕМУ ЧИСЛУ
ПЕРЕПОЛНЯЮЩИХ ЗАПИСЕЙ, КОТОРЫЕ ИМЕЛИСЬ БЫ ПРИ ИСПОЛЬЗОВАНИИ МЕТОДА
ЦЕПОЧЕК С $M/k$~БЛОКАМИ РАЗМЕРА~$kb$, Т.~Е.~$T_k=Nt_{kb}(\alpha)$, ЧТО И
УТВЕРЖДАЛОСЬ. фАЛЬНЕЙШЕЕ УТОЧНЕНИЕ ФОРМУЛЫ~(61) ПРОВЕДЕНО В УПР.~55.

юТЛИЧНОЕ ОБСУЖДЕНИЕ ПРАКТИЧЕСКИХ СООБРАЖЕНИЙ ПО ПОСТРОЕНИЮ ВНЕШНИХ
РАССЕЯННЫХ ТАБЛИЦ ДАЛ ўАРЛЬЗ юЛСОН
[{\sl Proc. ACM Nat'1 Conf.,\/} {\bf 24} (1969), 539--549]. ЁАБОТА
СОДЕРЖИТ НЕСКОЛЬКО ПОЛЕЗНЫХ ПРИМЕРОВ; В НЕЙ УКАЗЫВАЕТСЯ, ЧТО КОЛИЧЕСТВО
ПЕРЕПОЛНЯЮЩИХ ЗАПИСЕЙ ЗНАЧИТЕЛЬНО УВЕЛИЧИВАЕТСЯ, ЕСЛИ ФАЙЛ СЛУЖИТ ОБоЕКТОМ
ЧАСТЫХ ВСТАВОК И УДАЛЕНИЙ БЕЗ ПЕРЕРАЗМЕЩЕНИЯ ЗАПИСЕЙ. яРЕДСТАВЛЕН АНАЛИЗ
ЭТОЙ СИТУАЦИИ, ВЫПОЛНЕННЫЙ СОВМЕСТНО юЛСОНОМ И ДЕ~яЕЙСТЕРОМ.

\section ёРАВНЕНИЕ МЕТОДОВ. шТАК, МЫ ИЗУЧИЛИ МНОГО МЕТОДОВ ПОИСКА;
ЧЕМ ЖЕ НАМ РУКОВОДСТВОВАТЬСЯ ПРИ ВЫБОРЕ НАИЛУЧШЕГО ИЗ НИХ;
ДЛЯ КОНКРЕТНОГО ПРИЛОЖЕНИЯ? ЄРУДНО В НЕСКОЛЬКИХ СЛОВАХ ОПИСАТЬ ВСЕ, ЧТО
НАМ ХОТЕЛОСЬ БЫ УЧЕСТЬ ПРИ ВЫБОРЕ МЕТОДА ПОИСКА, ОДНАКО СЛЕДУЮЩИЕ
СООБРАЖЕНИЯ, ПОЖАЛУЙ, НАИБОЛЕЕ
%%639
\picture{ЁИС.~44. ёРАВНЕНИЕ МЕТОДОВ РАЗРЕШЕНИЯ КОЛЛИЗИЙ: ПРЕДЕЛЬНЫЕ
ЗНАЧЕНИЯ СРЕДНЕГО ЧИСЛА ПРОБ ПРИ~$M\to\infty$. (А)---НЕУДАЧНЫЙ ПОИСК
(КОЭФФИЦИЕНТ ЗАПОЛНЕНИЯ~$\alpha=N/M$);
(b)---УДАЧНЫЙ ПОИСК. ($L$---ЛИНЕЙНОЕ ОПРОБОВАНИЕ=АЛГОРИТМ~L; $U2$---СЛУЧАЙНОЕ
ОНРОБОВАНИЕ СО ВТОРИЧНЫМ ОКУЧИВАНИЕМ; $U$---РАВНОМЕРНОЕ
ХЕШИРОВАНИЕ$\approx$АЛГОРИТМ~D; $B$---АЛГОРИТМ~D С ИЗМЕНЕНИЕМ сРЕНТА;
$C$---МЕТОД ЦЕПОЧЕК СО СРАСТАНИЕМ=АЛГОРИТМ~C; $S$---РАЗДЕЛЬНЫЕ ЦЕПОЧКИ;
$SO$---РАЗДЕЛЬНЫЕ ЦЕПОЧКИ С УПОРЯДОЧЕННЫМИ СПИСКАМИ.)
}
%%640
ВАЖНЫ, ЕСЛИ МЫ ЗАИНТЕРЕСОВАНЫ В СОКРАЩЕНИИ ВРЕМЕНИ ПОИСКА И ОБоЕМА
ЗАНИМАЕМОЙ ПАМЯТИ.

эА РИС.~44 ПОКАЗАНЫ РЕЗУЛЬТАТЫ ПРОВЕДЕННОГО АНАЛИЗА. тИДНО, ЧТО РАЗЛИЧНЫЕ
СПОСОБЫ РАЗРЕШЕНИЯ КОЛЛИЗИЙ ПРИВОДЯТ К РАЗЛИЧНОМУ ЧИСЛУ ПРОБ. эО ЭТО ЕЩЕ
НЕ ВСЕ, ТАК КАК С ИЗМЕНЕНИЕМ МЕТОДА МЕНЯЕТСЯ ВРЕМЯ ПРОБЫ, ЧТО ЗАМЕТНО
ОТРАЖАЕТСЯ НА ВРЕМЕНИ РАБОТЫ (СМ.~РИС.~42). яРИ ЛИНЕЙНОМ ОПРОБОВАНИИ ЧАЩЕ,
 ЧЕМ В ДРУГИХ МЕТОДАХ, ПРОИСХОДИТ ОБРАЩЕНИЕ К ТАБЛИЦЕ, ЗАТО ЭТОТ МЕТОД
ПРОСТ. сОЛЕЕ ТОГО, НЕЛЬЗЯ СКАЗАТЬ, ЧТО ДАЖЕ ЛИНЕЙНОЕ ОПРОБОВАНИЕ СОВСЕМ УЖ
НИКУДА НЕ ГОДИТСЯ: ЕСЛИ ТАБЛИЦА ЗАПОЛНЕНА НА 90\%, АЛГОРИТМ~L ТРЕБУЕТ В
СРЕДНЕМ МЕНЕЕ $5.5$~ПРОБЫ ДЛЯ ОБНАРУЖЕНИЯ СЛУЧАЙНОГО ЭЛЕМЕНТА. (юДНАКО
СРЕДНЕЕ ЧИСЛО ПРОБ ПРИ ВСТАВКЕ \emph{НОВОГО} ЭЛЕМЕНТА С ПОМОЩЬЮ
АЛГОРИТМА~L РАВНО~$50.5$, ЕСЛИ ТАБЛИЦА ПОЛНА НА 90\%.)

шЗ РИС.~44 ВИДНО, ЧТО МЕТОДЫ ЦЕПОЧЕК ВЕСЬМА ЭКОНОМНЫ С ТОЧКИ ЗРЕНИЯ ЧИСЛА
ПРОБ, НО ПОТРЕБНОСТЬ В ДОПОЛНИТЕЛЬНОМ ПРОСТРАНСТВЕ ПАМЯТИ ДЛЯ ПОЛЕЙ ССЫЛОК
ИНОГДА (ПРИ НЕБОЛЬШОМ РАЗМЕРЕ ЗАПИСЕЙ) ДЕЛАЕТ БОЛЕЕ ПРИВЛЕКАТЕЛЬНОЙ
ОТКРЫТУЮ АДРЕСАЦИЮ. эАПРИМЕР, ЕСЛИ НУЖНО СДЕЛАТЬ ВЫБОР МЕЖДУ ТАБЛИЦЕЙ С
ЦЕПОЧКАМИ НА 500~ЭЛЕМЕНТОВ И ТАБЛИЦЕЙ С ОТКРЫТОЙ АДРЕСАЦИЕЙ НА
1000~ЭЛЕМЕНТОВ, ТО ПОСЛЕДНЯЯ, ОЧЕВИДНО, ПРЕДПОЧТИТЕЛЬНЕЕ, ИБО ОНА
ОБЕСПЕЧИВАЕТ ЭФФЕКТИВНЫЙ ПОИСК СРЕДИ 500~ЗАПИСЕЙ И СПОСОБНА ВМЕСТИТЬ В ДВА
РАЗА БОЛЬШЕ ДАННЫХ. ё ДРУГОЙ СТОРОНЫ, ПОРОЙ В СИЛУ РАЗМЕРА ЗАПИСЕЙ ИЛИ
ИХ ФОРМАТА ПРОСТРАНСТВО ПОД ПОЛЯ ССЫЛОК ДОСТАЕТСЯ ФАКТИЧЕСКИ БЕСПЛАТНО
(СР.~С~УПР.~65).

ъАК СООТНОСЯТСЯ МЕТОДЫ ХЕШИРОВАНИЯ С ДРУГИМИ СТРАТЕГИЯМИ ПОИСКА,
ИЗУЧЕННЫМИ В ЭТОЙ ГЛАВЕ? ёРАВНИВАЯ ИХ ПО СКОРОСТИ, МОЖНО УТВЕРЖДАТЬ, ЧТО
МЕТОДЫ ХЕШИРОВАНИЯ ЛУЧШЕ, ЕСЛИ ЧИСЛО ЗАПИСЕЙ ВЕЛИКО, ПОСКОЛЬКУ СРЕДНЕЕ
ВРЕМЯ ПОИСКА ДЛЯ МЕТОДОВ ХЕШИРОВАНИЯ ОСТАЕТСЯ ОГРАНИЧЕННЫМ
ПРИ~$N\to\infty$ В СЛУЧАЕ, КОГДА ТАБЛИЦА НЕ СТАНОВИТСЯ СЛИШКОМ ЗАПОЛНЕННОЙ.
 эАПРИМЕР, ПРОГРАММЕ~L НУЖНО ЛИШЬ 55~ЕДИНИЦ ВРЕМЕНИ ДЛЯ УДАЧНОГО ПОИСКА В
ТАБЛИЦЕ, ЗАПОЛНЕННОЙ НА~90\%; ЭТО БЫСТРЕЕ САМОЙ БЫСТРОЙ ИЗ ИЗВЕСТНЫХ НАМ
\MIX-ПРОГРАММ БИНАРНОГО ПОИСКА (СМ.~УПР.~6.2.1-24), ЕСЛИ~$N$ БОЛЬШЕ~600
ИЛИ ОКОЛО ТОГО, И ПЛАТИТЬ ЗА ЭТО ПРИХОДИТСЯ ЛИШЬ 11\%~ПРОСТРАНСТВА
ПАМЯТИ. сОЛЕЕ ТОГО, БИНАРНЫЙ ПОИСК ГОДИТСЯ ЛИШЬ ДЛЯ ФИКСИРОВАННЫХ ТАБЛИЦ,
 В ТО ВРЕМЯ КАК РАССЕЯННЫЕ ТАБЛИЦЫ ДОПУСКАЮТ ЭФФЕКТИВНЫЕ ПРОЦЕДУРЫ ВСТАВКИ.

ьЫ МОЖЕМ ТАКЖЕ СРАВНИТЬ ПРОГРАММУ~L С МЕТОДАМИ ПОИСКА ПО ДЕРЕВУ,
ДОПУСКАЮЩИМИ ДИНАМИЧЕСКИЕ ВСТАВКИ. яРОГРАММА~L ПРИ~$\alpha=0.9$ БЫСТРЕЕ
ПРОГРАММЫ~6.2.2T, ЕСЛИ $N$~ПРЕВЫШАЕТ ПРИБЛИЗИТЕЛЬНО~90, И БЫСТРЕЕ
ПРОГРАММЫ~6.3D (УПР.~6.3-9), ЕСЛИ $N$~ПРЕВЫШАЕТ ПРИМЕРНО~75.

%%641
ЄОЛЬКО ОДИН МЕТОД ЭТОЙ ГЛАВЫ В СЛУЧАЕ УДАЧНОГО ПОИСКА ВЕСЬМА ЭФФЕКТИВЕН И
ФАКТИЧЕСКИ НЕ ДАЕТ ПЕРЕРАСХОДА ПАМЯТИ, А ИМЕННО АЛГОРИТМ~D С ИЗМЕНЕНИЕМ
сРЕНТА. юН ПОЗВОЛЯЕТ ПОМЕСТИТЬ $N$~ЗАПИСЕЙ В ТАБЛИЦУ РАЗМЕРА~$M=N+1$ И НАХОДИТЬ
ЛЮБУЮ ЗАПИСЬ В СРЕДНЕМ ЗА $2{1\over2}$~ПРОБЫ. эЕ НУЖНО ДОПОЛНИТЕЛЬНОГО
ПРОСТРАНСТВА ДЛЯ ПОЛЕЙ ССЫЛОК И~Т.~П.; ОДНАКО НЕУДАЧНЫЙ ПОИСК БУДЕТ
КРАЙНЕ МЕДЛЕННЫМ---ОН ПОТРЕБУЕТ ОКОЛО ${1\over2}N$~ПРОБ.

ЄАКИМ ОБРАЗОМ, ХЕШИРОВАНИЕ ИМЕЕТ СВОИ ПРЕИМУЩЕСТВА. ё ДРУГОЙ СТОРОНЫ,
ПОИСК В РАССЕЯННЫХ ТАБЛИЦАХ ВСЕ ЖЕ УСТУПАЕТ ИЗУЧЕННЫМ РАНЕЕ МЕТОДАМ ПО
ТРЕМ ВАЖНЫМ ПУНКТАМ.

\medskip
a)~яОСЛЕ НЕУДАЧНОГО ПОИСКА В РАССЕЯННОЙ ТАБЛИЦЕ МЫ ЗНАЕМ ЛИШЬ ТО, ЧТО
НУЖНОГО КЛЮЧА ТАМ НЕТ. ьЕТОДЫ ПОИСКА, ОСНОВАННЫЕ НА СРАВНЕНИЯХ, ВСЕГДА
ДАЮТ БОЛЬШЕ ИНФОРМАЦИИ; ОНИ ПОЗВОЛЯЮТ НАЙТИ НАИБОЛЬШИЙ $\hbox{КЛЮЧ} \le K$
ИЛИ НАИМЕНЬШИЙ $\hbox{КЛЮЧ}\ge K$ , ЧТО ВАЖНО ВО МНОГИХ ПРИЛОЖЕНИЯХ
(НАПРИМЕР, ДЛЯ ИНТЕРПОЛЯЦИИ ЗНАЧЕНИЙ ФУНКЦИИ ПО ХРАНЯЩЕЙСЯ ТАБЛИЦЕ).
¤ТИ ЖЕ МЕТОДЫ МОЖНО ИСПОЛЬЗОВАТЬ И ДЛЯ НАХОЖДЕНИЯ ВСЕХ КЛЮЧЕЙ, ЛЕЖАЩИХ
\emph{МЕЖДУ} ДВУМЯ ЗАДАННЫМИ ВЕЛИЧИНАМИ~$K$ И~$K'$. фАЛЕЕ, АЛГОРИТМЫ
ПОИСКА ПО ДЕРЕВУ~\S~6.2 ПОЗВОЛЯЮТ ЛЕГКО РАСПЕЧАТАТЬ СОДЕРЖИМОЕ ТАБЛИЦЫ В
ВОЗРАСТАЮЩЕМ ПОРЯДКЕ БЕЗ СПЕЦИАЛЬНОЙ СОРТИРОВКИ, А ЭТО ИНОГДА БЫВАЕТ НУЖНО.

\medskip
b)~ўАСТО ДОВОЛЬНО ТРУДНО РАСПРЕДЕЛИТЬ ПАМЯТЬ ДЛЯ РАССЕЯННЫХ ТАБЛИЦ; ПОД
ХЕШ-ТАБЛИЦУ НУЖНО ОТВЕСТИ ОПРЕДЕЛЕННУЮ ОБЛАСТЬ ПАМЯТИ, А РАЗМЕР ЕЕ НЕ
ВСЕГДА ЯСЕН. хСЛИ ОТВЕСТИ СЛИШКОМ МНОГО ПАМЯТИ, ТО ТАКАЯ РАСТОЧИТЕЛЬНОСТЬ
ОТРАЗИТСЯ НА ДРУГИХ СПИСКАХ ИЛИ НА ДРУГИХ ПОЛЬЗОВАТЕЛЯХ ¤ть, НО
ЕСЛИ ОТВЕСТИ МАЛО МЕСТА, ТАБЛИЦА ПЕРЕПОЛНИТСЯ! яРИ ПЕРЕПОЛНЕНИИ РАССЕЯННОЙ
ТАБЛИЦЫ, ВЕРОЯТНО, ЛУЧШЕ ВСЕГО "РЕХЕШИРОВАТЬ" ЕЕ, Т.~Е.~ОТВЕСТИ БОЛЬШЕ
ПРОСТРАНСТВА И ИЗМЕНИТЬ ХЕШ-ФУНКЦИЮ, А ЗАТЕМ ВСТАВИТЬ ЗАПИСИ В БОЛЬШУЮ
ТАБЛИЦУ. Ї.~їОПГУД
[{\sl Comp. Bulletin,\/} {\bf 11} (1968), 297--300] ПРЕДЛОЖИЛ РЕХЕШИРОВАТЬ
ТАБЛИЦУ, ЕСЛИ КОЭФФИЦИЕНТ ЗАПОЛНЕНИЯ ДОСТИГНЕТ~$\alpha$, ЗАМЕНЯЯ~$M$
НА~$d_0 M$; С ПОМОЩЬЮ ПРИВЕДЕННОГО ВЫШЕ АНАЛИЗА И ХАРАКТЕРИСТИК ДАННЫХ
МОЖНО ОПРЕДЕЛИТЬ КРИТИЧЕСКУЮ ТОЧКУ, КОГДА РЕХЕШИРОВАНИЕ СТАНОВИТСЯ ДЕШЕВЛЕ
ДАЛЬНЕЙШЕЙ РАБОТЫ С ТОЙ ЖЕ ТАБЛИЦЕЙ, И ТЕМ САМЫМ ВЫБРАТЬ ЗНАЧЕНИЯ
ПАРАМЕТРОВ~$\alpha_0$ И~$d_0$. (чАМЕТИМ, ЧТО МЕТОД ЦЕПОЧЕК СВОБОДЕН ОТ
МУЧИТЕЛЬНЫХ ПЕРЕПОЛНЕНИИ И НЕ НУЖДАЕТСЯ В РЕХЕШИРОВАНИИ, ОДНАКО ПРИ
ФИКСИРОВАННОМ~$M$ И РАСТУЩЕМ~$N$ ВРЕМЯ ПОИСКА СТАНОВИТСЯ
ПРОПОРЦИОНАЛЬНЫМ~$N$.) эАПРОТИВ, АЛГОРИТМЫ ПОИСКА СО ВСТАВКОЙ ПО ДЕРЕВУ НЕ
ИЗОБИЛУЮТ ТЯГОСТНЫМИ РЕХЕШИРОВАНИЯМИ; ДЕРЕВЬЯ РАСТУТ НЕ БОЛЬШЕ, ЧЕМ ЭТО
НЕОБХОДИМО. яРИ РАБОТЕ С ВИРТУАЛЬНОЙ ПАМЯТЬЮ НУЖНО,
%% 642
ПО ВСЕЙ ВЕРОЯТНОСТИ, ИСПОЛЬЗОВАТЬ ПОИСК ПО ДЕРЕВУ ИЛИ ЦИФРОВОЙ ПОИСК
ПО ДЕРЕВУ ВМЕСТО СОЗДАНИЯ БОЛЬШИХ РАССЕЯННЫХ ТАБЛИЦ, ВЫЗЫВАЮЩИХ ПОДКАЧКУ
НОВОЙ СТРАНИЦЫ ПОЧТИ ПРИ КАЖДОМ ХЕШИРОВАНИИ КЛЮЧА.

\medskip
c)~эАКОНЕЦ, ПРИ ИСПОЛЬЗОВАНИИ МЕТОДОВ ХЕШИРОВАНИЯ НУЖНО СВЯТО ВЕРИТЬ В
ТЕОРИЮ ВЕРОЯТНОСТЕЙ, ИБО ОНИ ЭФФЕКТИВНЫ ЛИШЬ В СРЕДНЕМ, А НАИХУДШИЙ СЛУЧАЙ
ПРОСТО УЖАСЕН! ъАК И В СИТУАЦИИ С ДАТЧИКАМИ СЛУЧАЙНЫХ ЧИСЕЛ, МЫ НЕ МОЖЕМ
БЫТЬ ПОЛНОСТЬЮ УВЕРЕННЫМИ В ТОМ, ЧТО ПРИ ПРИМЕНЕНИИ К НОВОМУ МНОЖЕСТВУ
ДАННЫХ ХЕШ-ФУНКЦИЯ БУДЕТ РАБОТАТЬ УДОВЛЕТВОРИТЕЛЬНО. яОЭТОМУ РАССЕЯННАЯ
ПАМЯТЬ НЕ ВСЕГДА ПОДХОДИТ ДЛЯ РАБОТЫ В РЕАЛЬНОМ МАСШТАБЕ ВРЕМЕНИ, НАПРИМЕР
ДЛЯ УПРАВЛЕНИЯ ДВИЖЕНИЕМ ТРАНСПОРТА, ПОСКОЛЬКУ НА КАРТУ
ПОСТАВЛЕНЫ ЧЕЛОВЕЧЕСКИЕ ЖИЗНИ. рЛГОРИТМЫ СБАЛАНСИРОВАННОГО
ДЕРЕВА (П.~6.2.3 И~6.2.4) ГОРАЗДО БЕЗОПАСНЕЕ, ВЕДЬ ОНИ ИМЕЮТ
ГАРАНТИРОВАННУЮ ВЕРХНЮЮ ГРАНИЦУ ВРЕМЕНИ ПОИСКА.

\section шСТОРИЯ. яО-ВИДИМОМУ, ВПЕРВЫЕ ИДЕЮ ХЕШИРОВАНИЯ ВЫСКАЗАЛ у.~ыАН. т
ЯНВАРЕ 1953~Г., СОСТАВЛЯЯ ОДИН ИЗ ВНУТРЕННИХ ДОКУМЕНТОВ ФИРМЫ~IBM, ОН
ПРЕДЛОЖИЛ ИСПОЛЬЗОВАТЬ МЕТОД ЦЕПОЧЕК; ЭТО ЯВИЛОСЬ ТАКЖЕ ОДНОЙ ИЗ ПЕРВЫХ
ПУБЛИКАЦИЙ ПО СВЯЗАННЫМ ЛИНЕЙНЫМ СПИСКАМ. юН УКАЗАЛ НА ЖЕЛАТЕЛЬНОСТЬ
ИСПОЛЬЗОВАНИЯ ДЛЯ ВНЕШНЕГО ПОИСКА БЛОКОВ, СОДЕРЖАЩИХ БОЛЕЕ
ОДНОГО ЭЛЕМЕНТА. тСКОРЕ ПОСЛЕ ЭТОГО ¤.~ыИН ПРОДВИНУЛ АНАЛИЗ ыАНА НЕМНОГО
ДАЛЬШЕ И ПРЕДЛОЖИЛ МЕТОД ОБРАБОТКИ ПЕРЕПОЛНЕНИИ С ПОМОЩЬЮ "ВЫРОЖДАЮЩИХСЯ
АДРЕСОВ"; НАПРИМЕР, ПРИ ПЕРЕПОЛНЕНИИ ПЕРВИЧНОГО БЛОКА 2748~ЗАПИСИ
ПОПАДАЮТ ВО ВТОРИЧНЫЙ БЛОК~274; ЕСЛИ И ОН ПЕРЕПОЛНИЛСЯ, ИСПОЛЬЗУЕТСЯ
ТРЕТИЧНЫЙ БЛОК~27 И~Т.~Д. яРЕДПОЛАГАЕТСЯ, ЧТО ЕСТЬ 10000~ПЕРВИЧНЫХ БЛОКОВ,
1000~ВТОРИЧНЫХ, 100~ТРЕТИЧНЫХ И~Т.~Д. яЕРВОНАЧАЛЬНО ПРЕДЛОЖЕННЫЕ ыАНОМ
ХЕШ-ФУНКЦИИ БЫЛИ ЛИТЕРНО-ЦИФРОВЫМИ;
НАПРИМЕР, СКЛАДЫВАЛИСЬ ПО МОДУЛЮ~10 ПАРЫ СОСЕДНИХ ЦИФР КЛЮЧА, ТАК
ЧТО~31415926 СЖИМАЛОСЬ ДО~4548.

яРИМЕРНО В ЭТО ЖЕ ВРЕМЯ ИДЕЯ ХЕШИРОВАНИЯ ПОЯВИЛАСЬ У ДРУГОЙ ГРУППЫ
СОТРУДНИКОВ ФИРМЫ~IBM: фЖИН ¤МДЕЛ, ¤ЛЕЙН сОЭМ, э.~ЁОЧЕСТЕРА И рРТУРА
ёЭМЮЭЛЯ, СТРОИВШИХ АВТОКОДНУЮ ПРОГРАММУ ДЛЯ IBM~701. фЛЯ РАЗРЕШЕНИЯ
ПРОБЛЕМЫ КОЛЛИЗИЙ ¤МДЕЛ ВЫСКАЗАЛА ИДЕЮ ОТКРЫТОЙ АДРЕСАЦИИ С ЛИНЕЙНЫМ
ОПРОБОВАНИЕМ.

т ОТКРЫТОЙ ПЕЧАТИ ХЕШИРОВАНИЕ ВПЕРВЫЕ БЫЛО ОПИСАНО рРНОЛЬДОМ фУМИ
[{\sl Computers and Automation,\/} {\bf 5}, 12 (December 1956), 6--9].
шМЕННО ОН ВПЕРВЫЕ УПОМЯНУЛ ИДЕЮ ДЕЛЕНИЯ НА ПРОСТОЕ ЧИСЛО И ИСПОЛЬЗОВАНИЯ
ОСТАТКА В КАЧЕСТВЕ ХЕШ-АДРЕСА. т СТАТЬЕ фУМИ УПОМИНАЕТСЯ МЕТОД ЦЕПОЧЕК,
ОДНАКО ОТКРЫТОЙ АДРЕСАЦИИ В НЕЙ НЕТ. р.~я.~хРШОВ В 1957~Г. НЕЗАВИСИМО
ОТКРЫЛ ЛИНЕЙНУЮ ОТКРЫТУЮ АДРЕСАЦИЮ [{\sl фрэ ёёёЁ,\/} {\bf 118} (1958),
427--430];
%%643
ОН ОПУБЛИКОВАЛ ЭМПИРИЧЕСКИЕ РЕЗУЛЬТАТЫ О ЧИСЛЕ ПРОБ, СПРАВЕДЛИВО
ПРЕДПОЛОЖИВ, ЧТО ПРИ~$N/M<2/3$ СРЕДНЕЕ ЧИСЛО ПРОБ ДЛЯ УДАЧНОГО ПОИСКА $<2$.

ъЛАССИЧЕСКАЯ СТАТЬЯ є.~яЕТЕРСОНА
[{\sl IBM J.~Research \& Development,\/} {\bf 1} (1957), 130--146] БЫЛА
ПЕРВОЙ ВАЖНОЙ РАБОТОЙ ПО ВОПРОСУ ПОИСКА В БОЛЬШИХ ФАЙЛАХ. яЕТЕРСОН
ОПРЕДЕЛИЛ ОТКРЫТУЮ АДРЕСАЦИЮ В ОБЩЕМ СЛУЧАЕ, ПРОАНАЛИЗИРОВАЛ
ХАРАКТЕРИСТИКИ РАВНОМЕРНОГО ХЕШИРОВАНИЯ И ПРИВЕЛ
МНОГОЧИСЛЕННЫЕ СТАТИСТИЧЕСКИЕ ДАННЫЕ О ПОВЕДЕНИИ ЛИНЕЙНОЙ ОТКРЫТОЙ
АДРЕСАЦИИ ПРИ РАЗЛИЧНЫХ РАЗМЕРАХ БЛОКОВ, ПОДМЕТИВ УХУДШЕНИЕ
ХАРАКТЕРИСТИК, ВОЗНИКАЮЩЕЕ ПРИ УДАЛЕНИИ ЭЛЕМЕНТОВ. фРУГОЙ ВСЕСТОРОННИЙ
ОБЗОР ПРЕДМЕТА ШЕСТЬЮ ГОДАМИ ПОЗЖЕ ОПУБЛИКОВАЛ тЕРНЕР сУХХОЛЬЦ [{\sl IBM
Systems J.,\/} {\bf 2} (1963), 86--111]; ОН НАИБОЛЕЕ ОСНОВАТЕЛЬНО ИЗУЧИЛ
ХЕШ-ФУНКЦИИ.

ъ ЭТОМУ ВРЕМЕНИ ЛИНЕЙНОЕ ОПРОБОВАНИЕ БЫЛО ЕДИНСТВЕННЫМ ТИПОМ СХЕМЫ
ОТКРЫТОЙ АДРЕСАЦИИ, ОПИСАННЫМ В ЛИТЕРАТУРЕ, ХОТЯ НЕСКОЛЬКИМИ АВТОРАМИ
НЕЗАВИСИМО БЫЛА РАЗРАБОТАНА ДРУГАЯ СХЕМА, ОСНОВАННАЯ НА НЕОДНОКРАТНОМ
СЛУЧАЙНОМ ОПРОБОВАНИИ С ПОМОЩЬЮ НЕЗАВИСИМЫХ ХЕШ-ФУНКЦИЙ (СМ.~УПР.~48). т
ТЕЧЕНИЕ НЕСКОЛЬКИХ СЛЕДУЮЩИХ ЛЕТ ХЕШИРОВАНИЕ СТАЛО ИСПОЛЬЗОВАТЬСЯ ОЧЕНЬ
ШИРОКО, НО О НЕМ ЕДВА ЛИ БЫЛО ОПУБЛИКОВАНО ЧТО-НИБУДЬ НОВОЕ. чАТЕМ ЁОБЕРТ
ьОРРИС НАПИСАЛ ОКАЗАВШИЙ БОЛЬШОЕ ВЛИЯНИЕ ОБЗОР ПРЕДМЕТА [{\sl CACM,\/}
{\bf 11} (1968), 38--44], В КОТОРОМ ОН ВВЕЛ ИДЕЮ СЛУЧАЙНОГО ОПРОБОВАНИЯ
(СО ВТОРИЧНЫМ СКУЧИВАНИЕМ). ёТАТЬЯ ьОРРИСА ЗАВЕРШИЛА УСИЛИЯ, ПРИВЕДШИЕ К
СОЗДАНИЮ АЛГОРИТМА~D И ЕГО УСОВЕРШЕНСТВОВАНИЙ.

шНТЕРЕСНО ОТМЕТИТЬ, ЧТО СЛОВО "ХЕШИРОВАНИЕ" ("hashing") В ЕГО НЫНЕШНЕМ
ЗНАЧЕНИИ, ВЕРОЯТНО, НЕ ПОЯВЛЯЛОСЬ В ПЕЧАТИ ДО КОНЦА 60-Х ГОДОВ, ХОТЯ К
ТОМУ ВРЕМЕНИ В РАЗНЫХ ЧАСТЯХ СВЕТА ОНО УЖЕ СТАЛО ОБЩЕПРИНЯТЫМ ЖАРГОНОМ.
яО-ВИДИМОМУ, ВПЕРВЫЕ ЭТО СЛОВО БЫЛО ИСПОЛЬЗОВАНО В КНИГЕ їЕЛЛЕРМЭНА
[Digital Computers System Principles (New York, 1967), 152]. шЗ ПРИМЕРНО
60~ДОКУМЕНТОВ, ОТНОСЯЩИХСЯ К 1953--1967~ГГ., ИЗУЧЕННЫХ АВТОРОМ
ПРИ НАПИСАНИИ ДАННОГО ПАРАГРАФА, СЛОВО "ХЕШИРОВАНИЕ" ВСТРЕЧАЕТСЯ ЛИШЬ
ОДНАЖДЫ---В НЕОПУБЛИКОВАННОМ ДОКУМЕНТЕ ФИРМЫ, СОСТАВЛЕННОМ є.~яЕТЕРСОНОМ
(1961~Г.). ъАК ПО ВОЛШЕБСТВУ, ГЛАГОЛ "ХЕШИРОВАТЬ" (to hash) В СЕРЕДИНЕ
60-Х ГОДОВ СТАЛ СТАНДАРТНЫМ ТЕРМИНОМ ДЛЯ ПРЕОБРАЗОВАНИЯ КЛЮЧА, ХОТЯ
ИСПОЛЬЗОВАТЬ ТАКОЕ НЕДОСТОЙНОЕ СЛОВО В ПЕЧАТИ НИКТО НЕ ОСМЕЛИВАЛСЯ ДО 1967~Г.!

\excercises
\ex[20] яРЕДПОЛОЖИМ, ЧТО   БАЙТЫ 1, 2, 3 КЛЮЧА~$K$ СОДЕРЖАТ КОДЫ ЛИТЕР,
МЕНЬШИЕ~30. т КАКИХ ПРЕДЕЛАХ ЗАКЛЮЧЕНО СОДЕРЖИМОЕ~|rI1|, КОГДА
ДОСТИГАЕТСЯ ИНСТРУКЦИЯ~|9H| В ТАБЛ.~1?

\ex[20] эАЙДИТЕ ДОВОЛЬНО ИЗВЕСТНОЕ АНГЛИЙСКОЕ СЛОВО, КОТОРОЕ МОЖНО
ДОБАВИТЬ В ТАБЛ.~1 БЕЗ ИЗМЕНЕНИЯ ПРОГРАММЫ.

%%644
\ex[23] юБоЯСНИТЕ, ПОЧЕМУ ПРОГРАММУ В ТАБЛ.~1 НЕЛЬЗЯ ЗАМЕНИТЬ НА
БОЛЕЕ ПРОСТУЮ, НАЧИНАЮЩУЮСЯ СО СЛЕДУЮЩИХ ПЯТИ ИНСТРУКЦИЙ:
\medskip
\centerline{|LD1  K(1:1)| ИЛИ~|LD1N  K(1:1)|}
\centerline{|LD2  K(2:2)| ИЛИ~|LD2N  K(2:2)|}
\centerline{
\vbox{
 \hbox{\strut|INC1  $a$, 2|}
 \hbox{\strut|LD2   K(3:3)|}
 \hbox{\strut|J2Z   9F|}
}}
\medskip
НИ ПРИ КАКОЙ КОНСТАНТЕ~$a$, УЧИТЫВАЯ, ЧТО РАЗНЫЕ КЛЮЧИ НЕ МОГУТ ИМЕТЬ
ОДИНАКОВЫЕ ХЕШ-АДРЕСА.

\ex[ь30] ёКОЛЬКО ЧЕЛОВЕК НУЖНО ПРИГЛАСИТЬ НА ВЕЧЕРИНКУ, ЧТОБЫ С
ВЕРОЯТНОСТЬЮ $>{1\over2}$ НАШЛИСЬ \emph{ТРОЕ,} ИМЕЮЩИЕ ОДИН И ТОТ ЖЕ
ДЕНЬ РОЖДЕНИЯ?

\ex[15] ьИСТЕР ЄУПИЦА ПИСАЛ КОМПИЛЯТОР С ЇюЁЄЁрэА, ИСПОЛЬЗУЯ ДЕСЯТИЧНУЮ
МАШИНУ \MIX, И ПЕРЕД НИМ ВСТАЛА ЗАДАЧА СОЗДАНИЯ ТАБЛИЦЫ СИМВОЛОВ ДЛЯ
ХРАНЕНИЯ ИМЕН ПЕРЕМЕННЫХ КОМПИЛИРУЕМОЙ ПРОГРАММЫ. фЛИНА ЭТИХ ИМЕН
ОГРАНИЧЕНА ДЕСЯТЬЮ ЛИТЕРАМИ. юН РЕШИЛ ИСПОЛЬЗОВАТЬ РАССЕЯННУЮ ТАБЛИЦУ
С~$M=100$ И БЫСТРУЮ ХЕШ-ФУНКЦИЮ~$h(K)=\hbox{КРАЙННЙ ЛЕВЫЙ БАЙТ~$K$}$.
їОРОШО ЛИ ЭТО?

\ex[15] ЁАЗУМНО ЛИ ЗАМЕНИТЬ ПЕРВЫЕ ДВЕ ИНСТРУКЦИИ В~(3) НА~|LDA K|;
|ENTX 0|?

\ex[ть30] \exhead(яОЛИНОМИАЛЬНОЕ ХЕШИРОВАНИЕ.) ЎЕЛЬ НАСТОЯЩЕГО
УПРАЖНЕНИЯ---РАССМОТРЕТЬ ПОСТРОЕНИЕ МНОГОЧЛЕНОВ~$P(x)$ ТИПА~(10), КОТОРЫЕ
ПРЕОБРАЗУЮТ $n\hbox{-БИТОВЫЕ}$ КЛЮЧИ В $m\hbox{-БИТОВЫЕ}$ АДРЕСА И ПРИ
ЭТОМ РАЗНЫЕ КЛЮЧИ, ОТЛИЧАЮЩИЕСЯ НЕ БОЛЕЕ ЧЕМ $t$~БИТАМИ, ПОЛУЧАТ РАЗНЫЕ
АДРЕСА. яО ЗАДАННЫМ ЗНАЧЕНИЯМ~$n$, $t\le n$, И ЦЕЛОМУ ЧИСЛУ~$k$, ТАКОМУ,
ЧТО~$n$ ДЕЛИТ~$2^k-1$, МЫ ПОСТРОИМ МНОГОЧЛЕН, СТЕПЕНЬ ОТ КОТОРОГО
ЯВЛЯЕТСЯ ФУНКЦИЕЙ~$n$, $t$ И~$k$. (юБЫЧНО, ЕСЛИ ЭТО НЕОБХОДИМО,
$n$~УВЕЛИЧИВАЕТСЯ, ПОЭТОМУ $k$~МОЖНО ВЫБРАТЬ ДОСТАТОЧНО МАЛЫМ.)

яУСТЬ $S$---МИНИМАЛЬНОЕ МНОЖЕСТВО ЦЕЛЫХ ЧИСЕЛ, ТАКОЕ,
ЧТО~$\set{1,2,~\ldots, t}\subseteq S$ И~$(2j) \bmod n \in S$ ДЛЯ
ВСЕХ~$j\in S$. эАПРИМЕР, ЕСЛИ~$n=15$, $k=4$, $t=6$, ИМЕЕМ~$S=\set{1, 2, 3,
4, 5, 6, 8, 10, 12, 9}$. юПРЕДЕЛИМ ТЕПЕРЬ МНОГОЧЛЕН~$P(x)= \prod_{j\in S}
(x-\alpha^j)$, ГДЕ $\alpha$~ЕСТЬ ЭЛЕМЕНТ ПОРЯДКА~$n$ КОНЕЧНОГО
ПОЛЯ~$GF(2^k)$, А КОЭФФИЦИЕНТЫ~$P(x)$ ВЫЧИСЛЯЮТСЯ В ЭТОМ ПОЛЕ. ёТЕПЕНЬ~$m$
МНОГОЧЛЕНА~$P(x)$ РАВНА ЧИСЛУ ЭЛЕМЕНТОВ В~$S$.
хСЛИ~$\alpha^j$---КОРЕНЬ~$P(x)$, ТО И~$\alpha^2j$---КОРЕНЬ; ОТСЮДА СЛЕДУЕТ,
ЧТО КОЭФФИЦИЕНТЫ~$P(x)$ УДОВЛЕТВОРЯЮТ СООТНОШЕНИЮ~$p^2_i=p_i$, Т.~Е.~ОНИ
РАВНЫ~0 ИЛИ~1.

фОКАЖИТЕ, ЧТО ЕСЛИ~$R(x)=r_{n-1}x^{n-1}+\cdots+r_1x+r_0$---НЕНУЛЕВОЙ
МНОГОЧЛЕН ПО МОДУЛЮ~2 С НЕ БОЛЕЕ ЧЕМ $t$~НЕНУЛЕВЫМИ КОЭФФИЦИЕНТАМИ,
ТО~$R(x)$ НЕ КРАТЕН~$P(x)$ ПО МОДУЛЮ~2. [юТСЮДА СЛЕДУЕТ, ЧТО
СООТВЕТСТВУЮЩАЯ ХЕШ-ФУНКЦИЯ ВЕДЕТ СЕБЯ ОБЕЩАННЫМ ОБРАЗОМ.]

\ex[ь34] \exhead(ЄЕОРЕМА О ТРЕХ ДЛИНАХ.) яУСТЬ~$\theta$---ИРРАЦИОНАЛЬНОЕ
ЧИСЛО, ЛЕЖАЩЕЕ МЕЖДУ~0 И~1, ПРЕДСТАВЛЕНИЕ КОТОРОГО В ВИДЕ ПРАВИЛЬНОЙ
НЕПРЕРЫВНОЙ ДРОБИ (ОБОЗНАЧЕНИЯ П.~4.5.3) ЕСТЬ~$\theta=/a_1, a_2, a_3,
~\ldots/$. яУСТЬ~$q_0=0$, $p_0=1$, $q_1=1$, $p_1=0$
И~$q_{k+1}=a_kq_k+q_{k-1}$, $p_{k+1}=a_kp_k+p_{k-1}$ ПРИ~$k\ge1$.
юБОЗНАЧИМ~$x \bmod 1=x-\floor{x}$ ЧЕРЕЗ~$\{x\}$, А~$x-\ceil{x}+1$
ЧЕРЕЗ~$\{x\}^+$. сУДЕМ НУМЕРОВАТЬ ОТРЕЗКИ В ТОМ ПОРЯДКЕ, КАК ОНИ
ПОЛУЧАЮТСЯ ПРИ ПОСЛЕДОВАТЕЛЬНЫХ ВСТАВКАХ В ИНТЕРВАЛ~$[0, 1]$
ТОЧЕК~$\{\theta\}$, $\{2\theta\}$, $\{3\theta\}$,~\dots, ТАК ЧТО ПЕРВЫЙ
ОТРЕЗОК ДАННОЙ ДЛИНЫ ИМЕЕТ НОМЕР~0, ВТОРОЙ---НОМЕР~1 И~Т.~Д. фОКАЖИТЕ, ЧТО
ВСЕ СЛЕДУЮЩИЕ УТВЕРЖДЕНИЯ ВЕРНЫ.
ыЕВЫМ КОНЦОМ ИНТЕРВАЛА НОМЕР~$s$ ДЛИНЫ~$\{t\theta\}$,
ГДЕ~$t=rq_k+q_{k-1}$, $0\le r<a_k$, $k$~ЧЕТНО, a~$0\le s <q_k$,
СЛУЖИТ ТОЧКА~$\{s\theta\}$, А ПРАВЫМ---ТОЧКА~$\{(s+t)\theta\}^+$.
ыЕВЫМ КОНЦОМ ИНТЕРВАЛА НОМЕР~$s$ ДЛИНЫ~$1-\{t\theta\}$,
ГДЕ~$t=rq_k+q_{k-1}$, $0 \le r < a_k$, $k$~НЕЧЕТНО И~$0 \le s < q_k$,
СЛУЖИТ ТОЧКА~$\{(s+t)\theta\}$, А ПРАВЫМ---ТОЧКА~$\{s\theta\}^+$.
ыЮБОЕ НАТУРАЛЬНОЕ ЧИСЛО МОЖНО ЕДИНСТВЕННЫМ ОБРАЗОМ ПРЕДСТАВИТЬ В
ВИДЕ~$n=rq_k+q_{k-1}+s$ ПРИ~$k\ge 1$, $1 \le r \le a_k$, $0 \le s < q_k$.
т ЭТИХ ОБОЗНАЧЕНИЯХ ПЕРЕД ВСТАВКОЙ ТОЧКИ~$\{n\theta\}$ ИМЕЕТСЯ $n$~ИНТЕРВАЛОВ:
%%645
ПЕРВЫЕ $s$~ИНТЕРВАЛОВ (С НОМЕРАМИ~0,~\dots, $s-1$) ДЛИНЫ~$\{(-1)^k(rq_k+q_{k-1})\theta\}$;
ПЕРВЫЕ $n-q_k$~ИНТЕРВАЛОВ (С НОМЕРАМИ~0,~\dots, $n-q_k-1$) ДЛИНЫ~$\{(-1)^k q_k\theta\}$;
ПОСЛЕДНИЕ $q_k-s$~ИНТЕРВАЛОВ (С НОМЕРАМИ~$s$,~\dots, $q_k-1$) ДЛИНЫ~$\{(-1)^k((r-1)q_k+q_{k-1})\theta\}$.

юПЕРАЦИЯ ВСТАВКИ~$\{n\theta\}$ УСТРАНЯЕТ ИНТЕРВАЛ НОМЕР~$s$ ПОСЛЕДНЕГО
ТИПА И ПРЕОБРАЗУЕТ ЕГО В ИНТЕРВАЛ НОМЕР~$s$ ПЕРВОГО ТИПА И ИНТЕРВАЛ
НОМЕР~$n-q_k$ ВТОРОГО ТИПА.

\ex[M30] ЄЕОРЕМА~S УТВЕРЖДАЕТ, ЧТО ПРИ ПОСЛЕДОВАТЕЛЬНЫХ ВСТАВКАХ
ТОЧЕК~$\{\theta\}$, $\{2\theta\}$,~\dots В ИНТЕРВАЛ~$[0, 1]$ КАЖДАЯ НОВАЯ
ТОЧКА РАЗБИВАЕТ ОДИН ИЗ
НАИБОЛЬШИХ ИМЕЮЩИХСЯ ИНТЕРВАЛОВ. хСЛИ ИНТЕРВАЛ~$[a, c]$ РАЗБИТ ТАКИМ
ОБРАЭОМ НА ДВЕ
ЧАСТИ~$[a, b]$, $[b, c]$, МЫ НАЗОВЕМ ЭТО \dfn{ПЛОХИМ РАЗБИЕНИЕМ,} КОГДА
ОДНА ИЗ ЧАСТЕЙ БОЛЕЕ ЧЕМ ВДВОЕ ДЛИННЕЕ ДРУГОЙ, Т.~Е.~КОГДА $b-a>2(c-b)$
ИЛИ~$c-b>2(b-a)$.

фОКАЖИТЕ, ЧТО ЕСЛИ~$\theta\ne \phi^{-1}$ ИЛИ~$\theta\ne\phi^{-2}$, ТО ПРИ
НЕКОТОРОМ~$n$ ТОЧКА~$\{n\theta\}$ ДАЕТ ПЛОХОЕ РАЗБИЕНИЕ; ЕСЛИ
ЖЕ~$\theta=\phi^{-1}$ ИЛИ~$\theta=\phi^{-2}$, ТО ПЛОХИХ РАЗБИЕНИЙ НЕ ПОЛУЧАЕТСЯ.

\ex[ь43] (Ё.~уРЭХЕМ.) фОКАЖИТЕ ИЛИ ОПРОВЕРГНИТЕ СЛЕДУЮЩЕЕ
\emph{ПРЕДПОЛОЖЕНИЕ О $3d$~ДЛИНАХ:} ЕСЛИ~$\theta$, $\alpha_1$,~\dots,
$\alpha_d$--- ВЕЩЕСТВЕННЫЕ ЧИСЛА, ПРИЧЕМ~$\alpha_1=0$, ЕСЛИ~$n_1$,~\dots,
$n_d$---НАТУРАЛЬНЫЕ ЧИСЛА И ЕСЛИ ТОЧКИ~$\{n\theta+\alpha_i\}$ ВСТАВЛЯЮТСЯ В
ИНТЕРВАЛ~$[0, 1]$ ПРИ~$0\le n < n_i$, $1\le i\le d$, ТО
$n_1+\cdots+n_d$~ПОЛУЧАЮЩИХСЯ ИНТЕРВАЛОВ (ВОЗМОЖНО, ПУСТЫХ) ИМЕЮТ НЕ БОЛЕЕ
$3d$~РАЗЛИЧНЫХ ДЛИН.

\ex[16] юБЫЧНО УДАЧНЫЕ ПОИСКИ ПРОИЗВОДЯТСЯ ЧАЩЕ НЕУДАЧНЫХ ЁАЗУМНО ЛИ
СТРОКИ~12--13 ПРОГРАММЫ~C ПОМЕНЯТЬ МЕСТАМИ СО СТРОКАМИ~10--11?

\rex[21] яОКАЖИТЕ, ЧТО МОЖНО ТАК ПЕРЕПИСАТЬ ПРОГРАММУ~C, ЧТО ВО
ВНУТРЕННЕМ ЦИКЛЕ ОСТАНЕТСЯ ЛИШЬ ОДНА ИНСТРУКЦИЯ УСЛОВНОГО ПЕРЕХОДА.
ёРАВНИТЕ ВРЕМЕНА РАБОТЫ МОДИФИЦИРОВАННОЙ И ПЕРВОНАЧАЛЬНОЙ ПРОГРАММ.

\ex[24] \exhead(ёОКРАЩЕННЫЕ КЛЮЧИ.) яУСТЬ $h(K)$---ХЕШ-ФУНКЦИЯ, a
$g(K)$---ТАКАЯ ФУНКЦИЯ ОТ~$K$, ЧТО, ЗНАЯ~$h(K)$ И~$g(K)$, МОЖНО НАЙТИ~$K$.
эАПРИМЕР, ПРИ ХЕШИРОВАНИИ ДЕЛЕНИЕМ МОЖНО ПОЛОЖИТЬ~$h(K)=K \bmod M$
И~$g(K)=\floor{K/M}$; В МУЛЬТИПЛИКАТИВНОМ ХЕШИРОВАНИИ В КАЧЕСТВЕ~$h(K)$
МОЖНО ВЗЯТЬ СТАРШИЕ РАЗРЯДЫ~$(AK/w)\bmod 1$, А В КАЧЕСТВЕ~$g(K)$---ОСТАЛЬНЫЕ
РАЗРЯДЫ.

яОКАЖИТЕ, ЧТО ПРИ ИСПОЛЬЗОВАНИИ МЕТОДА ЦЕПОЧЕК БЕЗ НАЛОЖЕНИЯ В КАЖДОЙ
ЗАПИСИ ВМЕСТО~$K$ ДОСТАТОЧНО ХРАНИТЬ~$g(K)$. (¤ТО ИНОГДА ЭКОНОМИТ
ПРОСТРАНСТВО, НЕОБХОДИМОЕ ДЛЯ ПОЛЕЙ ССЫЛОК.) шЗМЕНИТЕ АЛГОРИТМ~C, ЧТОБЫ
ОН МОГ РАБОТАТЬ С ТАКИМИ СОКРАЩЕННЫМИ КЛЮЧАМИ, УСТРАНИВ НАЛОЖЕНИЕ СПИСКОВ,
 НО НЕ ИСПОЛЬЗУЯ ВСПОМОГАТЕЛЬНЫХ ЯЧЕЕК ПАМЯТИ ДЛЯ "ПЕРЕПОЛНЯЮЩИХ" ЗАПИСЕЙ.

\ex[24] (¤.~¤ЛЬКОК.) яОКАЖИТЕ, ЧТО БОЛЬШАЯ РАССЕЯННАЯ ТАБЛИЦА
МОЖЕТ ИСПОЛЬЗОВАТЬ ОБЩУЮ С ДРУГИМИ СВЯЗАННЫМИ СПИСКАМИ ПАМЯТЬ. яУСТЬ
КАЖДОЕ СЛОВО СПИСОЧНОЙ ПАМЯТИ СОДЕРЖИТ ДВУХБИТОВОЕ ПОЛЕ~|TAG|, ИМЕЮЩЕЕ
СЛЕДУЮЩИЙ СМЫСЛ:
{\medskip\narrower
\item{$|TAG|(|P|)=0$} ОБОЗНАЧАЕТ СЛОВО В СПИСКЕ СВОБОДНОГО ПРОСТРАНСТВА;
$|LINK|(|P|)$~УКАЗЫВАЕТ НА СЛЕДУЮЩЕЕ СВОБОДНОЕ СЛОВО.
%
\item{$|TAG|(|P|)=1$} ОБОЗНАЧАЕТ ИСПОЛЬЗУЕМОЕ СЛОВО, НЕ ЯВЛЯЮЩЕЕСЯ ЧАСТЬЮ
РАССЕЯННОЙ ТАБЛИЦЫ; ФОРМАТ ОСТАЛЬНЫХ ПОЛЕЙ ЭТОГО СЛОВА ПРОИЗВОЛЕН.
%
\item{$|TAG|(|P|)=2$} ОБОЗНАЧАЕТ СЛОВО В РАССЕЯННОЙ ТАБЛИЦЕ;
$|LINK|(|P|)$~УКАЗЫВАЕТ НА ДРУГОЕ СЛОВО. тСЯКИЙ РАЗ, КОГДА ПРИ ОБРАБОТКЕ
СПИСКА, НЕ ЯВЛЯЮЩЕГОСЯ ЧАСТЬЮ РАССЕЯННОЙ ТАБЛИЦЫ, МЫ ДОСТИГАЕМ СЛОВА
С~$|TAG|(|P|)=2$, НУЖНО УСТАНОВИТЬ~$P\asg|LINK|(|P|)$ ДО ПОЛУЧЕНИЯ СЛОВА
С~$|TAG|(|P|)\le 1$. (фЛЯ ЭФФЕКТИВНОСТИ МОЖНО ИЗМЕНИТЬ ОДНУ ИЗ
ПРЕДШЕСТВУЮЩИХ ССЫЛОК; ТОГДА НЕ ПРИДЕТСЯ СНОВА И СНОВА ПЕРЕСКАКИВАТЬ ЧЕРЕЗ
ОДНИ И ТЕ ЖЕ ЭЛЕМЕНТЫ РАССЕЯННОЙ ТАБЛИЦЫ.)
\medskip}

яОКАЖИТЕ, КАК ОПРЕДЕЛИТЬ ПОДХОДЯЩИЕ АЛГОРИТМЫ ДЛЯ ВСТАВКИ И ВЫБОРКИ КЛЮЧЕЙ
ИЗ ТАКОЙ КОМБИНИРОВАННОЙ ТАБЛИЦЫ, ПРЕДПОЛАГАЯ, ЧТО В СЛОВЕ
С~$|TAG|(|P|)=2$ ИМЕЕТСЯ ЕЩЕ ОДНО ПОЛЕ ССЫЛКИ~$|AUX|(|P|)$.

\ex[16] яОЧЕМУ В АЛГОРИТМАХ~L И~D РАЗУМНО ФИКСИРОВАТЬ
ПЕРЕПОЛНЕНИЕ ПРИ~$N=M-1$, А НЕ ПРИ~$N=M$?
%%646

\ex[10] т ПРОГРАММЕ~L ГОВОРИТСЯ, ЧТО $K$~НЕ ДОЛЖНО РАВНЯТЬСЯ~0. р ВДРУГ НА
САМОМ ДЕЛЕ ОНА РАБОТАЕТ ДАЖЕ ПРИ~$K=0$?

\ex[15] яОЧЕМУ НЕ ПОЛОЖИТЬ ПРОСТО~$h_2(K)=h_1(K)$ В~(25), ЕСЛИ~$h_1(K)\ne0$?

\rex[21] фЕЙСТВИТЕЛЬНО ЛИ~(31) ПРЕДПОЧТИТЕЛЬНЕЕ~(30) В КАЧЕСТВЕ
ЗАМЕНЫ СТРОК~10--13 ПРОГРАММЫ~D? фАЙТЕ ОТВЕТ, ИСХОДЯ ИЗ СРЕДНИХ
ЗНАЧЕНИЙ~$A$, $S1$ И~$C$.

\ex[40] яРОВЕРЬТЕ ЭМПИРИЧЕСКИ ВОЗДЕЙСТВИЕ ОГРАНИЧЕНИЯ ОБЛАСТИ
ЗНАЧЕНИЙ~$h_2(K)$ В АЛГОРИТМЕ~D ТАК, ЧТО: (a)~$1\le h_2(K)\le r$ ПРИ~$r=1$,
 2, 3,~\dots, 10;
(b)~$1\le h_2(K)\le\rho M$ ПРИ $\rho={1\over10}$, ${2\over10}$,
${3\over10}$,~\dots, ${9\over10}$.

\ex[ь25] (Ё.~ъРУТАР.) шЗМЕНИТЕ АЛГОРИТМ~D СЛЕДУЮЩИМ ОБРАЗОМ, УСТРАНЯЯ
ХЕШ-ФУНКЦИЮ~$h_2(K)$: В ШАГЕ~D3 УСТАНОВИТЬ~$c\asg 0$, А В НАЧАЛЕ
ШАГА~D4 УСТАНОВИТЬ~$c\asg c+1$. фОКАЖИТЕ, ЧТО, ЕСЛИ~$M=2^m$,
СООТВЕТСТВУЮЩАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ ПРОБ~$h_1(K)$, $(h_1(K)-1)\bmod M$,
~\dots, $\left(h_1(K)-\perm{M}{2}\right)\bmod M$ БУДЕТ
ПЕРЕСТАНОВКОЙ МНОЖЕСТВА~$\set{0, 1,~\dots, M-1}$. ъАК ЭТОТ МЕТОД, БУДУЧИ
ЗАПРОГРАММИРОВАННЫМ ДЛЯ МАШИНЫ~\MIX, ВЫГЛЯДИТ ПО СРАВНЕНИЮ С ТРЕМЯ
ПРОГРАММАМИ, РАССМАТРИВАЕМЫМИ НА РИС.~42, ЕСЛИ ПОВЕДЕНИЕ АНАЛОГИЧНО
СЛУЧАЙНОМУ ОПРОБОВАНИЮ СО ВТОРИЧНЫМ ОКУЧИВАНИЕМ?

\rex[20] яРЕДПОЛОЖИМ, ЧТО МЫ ХОТЕЛИ БЫ УДАЛИТЬ ЗАПИСЬ ИЗ ТАБЛИЦЫ,
 ПОСТРОЕННОЙ С ПОМОЩЬЮ АЛГОРИТМА~D, ПОМЕЧАЯ СООТВЕТСТВУЮЩУЮ ПОЗИЦИЮ
КАК УДАЛЕННУЮ. ёЛЕДУЕТ ЛИ ПРИ ЭТОМ УМЕНЬШАТЬ ЗНАЧЕНИЕ ПЕРЕМЕННОЙ~$N$,
УПРАВЛЯЮЩЕЙ АЛГОРИТМОМ~D?

\ex[27] фОКАЖИТЕ, ЧТО АЛГОРИТМ~R ОСТАВЛЯЕТ ТАБЛИЦУ ТОЧНО В ТАКОМ ЖЕ ВИДЕ,
КАК ЕСЛИ БЫ $|KEY|[i]$ НЕ БЫЛ СПЕРВА ВСТАВЛЕН.

\rex[23] яРИДУМАЙТЕ АЛГОРИТМ, АНАЛОГИЧНЫЙ АЛГОРИТМУ~R, ДЛЯ
УДАЛЕНИЯ ЭЛЕМЕНТОВ ИЗ РАССЕЯННОЙ ТАБЛИЦЫ ЦЕПОЧЕК, ПОСТРОЕННОЙ С ПОМОЩЬЮ
АЛГОРИТМА~C.

\ex[ь20] яРЕДПОЛОЖИМ, ЧТО МНОЖЕСТВО ВСЕХ ВОЗМОЖНЫХ КЛЮЧЕЙ СОСТОИТ ИЗ
$MP$~ЭЛЕМЕНТОВ, ПРИЧЕМ РОВНО $P$~КЛЮЧЕЙ ИМЕЮТ ДАННЫЙ ХЕШ-АДРЕС. (т
РЕАЛЬНЫХ СЛУЧАЯХ $P$~ОЧЕНЬ ВЕЛИКО; НАПРИМЕР, ЕСЛИ КЛЮЧАМИ ЯВЛЯЮТСЯ
ПРОИЗВОЛЬНЫЕ ДЕСЯТИЗНАЧНЫЕ ЧИСЛА, А~$M=10^3$, ТО~$P=10^7$.) яРЕДПОЛОЖИМ,
ЧТО~$M\ge7$ И~$N=7$. яУСТЬ ИЗ МНОЖЕСТВА ВСЕХ ВОЗМОЖНЫХ КЛЮЧЕЙ СЛУЧАЙНЫМ
ОБРАЗОМ ВЫБИРАЮТСЯ СЕМЬ РАЗЛИЧНЫХ ЭЛЕМЕНТОВ. тЫРАЗИТЕ ЧЕРЕЗ~$M$ И~$P$
ТОЧНУЮ ВЕРОЯТНОСТЬ ПОЛУЧЕНИЯ ХЕШ-ПОСЛЕДОВАТЕЛЬНОСТИ 1~2~6~2~1~6~1
(Т.~Е.~$h(K_1)=1$, $h(K_2)=2$,~\dots, $h(K_7)=1$).

\ex[M19] юБоЯСНИТЕ, ПОЧЕМУ ВЕРНА ФОРМУЛА~(39).

\ex[M20] ёКОЛЬКО ХЕШ-ПОСЛЕДОВАТЕЛЬНОСТЕЙ $a_1\ a_2~\ldots a_9$ ПРИ
ИСПОЛЬЗОВАНИИ ЛИНЕЙНОГО ОПРОБОВАНИЯ ДАДУТ КАРТИНУ ЗАНЯТЫХ ЯЧЕЕК~(21)?

\ex[ь27] чАВЕРШИТЕ ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ~K. [\emph{єКАЗАНИЕ:} ПУСТЬ
$$
s(n,x,y)=\sum_{k\ge0}\perm{n}{k}(x+k)^{k+1}(y-k)^{n-k-1}(y-n);
$$
ИСПОЛЬЗУЙТЕ БИНОМИАЛЬНУЮ ТЕОРЕМУ рБЕЛЯ [ФОРМУЛА~(1.2.6-16)] ДЛЯ
ДОКАЗАТЕЛЬСТВА ТОГО, ЧТО~$s(n, x, y)=x(x+y)^n+ns(n-1, x+1, y-1)$]

\ex[M30] т ТЕ ДАВНИЕ ВРЕМЕНА, КОГДА ¤ть БЫЛИ ГОРАЗДО МЕДЛЕННЕЕ НЫНЕШНИХ,
ПО МИГАНИЮ ЛАМПОЧЕК МОЖНО БЫЛО СУДИТЬ, С КАКОЙ СКОРОСТЬЮ РАБОТАЕТ
АЛГОРИТМ~L. ъОГДА ТАБЛИЦА СТАНОВИЛАСЬ ПОЧТИ ПОЛНОЙ, ОДНИ
ЭЛЕМЕНТЫ ОБРАБАТЫВАЛИСЬ ОЧЕНЬ БЫСТРО, А ДРУГИЕ ВЕСЬМА МЕДЛЕННО.

¤ТИ НАБЛЮДЕНИЯ НАВОДЯТ НА МЫСЛЬ О ТОМ, ЧТО, ЕСЛИ ИСПОЛЬЗУЕТСЯ ЛИНЕЙНОЕ
ОПРОБОВАНИЕ, СРЕДНЕКВАДРАТИЧНОЕ ОТКЛОНЕНИЕ ВЕЛИЧИНЫ~$C'_N$ ДОВОЛЬНО
ВЕЛИКО. эАЙДИТЕ ФОРМУЛУ, ВЫРАЖАЮЩУЮ ДИСПЕРСИЮ ЧЕРЕЗ ФУНКЦИИ~$Q_r$,
ОПРЕДЕЛЕННЫЕ В ТЕОРЕМЕ~K, И ОЦЕНИТЕ ЕЕ ПРИ~$N=\alpha M$ И~$M\to\infty$.

\ex[M21] \exhead(чАДАЧА О СТОЯНКЕ.) эА НЕКОЙ УЛИЦЕ С ОДНОСТОРОННИМ
ДВИЖЕНИЕМ ИМЕЕТСЯ $m$~МЕСТ ДЛЯ СТОЯНКИ, РАСПОЛОЖЕННЫХ В РЯД И
ПЕРЕНУМЕРОВАННЫХ ОТ~1 ДО~$m$. ьУЖ ВЕЗЕТ В АВТОМОБИЛЕ СВОЮ ДРЕМЛЮЩУЮ ЖЕНУ.
тНЕЗАПНО ЖЕНА ПРОСЫПАЕТСЯ И ТРЕБУЕТ НЕМЕДЛЕННО ОСТАНОВИТЬСЯ. юН ПОСЛУШНО
ОСТАНАВЛИВАЕТСЯ
%%647
НА ПЕРВОМ СВОБОДНОМ МЕСТЕ, НО ЕСЛИ НЕТ СВОБОДНЫХ МЕСТ, К КОТОРЫМ
МОЖНО ПОДоЕХАТЬ, НЕ ПОВОРАЧИВАЯ ОБРАТНО (Т.~Е.~ЕСЛИ ЖЕНА ПРОСНУЛАСЬ, КОГДА
МАШИНА ДОСТИГЛА $k\hbox{-ГО}$~МЕСТА ДЛЯ СТОЯНКИ, НО ВСЕ "ПОЗИЦИИ"~$k$,
$k+1$,~\dots, $m$ ЗАНЯТЫ), МУЖ ПРИНОСИТ СВОИ ИЗВИНЕНИЯ И ЕДЕТ ДАЛЬШЕ

яРЕДПОЛОЖИМ, ЧТО ЭТО ПРОИСХОДИТ С $n$~РАЗЛИЧНЫМИ МАШИНАМИ, ПРИЧЕМ
$j-\hbox{Я}$~ЖЕНА ПРОСЫПАЕТСЯ В МОМЕНТ, КОГДА МАШИНА НАХОДИТСЯ ПЕРЕД
МЕСТОМ~$a_j$. ёКОЛЬКО ИМЕЕТСЯ ТАКИХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ~$a_1$~\dots{}$a_n$,
 ПРИ КОТОРЫХ ВСЕ МАШИНЫ УДАЧНО ПРИПАРКУЮТСЯ, ПРЕДПОЛАГАЯ, ЧТО
ПЕРВОНАЧАЛЬНО УЛИЦА ПУСТА И НИКТО СО СТОЯНКИ НЕ УЕЗЖАЕТ? эАПРИМЕР,
ЕСЛИ~$m=n=9$
И~$a_1\ldots{}a_9=3\ 1\ 4\ 1\ 5\ 9\ 2\ 6\ 5$, АВТОМОБИЛИ РАСПОЛОЖАТСЯ
СЛЕДУЮЩИМ ОБРАЗОМ:
\picture{ЁИС. СТР. 647}
[єКАЗАНИЕ: ВОСПОЛЬЗУЙТЕСЬ АНАЛИЗОМ ЛИНЕЙНОГО ОПРОБОВАНИЯ.]

\ex[ь28] (фЖОН~ЁИОРДАН.) яОКАЖИТЕ, ЧТО В ЗАДАЧЕ О СТОЯНКЕ ИЗ
УПР.~29 ПРИ~$n=m$ ВСЕ МАШИНЫ ПРИПАРКУЮТСЯ ТОГДА И ТОЛЬКО ТОГДА, КОГДА
СУЩЕСТВУЕТ ПЕРЕСТАНОВКА~$p_1$ $p_2$~\dots{} $p_n$ МНОЖЕСТВА~$\set{1, 2,
~\ldots, П}$, ТАКАЯ,
ЧТО~$a_j\le p_j$ ДЛЯ ВСЕХ~$j$.

\ex[ь40] хСЛИ В ЗАДАЧЕ О СТОЯНКЕ (УПР.~29) $n=m$, ЧИСЛО РЕШЕНИЙ
ОКАЗЫВАЕТСЯ РАВНЫМ~$(n+1)^{n-1}$, А ИЗ УПР.~2.3.4.4-22 МЫ ЗНАЕМ, ЧТО ЭТО
ЕСТЬ ЧИСЛО СВОБОДНЫХ, ДЕРЕВЬЕВ НАД~$n+1$~РАЗЛИЧНЫМИ ВЕРШИНАМИ! эАЙДИТЕ
ИНТЕРЕСНУЮ ЗАВИСИМОСТЬ МЕЖДУ ПОСЛЕДОВАТЕЛЬНОСТЯМИ ОСТАНОВОК И ДЕРЕВЬЯМИ.

\ex[ь26] фОКАЖИТЕ, ЧТО СИСТЕМА УРАВНЕНИЙ~(44) ИМЕЕТ ЕДИНСТВЕННОЕ
РЕШЕНИЕ~$(C_0, C_1,~\ldots, C_{M-1})$ ПРИ ЛЮБЫХ ЦЕЛЫХ
НЕОТРИЦАТЕЛЬНЫХ~$b_0$, $b_1$,~\dots, $b_{M-1}$, СУММА КОТОРЫХ МЕНЬШЕ~$M$.
яОСТРОЙТЕ АЛГОРИТМ ДЛЯ НАХОЖДЕНИЯ ЭТОГО РЕШЕНИЯ.

\ex[ь23] юБоЯСНИТЕ, ПОЧЕМУ~(51) ВСЕГО ЛИШЬ ПРИБЛИЖЕНИЕ К
ИСТИННОМУ СРЕДНЕМУ ЧИСЛУ ПРОБ, ПРОИЗВОДИМЫХ АЛГОРИТМОМ~L. [ъАКИЕ
НЕСТРОГОСТИ БЫЛИ ДОПУЩЕНЫ ПРИ ВЫВОДЕ~(51)?]

\ex[ь22] ЎЕЛЬ ЭТОГО УПРАЖНЕНИЯ---ИССЛЕДОВАТЬ СРЕДНЕЕ, ЧИСЛО ПРОБ В
РАССЕЯННОЙ ТАБЛИЦЕ ЦЕПОЧЕК, КОГДА СПИСКИ ОСТАЮТСЯ РАЗДЕЛЬНЫМИ, КАК НА
РИС~38.
(a)~ўЕМУ РАВНА ВЕРОЯТНОСТЬ~$P_{Nk}$ ТОГО, ЧТО ДАННЫЙ СПИСОК ИМЕЕТ
ДЛИНУ~$k$, ЕСЛИ $M^N$~ХЕШ-ПОСЛЕДОВАТЕЛЬНОСТЕЙ~(35) РАВНОВЕРОЯТНЫ?
(b)~эАЙДИТЕ ПРОИЗВОДЯЩУЮ ФУНКЦИЮ~$P_N(z)\sum_{k\ge0} P_{Nk} z^k$.
(c)~тЫРАЗИТЕ ЧЕРЕЗ ЭТУ ПРОИЗВОДЯЩУЮ ФУНКЦИЮ
СРЕДНЕЕ ЧИСЛО ПРОБ ПРИ УДАЧНОМ И НЕУДАЧНОМ ПОИСКЕ. (яРЕДПОЛАГАЕТСЯ,
ЧТО НЕУДАЧНЫЙ ПОИСК В СПИСКЕ ДЛИНЫ~$k$ ТРЕБУЕТ $k+\delta_{k0}$~ПРОБ.)

\ex[ь21] (яРОДОЛЖЕНИЕ УПР.~34.) эАЙДИТЕ СРЕДНЕЕ ЧИСЛО ПРОБ ПРИ НЕУДАЧНОМ
ПОИСКЕ, ЕСЛИ ОТДЕЛЬНЫЕ СПИСКИ УПОРЯДОЧЕНЫ ПО ЗНАЧЕНИЯМ КЛЮЧЕЙ.

\ex[ь22] эАЙДИТЕ ДИСПЕРСИЮ ЧИСЛА ПРОБ ДЛЯ МЕТОДА РАЗДЕЛЬНЫХ ЦЕПОЧЕК, ЕСЛИ
ПОИСК БЫЛ НЕУДАЧНЫМ. (ёМ.~(18).)

\rex[ь29] эАЙДИТЕ ДИСПЕРСИЮ ЧИСЛА ПРОБ ДЛЯ МЕТОДА РАЗДЕЛЬНЫХ ЦЕПОЧЕК, ЕСЛИ
ПОИСК БЫЛ УДАЧНЫМ. (ёМ.~(19).)

\ex[ь32] \exhead(шСПОЛЬЗОВАНИЕ ДЕРЕВЬЕВ ПРИ ХЕШИРОВАНИИ.) шСКУСНЫЙ
ПРОГРАММИСТ МОГ БЫ ПОПЫТАТЬСЯ ИСПОЛЬЗОВАТЬ В МЕТОДЕ ЦЕПОЧЕК БИНАРНЫЕ
ДЕРЕВЬЯ ПОИСКА ВМЕСТО ЛИНЕЙНЫХ СПИСКОВ, КОМБИНИРУЯ ТАКИМ ОБРАЗОМ
АЛГОРИТМ~6.2.2Є
С ХЕШИРОВАНИЕМ. яРОАНАЛИЗИРУЙТЕ СРЕДНЕЕ ЧИСЛО ПРОБ, НУЖНЫХ ЭТОМУ
КОМБИНИРОВАННОМУ АЛГОРИТМУ И В СЛУЧАЕ УДАЧНОГО, И В СЛУЧАЕ НЕУДАЧНОГО
ПОИСКА. [\emph{єКАЗАНИЕ:} СР.~С ФОРМУЛОЙ~(5.2.1-11).]

\ex[M30] ЎЕЛЬ ЭТОГО УПРАЖНЕНИЯ---ПРОАНАЛИЗИРОВАТЬ СРЕДНЕЕ ЧИСЛО ПРОБ В
АЛГОРИТМЕ~C (СРАСТАЮЩИЕСЯ ЦЕПОЧКИ). юБОЗНАЧИМ ЧЕРЕЗ~$c(k_1, k_2, k_3,
~\dots)$ КОЛИЧЕСТВО ХЕШ-ПОСЛЕДОВАТЕЛЬНОСТЕЙ~(35), ЗАСТАВЛЯЮЩИХ АЛГОРИТМ~C
ОБРАЗОВАТЬ РОВНО $k_1$~СПИСКОВ ДЛИНЫ~1, $k_2$~СПИСКОВ ДЛИНЫ~2 И Т.~Д.;
$k_1+2k_2+3k_3+\ldots=N$.  эАЙДИТЕ РЕКУРРЕНТНОЕ СООТНОШЕНИЕ, ОПРЕДЕЛЯЮЩЕЕ
ЭТИ ЧИСЛА, И ИСПОЛЬЗУЙТЕ
%%648
ЕГО ПРИ ВЫВОДЕ ПРОСТОЙ ФОРМУЛЫ ДЛЯ СУММЫ
$$
S_N=\sum_{\scriptstyle j\ge 1\atop \scriptstyle k_1+k_2+\ldots=N}k_jc(k_1,
k_2, \ldots).
$$

ъАК СВЯЗАНА ВЕЛИЧИНА $S_N$ С ЧИСЛОМ ПРОБ ВО ВРЕМЯ НЕУДАЧНОГО ПОИСКА С
ИСПОЛЬЗОВАНИЕМ АЛГОРИТМА~C?

\ex[M33] эАЙДИТЕ ДИСПЕРСИЮ ЧИСЛА ПРОБ, ПРОИЗВОДИМЫХ В АЛГОРИТМЕ~C,  ЕСЛИ
ПОИСК БЫЛ НЕУДАЧНЫМ (СМ.~(15).)

\ex[ь40] яРОАНАЛИЗИРУЙТЕ, СКОЛЬКО РАЗ В СРЕДНЕМ |R|~УМЕНЬШАЕТСЯ НА~1 ПРИ
ВСТАВКЕ $(N+1)\hbox{-ГО}$~ЭЛЕМЕНТА С ПОМОЩЬЮ АЛГОРИТМА~C. (юБОЗНАЧИМ ЭТО ЧИСЛО
ЧЕРЕЗ~$T_N$.)

\ex[ь20] тЫВЕДИТЕ~(17).

\ex[ь42] яРОАНАЛИЗИРУЙТЕ МОДИФИКАЦИЮ АЛГОРИТМА~C, ИСПОЛЬЗУЮЩУЮ ТАБЛИЦУ
РАЗМЕРА~$M'\ge M$. фЛЯ ХЕШИРОВАНИЯ ИСПОЛЬЗУЮТСЯ ЛИШЬ ПЕРВЫЕ~$M$ ПОЗИЦИЙ,
ТАК ЧТО ПЕРВЫЕ $M'-M$~СВОБОДНЫХ УЗЛОВ, НАЙДЕННЫХ В ШАГЕ~C5, РАСПОЛОЖАТСЯ В
ДОПОЛНИТЕЛЬНОЙ ЧАСТИ ТАБЛИЦЫ. ъАКОЙ ВЫБОР~$M$ ПРИ ФИКСИРОВАННОМ~$M'$,
$1\le M \le M'$, ДАЕТ НАИЛУЧШИЕ ХАРАКТЕРИСТИКИ?

\ex[ь43] \exhead(ёЛУЧАЙНОЕ ОПРОБОВАНИЕ С ВТОРИЧНЫМ СКУЧИВАНИЕМ.) ЎЕЛЬ
ЭТОГО  УПРАЖНЕНИЯ---ОПРЕДЕЛИТЬ СРЕДНЕЕ ЧИСЛО ПРОБ В СХЕМЕ ОТКРЫТОЙ АДРЕСАЦИЙ
 С ПОСЛЕДОВАТЕЛЬНОСТЬЮ ОПРОБОВАНИЙ
$$
h(K), (h(K)+p_1)\bmod M, (h(K)+p_2)\bmod M, \ldots, (h(K)+p_{M-1})\bmod M,
$$
ГДЕ $p_1$ $p_2$~\dots $p_{M-1}$---СЛУЧАЙНО-ВЫБРАННАЯ ПЕРЕСТАНОВКА
МНОЖЕСТВА~$\set{1, 2,~\ldots, M-1}$, ЗАВИСЯЩАЯ ОТ~$h(K)$. шНЫМИ СЛОВАМИ, У
ВСЕХ КЛЮЧЕЙ С ОДИНАКОВЫМ ЗНАЧЕНИЕМ~$h(K)$ ОДНА И ТА ЖЕ ПОСЛЕДОВАТЕЛЬНОСТЬ
ОПРОБОВАНИЙ, А $(M-1)!^M$~ВОЗМОЖНЫХ ВЫБОРОВ $M$~ПОСЛЕДОВАТЕЛЬНОСТЕЙ ПРОБ С
ЭТИМ СВОЙСТВОМ РАВНОВЕРОЯТНЫ.

ьОЖНО ТОЧНО СМОДЕЛИРОВАТЬ СИТУАЦИЮ, ЕСЛИ НАД ПЕРВОНАЧАЛЬНО ПУСТЫМ
 ЛИНЕЙНЫМ МАССИВОМ РАЗМЕРА~$m$ ВЫПОЛНИТЬ СЛЕДУЮЩУЮ ПРОЦЕДУРУ. фЕЛАЕМ
$n$~РАЗ  ТАКУЮ ОПЕРАЦИЮ:
{\medskip\narrower

ё ВЕРОЯТНОСТЬЮ~$p$ ЗАЙМЕМ КРАЙНЮЮ ЛЕВУЮ СВОБОДНУЮ ПОЗИЦИЮ. т ПРОТИВНОМ
СЛУЧАЕ (Т.~Е.\ С~ВЕРОЯТНОСТЬЮ~$q=1-p$) ВЫБЕРЕМ ЛЮБУЮ ПОЗИЦИЮ ТАБЛИЦЫ,
КРОМЕ КРАЙНЕЙ ЛЕВОЙ, ПРИЧЕМ ВСЕ $m-1$~ПОЗИЦИЙ РАВНОВЕРОЯТНЫ. хСЛИ
ВЫБРАННАЯ ПОЗИЦИЯ СВОБОДНА, ЗАЙМЕМ ЕЕ; В ПРОТИВНОМ СЛУЧАЕ ВЫБЕРЕМ
\emph{ЛЮБУЮ} СВОБОДНУЮ ПОЗИЦИЮ (ВКЛЮЧАЯ САМУЮ ЛЕВУЮ) И ЗАЙМЕМ ЕЕ, СЧИТАЯ,
 ЧТО ВСЕ СВОБОДНЫЕ ПОЗИЦИИ РАВНОВЕРОЯТНЫ.
\medskip}
эАПРИМЕР, ЕСЛИ~$m=5$ И~$n=3$, ТО ПОСЛЕ ВЫПОЛНЕНИЯ ОПИСАННОЙ
ПРОЦЕДУРЫ КОНФИГУРАЦИЯ (ЗАНЯТО, ЗАНЯТО, СВОБОДНО, ЗАНЯТО, СВОБОДНО)
ПОЛУЧАЕТСЯ С ВЕРОЯТНОСТЬЮ
$$
{7\over 192}qqq+{1\over6}pqq+{1\over6}qpq+{11\over64}qqp+{1\over3}ppq+{1\over4}pqp+{1\over4}qpp.
$$
(¤ТА ПРОЦЕДУРА СООТВЕТСТВУЕТ СЛУЧАЙНОМУ ОПРОБОВАНИЮ С ВТОРИЧНЫМ
СКУЧИВАНИЕМ, КОГДА~$p=1/m$, ИБО МОЖНО ПЕРЕНУМЕРОВАТЬ ЭЛЕМЕНТЫ ТАБЛИЦЫ ТАК,
ЧТО НЕКОТОРАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ ПРОБ СОВПАДЕТ С~0, 1, 2,~\dots, А ВСЕ
ОСТАЛЬНЫЕ БУДУТ СЛУЧАЙНЫМИ.)

эАЙДИТЕ ФОРМУЛУ ДЛЯ СРЕДНЕГО ЧИСЛА ЗАНЯТЫХ ПОЗИЦИЙ В ЛЕВОМ КОНЦЕ МАССИВА
(ДВЕ В ПРИВЕДЕННОМ ПРИМЕРЕ). юПРЕДЕЛИТЕ ТАКЖЕ АСИМПТОТИЧЕСКОЕ ЗНАЧЕНИЕ
ЭТОЙ ВЕЛИЧИНЫ ПРИ~$p=1/m$, $n=\alpha(m+1)$, $m\to\infty$.

\ex[ь43] ЁЕШИТЕ АНАЛОГ УПР.~44 С \emph{ТРЕТИЧНЫМ СКУЧИВАНИЕМ,} КОГДА
ПОСЛЕДОВАТЕЛЬНОСТЬ ПРОБ НАЧИНАЕТСЯ С~$h_1(K)$, $(h_1(K)+h_2(K))\bmod M$;
ВЫБОР ДАЛЬНЕЙШИХ ПРОБ СЛУЧАЕН И ЗАВИСИТ ЛИШЬ ОТ~$h_1(K)$ И~$h_2(K)$
(Т.~Е.~$(M-2)!^{M(M-1)}$ ВОЗМОЖНЫХ ВЫБОРОВ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ПРОБ С ЭТИМ
СВОЙСТВОМ СЧИТАЮТСЯ
%%649
РАВНОВЕРОЯТНЫМИ). ▀ВЛЯЕТСЯ ЛИ ПРЕДЛАГАЕМАЯ ПРОЦЕДУРА АСИМПТОТИЧЕСКИ
ЭКВИВАЛЕНТНОЙ РАВНОМЕРНОМУ ОПРОБОВАНИЮ?

\ex[M42] эАЙДИТЕ~$C'_N$ И~$C_N$ ДЛЯ МЕТОДА ОТКРЫТОЙ АДРЕСАЦИИ,
ИСПОЛЬЗУЮЩЕГО ПОСЛЕДОВАТЕЛЬНОСТЬ ПРОБ
$$
h(K), 0, 1, \ldots, h(K-1), h(K)+1, \ldots, M-1.
$$
\ex[M25] ъАКОЕ СРЕДНЕЕ ЧИСЛО ПРОБ ПОТРЕБУЕТСЯ ДЛЯ ОТКРЫТОЙ АДРЕСАЦИИ С
ПОСЛЕДОВАТЕЛЬНОСТЬЮ ПРОБ
$$
h(K), h(K)-1, h(K)+1, h(K)-2, h(K)+2,\ldots\,?
$$
¤ТА ПОСЛЕДОВАТЕЛЬНОСТЬ БЫЛА ОДНАЖДЫ ПРЕДЛОЖЕНА ИЗ-ЗА ТОГО, ЧТО ВСЕ
РАССТОЯНИЯ МЕЖДУ ПОСЛЕДОВАТЕЛЬНЫМИ ПРОБАМИ ПРИ ЧЕТНОМ~$M$ РАЗЛИЧНЫ
[\emph{єКАЗАНИЕ: НЕБОЛЬШАЯ  ХИТРОСТЬ СУЩЕСТВЕННО ОБЛЕГЧИТ ЗАДАЧУ.}]

\rex[M21] фАНА БЕСКОНЕЧНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ ВЗАИМНО НЕЗАВИСИМЫХ
 СЛУЧАЙНЫХ ХЕШ-ФУНКЦИЙ~$h_n(K)$. яРОАНАЛИЗИРУЙТЕ МЕТОД ОТКРЫТОЙ АДРЕСАЦИИ,
В КОТОРОМ ПРОБУЮТСЯ ПОЗИЦИИ~$h_1(K)$, $h_2(K)$, $h_3(K)$,~$\ldots\,$.
чАМЕТЬТЕ, ЧТО ВОЗМОЖНО ПОВТОРНОЕ ОПРОБОВАНИЕ ОДНОЙ И ТОЙ ЖЕ ПОЗИЦИИ,
НАПРИМЕР ЕСЛИ~$h_1(K)=h_2(K)$, НО ЭТО ВЕСЬМА МАЛОВЕРОЯТНО.

\ex[ть24] юБОБЩИВ УПР.~34 НА СЛУЧАЙ $b$~ЗАПИСЕЙ В БЛОКЕ, ОПРЕДЕЛИТЕ
СРЕДНЕЕ ЧИСЛО ПРОБ (Т.~Е.~ОБРАЩЕНИЙ К ФАЙЛУ) $C_N$ И~$C'_N$ ПРИ
ИСПОЛЬЗОВАНИИ РАЗДЕЛЬНЫХ ЦЕПОЧЕК, ПРЕДПОЛАГАЯ, ЧТО НЕУДАЧНЫЙ ПОИСК В
СПИСКЕ ИЗ $k$~ЭЛЕМЕНТОВ ТРЕБУЕТ~$\min(1, k-b+1)$~ПРОБ. тМЕСТО ТОЧНЫХ
ВЕРОЯТНОСТЕЙ~$P_{Nk}$ ИЗ УПР.~34 ВОСПОЛЬЗУЙТЕСЬ \dfn{ПРИБЛИЖЕНИЕМ яУАССОНА}
$$
\eqalign{
\perm{N}{k}\left({1\over M}\right)^k \left(1-{1\over M}\right)^{N-k}
&={N\over M}{N-1\over M}\ldots{N-k+1\over M}\left(1-{1\over M}\right)^N
\left(1-{1\over M}\right)^{-k}{1\over k!}=\cr
&=e^{-\rho}\rho^k/k!+O(M^{-1}),\cr
}
$$
СПРАВЕДЛИВЫМ ПРИ~$N=\rho M$, $M\to\infty$.

\ex[M20] яОКАЖИТЕ, ЧТО В ОБОЗНАЧЕНИЯХ~(42) $Q_1(M, N)=M-(M-N-1)Q_0(M, N)$.
[\emph{єКАЗАНИЕ:} ДОКАЖИТЕ СНАЧАЛА, ЧТО $Q_1(M, N)=(N+1)Q_0(M, N)-NQ_0(M, N-1)$.]

\ex[BM16] тЫРАЗИТЕ ФУНКЦИЮ~$R(\alpha, n)$, ОПРЕДЕЛЕННУЮ В~(55), ЧЕРЕЗ
ФУНКЦИЮ~$Q_0$, ОПРЕДЕЛЕННУЮ В~(42).

\ex[ть20] фОКАЖИТЕ, ЧТО~$Q_0(M,N)=\int_0^\infty e^{-t}(1+t/M)^N\,dt.$

\ex[ть20] фОКАЖИТЕ, ЧТО ФУНКЦИЮ~$R(\alpha, n)$ МОЖНО ВЫРАЗИТЬ ЧЕРЕЗ
НЕПОЛНУЮ ГАММА-ФУНКЦИЮ, И ИСПОЛЬЗУЙТЕ РЕЗУЛЬТАТ УПР.~1.2.11.3-9 ДЛЯ
НАХОЖДЕНИЯ АСИМПТОТИЧЕСКОГО ЗНАЧЕНИЯ~$R(\alpha, n)$ С ТОЧНОСТЬЮ
ДО~$O(n^{-2})$) ПРИ~$n\to\infty$ И ФИКСИРОВАННОМ~$\alpha<1$.

\ex[40] шССЛЕДУЙТЕ ПОВЕДЕНИЕ АЛГОРИТМА~C, ЕСЛИ ЕГО ПРИСПОСОБИТЬ К
ВНЕШНЕМУ ПОИСКУ ТАК, КАК ЭТО ОПИСАНО В ТЕКСТЕ.

\ex[ть43] юБОБЩИТЕ МОДЕЛЬ °АЯ---ёПРУТА, ОБСУЖДАВШУЮСЯ ПОСЛЕ ТЕОРЕМЫ~P, НА
СЛУЧАЙ $M$~БЛОКОВ РАЗМЕРА~$b$. фОКАЖИТЕ, ЧТО~$C(z)=Q(z)/(B(z)-z^b)$, ГДЕ
$Q(z)$---МНОГОЧЛЕН СТЕПЕНИ~$b$ И~$Q(1)=0$. яОКАЖИТЕ, ЧТО СРЕДНЕЕ ЧИСЛО ПРОБ
РАВНО
$$
1+{M\over N}C'(1)=1+{1\over b}\left({1\over 1-q_1}+\cdots++{1\over
1-q_{b-1}}-{1\over2}{B''(1)-b(b-1)\over B'(1)-b}\right),
$$
ГДЕ~$q_1$~\dots$q_{b-1}$ СУТЬ КОРНИ МНОГОЧЛЕНА~$Q(z)/(z-1)$. чАМЕНИВ
БИНОМИАЛЬНОЕ РАСПРЕДЕЛЕНИЕ ВЕРОЯТНОСТЕЙ~$B(z)$ ПРИБЛИЖЕНИЕМ
яУАССОНА~$P(z)=e^{b\alpha(z-1)}$, ГДЕ $\alpha=N/Mb$, И ИСПОЛЬЗОВАВ
ЛАГРАНЖЕВУ ФОРМУЛУ ОБРАЩЕНИЯ (СР. С ФОРМУЛОЙ~(2.3.4.4-9) И УПР.~4.7-8),
ПРИВЕДИТЕ ОТВЕТ К ВИДУ~(61).

\ex[M48] юБОБЩИТЕ ТЕОРЕМУ~K, ПОЛУЧИВ ТОЧНЫЙ АНАЛИЗ ЛИНЕЙНОГО ОПРОБОВАНИЯ
ПРИ ИСПОЛЬЗОВАНИИ БЛОКОВ РАЗМЕРА~$b$.

%%650
\ex[ь47] фАЕТ ЛИ ПРИПИСЫВАНИЕ ПОСЛЕДОВАТЕЛЬНОСТЯМ ПРОБ
ОДИНАКОВЫХ ВЕРОЯТНОСТЕЙ МИНИМАЛЬНОЕ ЗНАЧЕНИЕ~$C_N$ СРЕДИ ВСЕХ МЕТОДОВ
ОТКРЫТОЙ АДРЕСАЦИИ?

\ex[M21] (ё.~фЖОНСОН.) эАЙДИТЕ ДЕСЯТЬ ПЕРЕСТАНОВОК
МНОЖЕСТВА~$\set{0, 1, 2, 3, 4}$, ЭКВИВАЛЕНТНЫХ РАВНОМЕРНОМУ ХЕШИРОВАНИЮ В
СМЫСЛЕ ТЕОРЕМЫ~U.

\ex[ь25] фОКАЖИТЕ, ЧТО ЕСЛИ ПРИПИСЫВАНИЕ ВЕРОЯТНОСТЕЙ
ПЕРЕСТАНОВКАМ ЭКВИВАЛЕНТНО РАВНОМЕРНОМУ ХЕШИРОВАНИЮ (В СМЫСЛЕ ТЕОРЕМЫ~U),
ТО ЧИСЛО ПЕРЕСТАНОВОК С НЕНУЛЕВЫМИ ВЕРОЯТНОСТЯМИ ПРЕВЗОЙДЕТ~$M^a$ ПРИ
ЛЮБОМ ФИКСИРОВАННОМ ПОКАЗАТЕЛЕ~$a$, ЕСЛИ $M$~ДОСТАТОЧНО ВЕЛИКО.

\ex[M48] сУДЕМ ГОВОРИТЬ, ЧТО СХЕМА ОТКРЫТОЙ АДРЕСАЦИИ ВКЛЮЧАЕТ
\emph{ЕДИНСТВЕННОЕ ХЕШИРОВАНИЕ,} ЕСЛИ ИСПОЛЬЗУЕТСЯ РОВНО
$M$~ПОСЛЕДОВАТЕЛЬНОСТЕЙ ПРОБ, НАЧИНАЮЩИХСЯ СО ВСЕХ ВОЗМОЖНЫХ
ЗНАЧЕНИЙ~$h(K)$ И ВСТРЕЧАЮЩИХСЯ С ВЕРОЯТНОСТЬЮ~$1/M$.

ўТО АСИМПТОТИЧЕСКИ ЛУЧШЕ (В СМЫСЛЕ МИНИМАЛЬНОСТИ~$C_N$): НАИЛУЧШАЯ СХЕМА
С ЕДИНСТВЕННЫМ ХЕШИРОВАНИЕМ ИЛИ СЛУЧАЙНЫЕ СХЕМЫ, АНАЛИЗИРОВАВШИЕСЯ В УПР.~44?

\ex[ь46] ▀ВЛЯЕТСЯ ЛИ МЕТОД, АНАЛИЗИРОВАВШИЙСЯ В УПР.~46,
НАИХУДШЕЙ ВОЗМОЖНОЙ СХЕМОЙ С ЕДИНСТВЕННЫМ ХЕШИРОВАНИЕМ? (ёР.~С~УПР.~60.)

\ex[ь49] эАСКОЛЬКО ХОРОША МОЖЕТ БЫТЬ СХЕМА С ЕДИНСТВЕННЫМ ХЕШИРОВАНИЕМ,
ЕСЛИ ШАГИ~$p_1$ $p_2$~\dots $p_{M-1}$ (ОБОЗНАЧЕНИЯ УПР.~44) ФИКСИРОВАНЫ И
НЕ ЗАВИСЯТ ОТ~$K$? (яРИМЕРАМИ ТАКИХ МЕТОДОВ СЛУЖАТ ЛИНЕЙНОЕ ОПРОБОВАНИЕ И
ПОСЛЕДОВАТЕЛЬНОСТИ, РАССМАТРИВАВШИЕСЯ В УПР.~20 И~47.)

\ex[ь25] хСЛИ В РАССЕЯННОЙ ТАБЛИЦЕ ПРОИЗВОДЯТСЯ СЛУЧАЙНЫЕ ВСТАВКИ И
УДАЛЕНИЯ, ТО СКОЛЬКО НУЖНО В СРЕДНЕМ НЕЗАВИСИМЫХ ВСТАВОК, ЧТОБЫ ВСЕ
$M$~ПОЗИЦИЙ ПОБЫВАЛИ В ЗАНЯТОМ СОСТОЯНИИ?

\ex[M46] яРОАНАЛИЗИРУЙТЕ ОЖИДАЕМОЕ ПОВЕДЕНИЕ АЛГОРИТМА~R. ёКОЛЬКО РАЗ В
СРЕДНЕМ БУДЕТ ВЫПОЛНЯТЬСЯ ШАГ~R4?

\rex[20] \exhead(ъЛЮЧИ ПЕРЕМЕННОЙ ДЛИНЫ.) тО МНОГИХ ПРИЛОЖЕНИЯХ
РАССЕЯННЫХ ТАБЛИЦ КЛЮЧИ МОГУТ СОСТОЯТЬ ИЗ ПРОИЗВОЛЬНОГО ЧИСЛА ЛИТЕР. т
ТАКОМ СЛУЧАЕ НЕЛЬЗЯ ПРОСТО ЗАПОМНИТЬ КЛЮЧ В ТАБЛИЦЕ, КАК ЭТО ДЕЛАЛОСЬ В
ПРОГРАММАХ ДАННОГО ПАРАГРАФА. яРИДУМАЙТЕ ХОРОШИЙ СПОСОБ ИСПОЛЬЗОВАНИЯ
РАССЕЯННЫХ ТАБЛИЦ ДЛЯ ХРАНЕНИЯ КЛЮЧЕЙ ПЕРЕМЕННОЙ ДЛИНЫ, ЕСЛИ РАБОТА
ВЕДЕТСЯ НА МАШИНЕ~\MIX.

%% 651
\bye