\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