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

%%601

\subchap{heshirovanie} % 6.4
dO SIH POR MY RASSMATRIVALI METODY POISKA, OSNOVANNYE NA SRAVNENII DANNOGO
ARGUMENTA~$K$ S IMEYUSHCHIMISYA V TABLICE KLYUCHAMI ILI NA ISPOLXZOVANII EGO
CIFR DLYA UPRAVLENIYA PROCESSOM RAZVETVLENIYA. nO ESTX I TRETIJ PUTX: NE
RYSKATX VOKRUG DA OKOLO, A PROIZVESTI NAD~$K$ NEKOTOROE ARIFMETICHESKOE
VYCHISLENIE I POLUCHITX FUNKCIYU~$f(K)$, UKAZYVAYUSHCHUYU ADRES V TABLICE, GDE
HRANITSYA~$K$ I ASSOCIIROVANNAYA S NIM INFORMACIYA.

nAPRIMER, RASSMOTRIM VNOVX MNOZHESTVO IZ 31~ANGLIJSKOGO SLOVA, KOTOROE MY
PODVERGALI VOZDEJSTVIYU RAZLICHNYH STRATEGII POISKA V P.~6.2.2 I \S~6.3.
tABLICA~1 SODERZHIT KOROTKUYU PROGRAMMU DLYA \MIX, PREOBRAZUYUSHCHUYU KAZHDYJ IZ
31~KLYUCHA V UNIKALXNOE CHISLO~$f(K)$ MEZHDU~$-10$ I~$30$. eSLI MY SRAVNIM
|TOT METOD S \MIX-PROGRAMMAMI DLYA UZHE IZUCHENNYH NAMI METODOV (NAPRIMER, S
BINARNYM POISKOM, OPTIMALXNYM POISKOM PO DEREVU, BOROVOJ PAMYATXYU,
CIFROVYM POISKOM PO DEREVU), TO UVIDIM, CHTO ON LUCHSHE KAK S TOCHKI ZRENIYA
PROSTRANSTVA, TAK I S TOCHKI ZRENIYA SKOROSTI; TOLXKO BINARNYJ POISK
ISPOLXZUET NESKOLXKO MENXSHE PROSTRANSTVA. v SAMOM DELE, PRI ISPOLXZOVANII
PROGRAMMY IZ TABL.~1 SREDNEE VREMYA POISKA SOSTAVLYAET LISHX
OKOLO~$17.8u$ (DANNYE O CHASTOTE VZYATY IZ RIS.~12), I DLYA HRANENIYA
31~KLYUCHA TREBUETSYA TABLICA VSEGO DLYA 41~|LEMENTA.

k SOZHALENIYU, NAHODITX PODOBNYE FUNKCII~$f(K)$ DOVOLXNO SLOZHNO. sUSHCHESTVUET
$41^{31}\approx10^{50}$~RAZLICHNYH OTOBRAZHENIJ MNOZHESTVA IZ 31~|LEMENTA V
MNOZHESTVO IZ 41~|LEMENTA, I
TOLXKO $41\cdot40\cdot\ldots\cdot11=41!/10!\approx10^{43}$ IZ NIH DAYUT
RAZLICHNYE ZNACHENIYA DLYA KAZHDOGO ARGUMENTA; TAKIM OBRAZOM, LISHX ODNA IZ
KAZHDYH 10~MILLIONOV FUNKCIJ OKAZYVAETSYA PODHODYASHCHEJ.

fUNKCII, DAYUSHCHIE NEPOVTORYAYUSHCHIESYA ZNACHENIYA, NEOZHIDANNO REDKI DAZHE V SLUCHAE
DOVOLXNO BOLXSHOJ TABLICY. nAPRIMER, ZNAMENITYJ PARADOKS DNEJ ROZHDENIYA
UTVERZHDAET, CHTO, ESLI V KOMNATE PRISUTSTVUET NE MENEE 23~CHELOVEK, IMEETSYA
HOROSHIJ SHANS NA TO, CHTO U DVUH IZ NIH SOVPADET DENX ROZHDENIYA!
iNYMI SLOVAMI, ESLI MY VYBIRAEM SLUCHAJNUYU FUNKCIYU, OTOBRAZHAYUSHCHUYU 23~KLYUCHA V
365-|LEMENTNUYU TABLICU, TO S VEROYATNOSTXYU~$0.4927$ (MENEE POLOVINY) VSE
KLYUCHI POPADUT V RAZNYE MESTA. sKEPTIKI, SOMNEVAYUSHCHIESYA V |TOM, MOGUT
POPYTATXSYA NAJTI SOVPADENIE DNEJ ROZHDENIYA NA BLIZHAJSHEJ BOLXSHOJ VECHERINKE.
[pARADOKS DNEJ ROZHDENIYA VPERVYE UPOMYANUT V RABOTAH FON~mIZESA ({\sl Istanbul
%%602
\"Universitesi Fen Fak\"ultesi Mecmuasi,\/} {\bf 4} (1939), 145--163)
I~u.~fELLERA (vVEDENIE V TEORIYU VEROYATNOSTEJ I EE PRILOZHENIYA, m., "mIR",
1964, GL.~2, \S~3).]

s DRUGOJ STORONY, PODHOD, ISPOLXZOVANNYJ V TABL.~1, DOVOLXNO GIBKIJ
[SR.~S~m.~gRENEVSKI I~v.~tURSKI, {\sl CACM,\/} {\bf 6} (1963), 322--323],
I DLYA TABLICY SREDNEGO RAZMERA PODHODYASHCHUYU FUNKCIYU MOZHNO NAJTI PRIMERNO
ZA DENX. v SAMOM DELE, OCHENX ZANYATNO RESHATX PODOBNYE GOLOVOLOMKI.

rAZUMEETSYA, TAKOJ METOD IMEET SUSHCHESTVENNYJ NEDOSTATOK, IBO SODERZHIMOE
TABLICY DOLZHNO BYTX IZVESTNO ZARANEE; DOBAVLENIE HOTYA BY ODNOGO KLYUCHA
MOZHET VSE ISPORTITX, I NAM PRIDETSYA NACHINATX FAKTICHESKI NA PUSTOM MESTE.
mOZHNO POLUCHITX GORAZDO BOLEE GIBKIJ METOD, ESLI OTBROSITX IDEYU
ODNOZNACHNOSTI, DOPUSKAYA SOVPADENIYA ZNACHENIJ~$f(K)$ DLYA RAZLICHNYH
ARGUMENTOV, I ISPOLXZOVATX OSOBYJ METOD RAZRESHENIYA NEOPREDELENNOSTI POSLE
VYCHISLENIYA~$f(K)$.

nASHI RASSMOTRENIYA PRIVODYAT K SHIROKO IZVESTNOMU KLASSU METODOV, OBYCHNO
NAZYVAEMYH \dfn{HESHIROVANIEM} ILI \dfn{RASSEYANNOJ PAMYATXYU.} aNGLIJSKIJ
GLAGOL "to hash" IMEET SMYSL NAREZATX, RASKROSHITX CHTO-LIBO ILI SDELATX IZ
|TOGO MESIVO; IDEYA HESHIROVANIYA SOSTOIT V TOM, CHTOBY VZYATX NEKOTORYE
HARAKTERISTIKI KLYUCHA I ISPOLXZOVATX POLUCHENNUYU CHASTICHNUYU INFORMACIYU
V KACHESTVE OSNOVY POISKA. mY VYCHISLYAEM \dfn{HESH-FUNKCIYU $h(K)$} I BEREM
|TO ZNACHENIE V KACHESTVE ADRESA NACHALA POISKA.

pARADOKS DNEJ ROZHDENIYA SLUZHIT DLYA NAS PREDOSTEREZHENIEM, CHTO, VEROYATNO,
NAJDUTSYA RAZLICHNYE KLYUCHI~$K_i\ne K_j$, DLYA KOTORYH
%%603
$h(K_i)=h(K_j)$. pODOBNOE SOBYTIE NAZYVAETSYA \dfn{KOLLIZIEJ;} DLYA
RAZRESHENIYA KOLLIZIJ BYLI RAZRABOTANY INTERESNYE PODHODY. chTOBY
ISPOLXZOVATX RASSEYANNUYU TABLICU, PROGRAMMIST DOLZHEN PRINYATX DVA POCHTI
NEZAVISIMYH RESHENIYA: ON DOLZHEN VYBRATX HESH-FUNKCIYU~$h(K)$ I METOD
RAZRESHENIYA KOLLIZIJ. eTI DVA ASPEKTA ZADACHI POISKA MY I RASSMOTRIM PO OCHEREDI.

\section hESH-FUNKCII. dLYA OPREDELENNOSTI NA PROTYAZHENII |TOGO PUNKTA BUDET
PREDPOLAGATXSYA, CHTO HESH-FUNKCIYA~$h$ IMEET NE BOLEE $M$~RAZLICHNYH ZNACHENIJ
I CHTO |TI ZNACHENIYA UDOVLETVORYAYUT USLOVIYU
$$
0\le h(K)<M
\eqno(1)
$$
DLYA VSEH KLYUCHEJ~$K$. v REALXNOM FAJLE MNOGO POCHTI ODINAKOVYH KLYUCHEJ,
PO|TOMU ZHELATELXNO VYBRATX HESH-FUNKCIYU, RASSEIVAYUSHCHUYU IH PO TABLICE. eTO
VAZHNO DLYA UMENXSHENIYA CHISLA KOLLIZIJ.

tEORETICHESKI NEVOZMOZHNO TAK OPREDELITX HESH-FUNKCIYU, CHTOBY ONA SOZDAVALA
SLUCHAJNYE DANNYE IZ NESLUCHAJNYH REALXNYH FAJLOV. nO NA PRAKTIKE NETRUDNO
SDELATX DOSTATOCHNO HOROSHUYU IMITACIYU SLUCHAJNOSTI, ISPOLXZUYA PROSTYE
ARIFMETICHESKIE DEJSTVIYA, OBSUZHDAVSHIESYA V GL.~3. nA SAMOM DELE MY MOZHEM
POSTUPITX DAZHE LUCHSHE, VYYAVLYAYA NESLUCHAJNYE SVOJSTVA REALXNYH DANNYH I
STROYA NA IH OSNOVE HESH-FUNKCIYU, DAYUSHCHUYU MENXSHE KOLLIZIJ; CHEM KOGDA IMEYUTSYA
ISTINNO SLUCHAJNYE KLYUCHI.

rASSMOTRIM, NAPRIMER, SLUCHAJ DESYATIZNACHNYH KLYUCHEJ NA DESYATICHNOM KOMPXYUTERE.
 sAM SOBOJ NAPRASHIVAETSYA SLEDUYUSHCHIJ SPOSOB VYBORA HESH-FUNKCII: POLOZHITX~$M$
RAVNYM, SKAZHEM, 1000,
%%604
A V KACHESTVE~$h(K)$ VZYATX TRI CIFRY, VYBRANNYE PRIMERNO IZ SEREDINY
20-ZNACHNOGO PROIZVEDENIYA~$K\times K$. kAZALOSX BY, |TO DOLZHNO DAVATX
DOVOLXNO RAVNOMERNOE RASPREDELENIE ZNACHENIJ MEZHDU~$000$ I~$999$ S NIZKOJ
VEROYATNOSTXYU KOLLIZIJ. v SAMOM DELE, |KSPERIMENTY S REALXNYMI DANNYMI
POKAZALI, CHTO TAKOJ METOD "SEREDINY KVADRATA" NEPLOH PRI USLOVII, CHTO
KLYUCHI NE SODERZHAT MNOGO LEVYH ILI PRAVYH NULEJ PODRYAD. vYYASNILOSX, ODNAKO,
CHTO SUSHCHESTVUYUT BOLEE NADEZHNYE I PROSTYE SPOSOBY, PODOBNO TOMU KAK V GL.~3
METOD SEREDINY KVADRATA OKAZALSYA NE SLISHKOM HOROSHIM DATCHIKOM SLUCHAJNYH CHISEL.

mNOGOCHISLENNYE PROVERKI REALXNYH FAJLOV VYYAVILI OCHENX HOROSHUYU RABOTU DVUH
OSNOVNYH TIPOV HESH-FUNKCIJ. oDIN IZ NIH OSNOVAN NA DELENII, A DRUGOJ NA
UMNOZHENII.

mETOD DELENIYA OSOBENNO PROST: ISPOLXZUETSYA OSTATOK OT DELENIYA NA~$M$
$$
h(K)=K\bmod M.
\eqno(2)
$$
v |TOM SLUCHAE, OCHEVIDNO, NEKOTORYE ZNACHENIYA~$M$ MNOGO LUCHSHE DRUGIH.
nAPRIMER, ESLI $M$---CHETNOE CHISLO, TO ZNACHENIE~$h(K)$ BUDET CHETNYM PRI
CHETNOM~$K$ I NECHETNYM V PROTIVNOM SLUCHAE; CHASTO |TO PRIVODIT K
ZNACHITELXNYM SMESHCHENIYAM DANNYH. sOVSEM PLOHO BRATX~$M$ RAVNYM STEPENI
OSNOVANIYA SISTEMY SCHISLENIYA evm, TAK KAK TOGDA $h(K)$~DAET NAM PRAVYE
ZNACHASHCHIE CIFRY~$K$ ($K \bmod M$ NE ZAVISIT OT DRUGIH CIFR). aNALOGICHNO,
$M$ NE DOLZHNO BYTX KRATNO~$3$, IBO BUKVENNYE KLYUCHI, OTLICHAYUSHCHIESYA DRUG OT
DRUGA LISHX PORYADKOM BUKV, MOGLI BY DATX ZNACHENIYA FUNKCII, RAZNOSTX MEZHDU
KOTORYMI KRATNA~$3$. (pRICHINA KROETSYA V TOM,
CHTO~$10^n \bmod 3= 4^n \bmod 3= 1$.) vOOBSHCHE MY HOTELI BY IZBEZHATX
ZNACHENIJ~$M$, DELYASHCHIH~$r^k\pm a$, GDE $k$ I~$a$---NEBOLXSHIE CHISLA, A
$r$---"OSNOVANIE SISTEMY SCHISLENIYA" DLYA MNOZHESTVA ISPOLXZUEMYH LITER
(OBYCHNO $r=64$, 256 I~100), TAK KAK OSTATOK OT DELENIYA NA TAKIE
ZNACHENIYA~$M$ OBYCHNO OKAZYVAYUTSYA PROSTOJ SUPERPOZICIEJ CIFR KLYUCHA. nASHI
RASSMOTRENIYA PODSKAZYVAYUT, CHTO LUCHSHE VSEGO \emph{VZYATX V KACHESTVE~$M$
TAKOE PROSTOE CHISLO,} CHTOBY~$r^k\not\equiv \pm a \pmod{M}$ PRI
NEBOLXSHIH~$k$ I~$a$. pRAKTICHESKI VO VSEH SLUCHAYAH,  |TOT VYBOR OKAZYVAETSYA
VPOLNE UDOVLETVORITELXNYM.

nAPRIMER, NA MASHINE~\MIX\ MOZHNO POLOZHITX~$M=1009$, VYCHISLYAYA~$h (K)$
SLEDUYUSHCHIM OBRAZOM:
$$
\mixcode
LDX  &K      & $|rX|\asg K$.
ENTA &0      & $|rA|\asg 0$.
DIV  &=1009= & $|rA|\asg K \bmod 1009$.
\endmixcode
\eqno(3)
$$

mULXTIPLIKATIVNUYU SHEMU HESHIROVANIYA TAKZHE LEGKO REALIZOVATX, NO
NESKOLXKO TRUDNEE OPISATX, TAK KAK NUZHNO PREDSTAVITX, CHTO MY RABOTAEM S
DROBYAMI, A NE S CELYMI CHISLAMI. pUSTX $w$~ESTX RAZMER MASHINNOGO SLOVA
(DLYA \MIX{} |TO ZNACHENIE OBYCHNO
%%605
RAVNO~$10^{10}$ ILI~$2^{30}$); CELOE CHISLO~$A$ MOZHNO RASSMATRIVATX KAK
DROBX~$A/w$, ESLI MYSLENNO POSTAVITX DESYATICHNUYU (ILI DVOICHNUYU) TOCHKU SLEVA
OT MASHINNOGO SLOVA, V KOTOROM ZAPISANO~$A$. mETOD SOSTOIT V TOM, CHTOBY
VYBRATX~$A$ VZAIMNO PROSTYM S~$w$ I POLOZHITX
$$
h(K)=\floor{M\left(\left({A\over w} K\right)\bmod 1\right)}.
\eqno(4)
$$
nA DVOICHNOJ~evm  $M$~OBYCHNO BERUT RAVNYM STEPENI DVOJKI, TAK CHTO
$h(K)$~SOSTOIT IZ STARSHIH BITOV PRAVOJ ZNACHASHCHEJ POLOVINY PROIZVEDENIYA~$AK$.

nA DVOICHNOJ VERSII MASHINY~\MIX{} PRI~$M=2^m$ MULXTIPLIKATIVNAYA
HESH-FUNKCIYA VYCHISLYAETSYA TAK:
$$
\mixcode
LDA  & K & $|rA|\asg K$.
MUL & A & $|rAX|\asg AK$.
ENTA& 0 & $|rAX|\asg AK \bmod w$.
SLB   & m & sDVIG |rAX| NA $m$~BITOV VLEVO.
\endmixcode
\eqno(5)
$$
rEZULXTAT POLUCHAETSYA V REGISTRE~|A|. \MIX{} IMEET DOVOLXNO MEDLENNYE
KOMANDY UMNOZHENIYA I SDVIGA, PO|TOMU~(5) I~(3) ZATRACHIVAYUT ODINAKOVOE
VREMYA; ODNAKO NA MNOGIH MASHINAH UMNOZHENIE ZNACHITELXNO BYSTREE DELENIYA.

v SUSHCHNOSTI, |TOT METOD MOZHNO RASSMATRIVATX KAK OBOBSHCHENIE~(3), POSKOLXKU
MY MOGLI BY, NAPRIMER, VZYATX V KACHESTVE~$A$ PRIBLIZHENIE K~$w/1009$;
UMNOZHENIE NA OBRATNUYU VELICHINU CHASTO OKAZYVAETSYA BYSTREE DELENIYA. zAMETIM,
CHTO (5)~POCHTI SOVPADAET S METODOM SEREDINY KVADRATA, ODNAKO IMEETSYA ODNO
VAZHNOE OTLICHIE: V DALXNEJSHEM MY UVIDIM, CHTO UMNOZHENIE NA
PODHODYASHCHUYU KONSTANTU IMEET MNOGO POLEZNYH SVOJSTV.

oDNA IZ PRIVLEKATELXNYH CHERT MULXTIPLIKATIVNOJ SHEMY SOSTOIT V TOM, CHTO
V~(5) NE PROISHODIT POTERI INFORMACII; MY MOGLI BY VNOVX NAJTI~$K$, ZNAYA
LISHX SODERZHIMOE~$|rAX|$ POSLE VYPOLNENIYA INSTRUKCIJ~(5). dELO V TOM, CHTO
$A$~VZAIMNO PROSTO S~$w$, I PRI POMOSHCHI ALGORITMA eVKLIDA MOZHNO NAJTI
KONSTANTU~$A'$:~$AA'\bmod w=1$; OTSYUDA SLEDUET,
CHTO~$K=(A' (AK \bmod w)) \bmod w$. iNYMI SLOVAMI, ESLI OBOZNACHITX
CHEREZ~$f(K)$ SODERZHIMOE REGISTRA~$X$ PERED VYPOLNENIEM INSTRUKCII~|SLB|
V~(5), TO
$$
K_1\ne K_2 \hbox{ VLECHET } f(K_1)\ne f(K_2).
\eqno(6)
$$
kONECHNO, $f(K)$~PRINIMAET ZNACHENIYA V DIAPAZONE OT~0 DO~$w-1$ I NE YAVLYAETSYA
SKOLXKO-NIBUDX PODHODYASHCHEJ HESH-FUNKCIEJ, NO ONA MOZHET BYTX OCHENX POLEZNOJ V
KACHESTVE \dfn{RASSEIVAYUSHCHEJ FUNKCII}, A IMENNO FUNKCII,
UDOVLETVORYAYUSHCHEJ~(6) I OBYCHNO PRIVODYASHCHEJ K RANDOMIZACII KLYUCHEJ. nAPRIMER,
EE OCHENX HOROSHO ISPOLXZOVATX V SOCHETANII S ALGORITMAMI POISKA PO DEREVU
IZ P.~6.2.2, ESLI PORYADOK KLYUCHEJ NAM BEZRAZLICHEN, TAK KAK ONA
USTRANYAET OPASNOSTX VYROZHDENIYA DEREVA PRI POSTUPLENII KLYUCHEJ V VOZRASTAYUSHCHEM
%%606
PORYADKE. rASSEIVAYUSHCHAYA FUNKCIYA POLEZNA TAKZHE V SVYAZI S
ALGORITMAMI CIFROVOGO POISKA PO DEREVU IZ \S~6.3, ESLI BITY ISTINNYH
KLYUCHEJ IMEYUT SMESHCHENIE.

dRUGAYA CHERTA MULXTIPLIKATIVNOGO METODA HESHIROVANIYA SOSTOIT V TOM, CHTO ON
HOROSHO ISPOLXZUET NESLUCHAJNYE SVOJSTVA, KOTORYE OBNARUZHIVAYUTSYA VO MNOGIH
FAJLAH. chASTO MNOZHESTVA ISTINNYH KLYUCHEJ SODERZHAT ARIFMETICHESKIE PROGRESSII
$\set{K, K+d, K+2d,~\ldots, K+td}$, NAPRIMER
IMENA~$\set{|PART1|,\ |PART2|,\ |PART3|}$
ILI~$\set{|TYPEA|,\ |TYPEB|,\ |TYPEC|}$. mULXTIPLIKATIVNYJ METOD,
HESHIROVANIYA PREOBRAZUET ARIFMETICHESKIE PROGRESSII V PRIBLIZHENNYE
\picture{rIS. 37. fIBONACHCHIEVO HESHIROVANIE.}
ARIFMETICHESKIE PROGRESSII~$h(K)$, $h(K+d)$, $h(K+2d)$,~\dots{}
NESOVPADAYUSHCHIH VELICHIN, UMENXSHAYA TEM SAMYM CHISLO KOLLIZIJ PO SRAVNENIYU SO
SLUCHAJNOJ SITUACIEJ. mETOD DELENIYA OBLADAET TAKIM ZHE SVOJSTVOM.

rISUNOK~37 ILLYUSTRIRUET |TOT ASPEKT MULXTIPLIKATIVNOGO HESHIROVANIYA V
OSOBENNO INTERESNOM SLUCHAE. pREDPOLOZHIM, CHTO $A/w$~PRIBLIZHENNO RAVNO
ZOLOTOMU
SECHENIYU~$\phi^{-1}=(\sqrt{5}-1)/2=0.6180339887$; POVEDENIE
POSLEDOVATELXNYH ZNACHENIJ~$h(K)$, $h(K+1)$, $h(K+2)$,~\dots{} MOZHNO IZUCHATX,
RASSMATRIVAYA POVEDENIE VELICHIN~$h(0)$, $h(1)$, $h(2)$,~\dots{} eTO NAVODIT
NAS NA MYSLX PROVESTI TAKOJ |KSPERIMENT: BERETSYA OTREZOK~$[0, 1]$, NA
KOTOROM POSLEDOVATELXNO OTMECHAYUTSYA TOCHKI~$\{\phi^{-1}\}$, $\{2\phi^{-1}\}$,
$\{3\phi^{-1}\}$,~\dots,  GDE $\{x\}$~OBOZNACHAET DROBNUYU CHASTX
CHISLA~($\{x\}=x-\floor{x}=x\bmod1$). kAK POKAZANO NA RIS.~37, |TI TOCHKI
RASPOLOZHENY NE SLISHKOM BLIZKO DRUG K DRUGU; KAZHDAYA VNOVX DOBAVLYAEMAYA TOCHKA
%%607
POPADAET V ODIN IZ NAIBOLXSHIH OSTAVSHIHSYA INTERVALOV I DELIT EGO ZOLOTYM
SECHENIEM! [eTO YAVLENIE BYLO VPERVYE ZAMECHENO ya.~oDERFELXDOM I DOKAZANO
s.~sVERCHKOVSKI, {\sl Fundamenta Math.,\/} {\bf 46} (1958), 187--189.
vAZHNUYU ROLX V DOKAZATELXSTVE IGRAYUT CHISLA fIBONACHCHI.]

eTO ZAMECHATELXNOE SVOJSTVO ZOLOTOGO SECHENIYA V DEJSTVITELXNOSTI YAVLYAETSYA
CHASTNYM SLUCHAEM OCHENX OBSHCHEJ TEOREMY, PREDUGADANNOJ gUGO shTEJNGAUZOM I
DOKAZANNOJ vEROJ tURAN shOSH [{\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 tEOREMA S. pUSTX $\theta$---LYUBOE IRRACIONALXNOE CHISLO. eSLI
POMESTITX NA OTREZOK~$[0, 1]$ TOCHKI~$\{\theta\}$, $\{2\theta\}$,~\dots,
$\{n\theta\}$, TO DLINY POLUCHIVSHIHSYA OTREZKOV BUDUT VYRAZHATXSYA NE BOLEE
CHEM TREMYA RAZLICHNYMI CHISLAMI. kROME TOGO, SLEDUYUSHCHAYA
TOCHKA~$\{(n+1)\theta\}$ POPADET V ODIN IZ OTREZKOV NAIBOLXSHEJ DLINY.\endmark

\noindent tAKIM OBRAZOM, TOCHKI~$\{\theta\}$, $\{2\theta\}$,~\dots,
$\{n\theta\}$ RASPOLAGAYUTSYA MEZHDU~0 I~1 OCHENX RAVNOMERNO. tEOREMA VERNA I
DLYA RACIONALXNYH~$\{\theta\}$, ESLI DATX PODHODYASHCHUYU TRAKTOVKU OTREZKOV
NULEVOJ DLINY, OBRAZUYUSHCHIHSYA PRI~$n$, BOLXSHEM ILI RAVNOM
ZNAMENATELYU~$\{\theta\}$. dOKAZATELXSTVO TEOREMY~S VMESTE S PODROBNYM
ANALIZOM VOZNIKAYUSHCHEJ SITUACII PRIVODITSYA V UPR.~8. oKAZYVAETSYA, CHTO
OTREZKI DANNOJ DLINY SOZDAYUTSYA I RAZRUSHAYUTSYA V PORYADKE
"PERVYM VKLYUCHAETSYA---PERVYM ISKLYUCHAETSYA". kONECHNO, NEKOTORYE
ZNACHENIYA~$\{\theta\}$ PREDPOCHTITELXNEE DRUGIH; NAPRIMER, ESLI
VZYATX~$\{\theta\}$ BLIZKIM K~0 ILI~1, TO SNACHALA OBRAZUETSYA MNOGO
MALENXKIH OTREZKOV I ODIN BOLXSHOJ. v UPR.~9 POKAZANO, CHTO DVA
CHISLA~$\phi^{-1}$ I~$\phi^{-2}=1-\phi^{-1}$ PRIVODYAT K "NAIBOLEE
RAVNOMERNO RASPREDELENNYM" POSLEDOVATELXNOSTYAM SREDI VSEH~$\{\theta\}$
OT~0 DO~1.

pRIVEDENNYE RASSUZHDENIYA PODVODYAT NAS K \dfn{FIBONACHCHIEVU HESHIROVANIYU,}
KOGDA V KACHESTVE~$A$ BERETSYA BLIZHAJSHEE K~$\phi^{-1}w$ CELOE CHISLO, VZAIMNO
PROSTOE S~$w$. nAPRIMER, ESLI BY \MIX{} BYLA DESYATICHNOJ evm, MOZHNO BYLO VZYATX
\picture{rIS. STR. 607}
eTOT MNOZHITELX OCHENX HOROSHO RASSEET KLYUCHI VRODE |LIST1|, |LIST2|, |LIST3|.
pOSMOTRIM, ODNAKO, CHTO PROIZOJDET, ESLI VOZRASTANIE POSLEDOVATELXNOSTI
PROISHODIT V CHETVERTOJ POZICII, KAK V KLYUCHAH |SUM1\]|~, |SUM2\]|~, |SUM3\]|~:
KARTINA BUDET TAKOJ, KAK ESLI BY TEOREMA~S ISPOLXZOVALASX
S~$\theta=\{100A/w\}=0.80339887$ VMESTO~$\theta=0.6180339887=A/w$.
rEZULXTIRUYUSHCHEE POVEDENIE, ODNAKO, BUDET DOSTATOCHNO HOROSHIM, NESMOTRYA NA TO
CHTO |TO ZNACHENIE~$\theta$ HUZHE~$\phi^{-1}$. eSLI ZHE VOZRASTANIE PROISHODIT
%%608
VO VTOROJ POZICII, KAK V KLYUCHAH |A1\]\]\]|~, |A2\]\]\]|~, |A3\]\]\]|~, TO
ISTINNOE ZNACHENIE~$\theta=0.9887$; POZHALUJ, |TO SLISHKOM BLIZKO
K~1. pO|TOMU, MOZHET BYTX, LUCHSHE VMESTO~(7) VZYATX V KACHESTVE MNOZHITELYA
\picture{rIS. STR. 608}
pODOBNYJ MNOZHITELX RAZDELIT POSLEDOVATELXNYE KLYUCHI, RAZLICHAYUSHCHIESYA V
\emph{LYUBOJ} POZICII. k SOZHALENIYU, |TOT VYBOR STRADAET DRUGIM POROKOM,
ANALOGICHNYM DELIMOSTI~$r^k\pm1$: KLYUCHI VRODE~|XY| I~|YX| POPADUT V ODNO I
TO ZHE MESTO! oDIN IZ SPOSOBOV PREODOLENIYA VOZNIKAYUSHCHEJ TRUDNOSTI SOSTOIT V
BOLEE PRISTALXNOM IZUCHENII SITUACII, LEZHASHCHEJ V OSNOVE TEOREMY~S. dLYA
KOROTKIH POSLEDOVATELXNOSTEJ KLYUCHEJ IMEYUT ZNACHENIE LISHX NESKOLXKO PERVYH
NEPOLNYH CHASTNYH RAZLOZHENIYA~$\theta$ V NEPRERYVNUYU DROBX; MALOSTX
NEPOLNYH CHASTNYH SOOTVETSTVUET HOROSHIM SVOJSTVAM RASPREDELENIYA. pO|TOMU
NAILUCHSHIE ZNACHENIYA~$\theta$ VYBIRAYUTSYA IZ INTERVALOV
$$
{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}.
$$
v KACHESTVE~$A$ MOZHNO VZYATX TAKOE ZNACHENIE, CHTOBY KAZHDYJ IZ EGO BAJTOV
LEZHAL V HOROSHEM DIAPAZONE I NE BYL SLISHKOM BLIZOK K ZNACHENIYAM DRUGIH
BAJTOV ILI IH DOPOLNENIYAM, NAPRIMER
\picture{rIS. STR. 608}
tAKOJ MNOZHITELX MOZHNO REKOMENDOVATX. (iZLOZHENNYE IDEI V OSNOVNOM
PRINADLEZHAT r. fLOJDU.)

hOROSHAYA HESH-FUNKCIYA DOLZHNA UDOVLETVORYATX DVUM TREBOVANIYAM:
\medskip
\item{a)}~EE VYCHISLENIE DOLZHNO BYTX OCHENX BYSTRYM;
\item{b)}~ONA DOLZHNA MINIMIZIROVATX CHISLO KOLLIZIJ.
\medskip
\noindent sVOJSTVO~(a) OTCHASTI ZAVISIT OT OSOBENNOSTEJ MASHINY, A
SVOJSTVO~(b)---OT HARAKTERA DANNYH. eSLI BY KLYUCHI BYLI
DEJSTVITELXNO SLUCHAJNYMI, MOZHNO BYLO BY PROSTO VYDELITX NESKOLXKO BITOV I
ISPOLXZOVATX IH DLYA HESH-FUNKCII, NO NA PRAKTIKE, CHTOBY UDOVLETVORITX~(b),
POCHTI VSEGDA NUZHNA FUNKCIYA, ZAVISYASHCHAYA OT VSEH BITOV.

dO SIH POR MY RASSMATRIVALI HESHIROVANIE KLYUCHEJ, SOSTOYASHCHIH IZ ODNOGO
SLOVA. s KLYUCHAMI, SOSTOYASHCHIMI IZ NESKOLXKIH SLOV ILI IMEYUSHCHIMI PEREMENNUYU
DLINU, MOZHNO RABOTATX KAK
%%609
S PREDSTAVLENNYMI S MNOGOKRATNOJ TOCHNOSTXYU CHISLAMI I PRIMENITX K NIM
RASSMOTRENNYE METODY. oDNAKO OBYCHNO OKAZYVAETSYA DOSTATOCHNOJ BOLEE BYSTRAYA
PROCEDURA, KOGDA OTDELXNYE SLOVA SNACHALA KOMBINIRUYUTSYA V ODNO, A ZATEM
PROIZVODITSYA EDINSTVENNOE UMNOZHENIE ILI DELENIE. dLYA KOMBINIROVANIYA
MOZHNO ISPOLXZOVATX SLOZHENIE PO MODULYU~$w$ ILI OPERACIYU "ISKLYUCHAYUSHCHEE ILI"
(NA DVOICHNYH evm). dOSTOINSTVOM OBEIH OPERACIJ YAVLYAETSYA IH OBRATIMOSTX,
T.~E.~IH REZULXTAT ZAVISIT OT VSEH BITOV ARGUMENTOV, PRICHEM "ISKLYUCHAYUSHCHEE
ILI" INOGDA PREDPOCHTITELXNEE, TAK KAK NE MOZHET PRIVESTI K
ARIFMETICHESKOMU PEREPOLNENIYU. zAMETIM, CHTO OBE OPERACII KOMMUTATIVNY,
PO|TOMU KLYUCHI~$(X, Y)$ I~$(Y, X)$ BUDUT "BROSHENY" PO ODNOMU ADRESU. chTOBY
IZBEZHATX |TOGO, g.~d.~kNOTT PREDLOZHIL PREDVARITELXNO DELATX CIKLICHESKIJ SDVIG.

bYLO PRIDUMANO MNOGO DRUGIH METODOV HESHIROVANIYA, NO NI ODIN IZ NIH NE
OKAZALSYA PREDPOCHTITELXNEE OPISANNYH VYSHE PROSTYH SHEM DELENIYA I UMNOZHENIYA.
oBZOR NEKOTORYH METODOV I IH PODROBNYE STATISTICHESKIE HARAKTERISTIKI PRI
RABOTE S REALXNYMI FAJLAMI MOZHNO NAJTI V STATXE
[V.~Y.~Lum, r.~S.~t.~Yuen, M.~Dodd, {\sl CACM,\/} {\bf 14} (1971), 228--239].

iZ DRUGIH ISPYTANNYH METODOV HESHIROVANIYA, POZHALUJ, NAIBOLEE INTERESNYM
YAVLYAETSYA SPOSOB, OSNOVANNYJ NA ALGEBRAICHESKOJ TEORII KODIROVANIYA. iDEYA
ANALOGICHNA METODU DELENIYA, TOLXKO VMESTO DELENIYA NA CELOE CHISLO
ISPOLXZUETSYA DELENIE NA MNOGOCHLEN PO MODULYU~2. (kAK BYLO ZAMECHENO V \S~4.6,
 |TA OPERACIYA PREDSTAVLYAET SOBOJ ANALOG DELENIYA, TAK ZHE KAK
SLOZHENIE---ANALOG "ISKLYUCHAYUSHCHEGO ILI".) dLYA PREDLAGAEMOGO METODA $M$~DOLZHNO
BYTX STEPENXYU~2: $M=2^m$; KROME TOGO, ISPOLXZUETSYA MNOGOCHLEN
$m\hbox{-J}$~STEPENI $P(x)=x^m+p_{m-1}x^{m-1}+\cdots+p_0$. dVOICHNYJ
KLYUCH~$K=(k_{n-1}\ldots{}k_1k_0)_2$ MOZHNO RASSMATRIVATX KAK
MNOGOCHLEN~$K(x)=k_{n-1}x^{n-1}+\cdots+k_1x+k_0$, I VYCHISLITX
OSTATOK~$K(x) \bmod P(x) = h_{m-1}x^{m-1}+\cdots+h_1x+h_0$,
ISPOLXZUYA POLINOMIALXNUYU ARIFMETIKU PO MODULYU~2:
$h(K)=(h_{m-1}\ldots{}h_1h_0)_2$. pRI PRAVILXNOM VYBORE~$P(x)$ TAKAYA
HESH-FUNKCIYA POZVOLYAET IZBEZHATX KOLLIZIJ, MEZHDU POCHTI RAVNYMI KLYUCHAMI.
nAPRIMER, ESLI $n=15$, $m=10$ I
$$
P(x)=x^{10}+x^8+x^5=x^4+x^2+x+1,
\eqno(10)
$$
TO MOZHNO POKAZATX, CHTO~$h(K_1)\ne h(K_2)$, KOGDA~$K_1\ne K_2$ I~$K_1$
OTLICHAETSYA OT~$K_2$ MENEE CHEM SEMXYU BITAMI. (v UPR.~7 VY NAJDETE
DOPOLNITELXNUYU INFORMACIYU OB |TOJ SHEME; RAZUMEETSYA, DLYA NEE BOLXSHE
PODHODIT APPARATNAYA ILI MIKROPROGRAMMNAYA, A NE PROGRAMMNAYA REALIZACIYA.)

kAK POKAZAL OPYT, PRI OTLADKE PROGRAMM UDOBNO ISPOLXZOVATX POSTOYANNUYU
HESH-FUNKCIYU~$h(K)=0$; TAK KAK VSE KLYUCHI
%% 610
BUDUT HRANITXSYA VMESTE; |FFEKTIVNAYA~$h(K)$ MOZHET BYTX VVEDENA POZDNEE.

\section rAZRESHENIE KOLLIZIJ METODOM CEPOCHEK. mY UZHE GOVORILI,
CHTO NEKOTORYE ADRESA MOGUT POROZHDATXSYA NESKOLXKIMI KLYUCHAMI. pOZHALUJ,
NAIBOLEE OCHEVIDNYJ SPOSOB RESHENIYA PROBLEMY SOSTOIT V TOM, CHTOBY
PODDERZHIVATX $M$~SVYAZANNYH SPISKOV, PO ODNOMU NA KAZHDYJ VOZMOZHNYJ
HESH-ADRES. vSE ZAPISI DOLZHNY SODERZHATX POLYA~|LINK|; KROME TOGO, NUZHNO
IMETX $M$~GOLOVNYH UZLOV SPISKOV~$|HEAD|[i]$, GDE $i$~MENYAETSYA OT~1
DO~$M$. pOSLE HESHIROVANIYA
\picture{rIS.~38.           rAZDELXNYE CEPOCHKI.}
KLYUCHA MY PROSTO VYPOLNYAEM POSLEDOVATELXNYJ POISK V SPISKE S
NOMEROM~$h(K)+1$. (sR.~UPR.~6.1-2. sITUACIYA ANALOGICHNA SORTIROVKE
VSTAVKAMI V NESKOLXKO SPISKOV---PROGRAMMA 5.2.1M.)
rISUNOK~38 ILLYUSTRIRUET |TOT PROSTOJ METOD CEPOCHEK PRI~$M=9$ DLYA
POSLEDOVATELXNOSTI SEMI KLYUCHEJ
$$
K=|EN|, |TO|, |TRE|, |FIRE|, |FEM|, |SEKS|, |SYV|
\eqno   (11)
$$
(TAK NAZYVAYUTSYA CHISLA OT~1 DO~7 PO-NORVEZHSKI), IMEYUSHCHIH SOOTVETSTVENNYE
HESH-KODY
$$
h(K)+1=3, 1, 4, 1, 5, 9, 2.
\eqno(12)
$$
pERVYJ SPISOK SODERZHIT DVA |LEMENTA, TRI SPISKA PUSTY.

mETOD CEPOCHEK YAVLYAETSYA VESXMA BYSTRYM, POSKOLXKU SPISKI KOROTKI. eSLI V
ODNOJ KOMNATE SOBRATX 365~CHELOVEK, DTO NAJDETSYA MNOGO PAR, IMEYUSHCHIH ODIN
I TOT ZHE DENX ROZHDENIYA, NO DANNYJ DENX ROZHDENIYA V SREDNEM IMEET LISHX ODIN
CHELOVEK! vOOBSHCHE, ESLI IMEETSYA $N$~KLYUCHEJ I $M$~SPISKOV, SREDNIJ
RAZMER SPISKA RAVEN~$N/M$; TAKIM OBRAZOM, HESHIROVANIE UMENXSHAET KOLICHESTVO
RABOTY, TREBUEMOE NA POSLEDOVATELXNYJ POISK, PRIMERNO V $M$~RAZ. (tOCHNAYA
FORMULA VYVEDENA V UPR.~34.)

%%611

eTOT METOD PREDSTAVLYAET SOBOJ OCHEVIDNUYU KOMBINACIYU OBSUZHDAVSHIHSYA RANEE
METODOV, PO|TOMU NET NUZHDY PODROBNO OPISYVATX ALGORITM DLYA RASSEYANNYH
TABLIC S CEPOCHKAMI. chASTO POLEZNO SODERZHATX OTDELXNYE  SPISKI
UPORYADOCHENNYMI  PO KLYUCHAM;
|TO UBYSTRYAET VSTAVKI I NEUDACHNYJ POISK. tAK, ESLI DELATX SPISKI
VOZRASTAYUSHCHIMI, NA RIS.~38 SLEDOVALO BY POMENYATX MESTAMI UZLY~|TO| I~|FIRE|,
 A VSE PUSTYE SSYLKI ZAMENITX NA UKAZATELX NA VSPOMOGATELXNUYU ZAPISX
S~$\infty$ V KACHESTVE KLYUCHA (SM. ALGORITM 6.1T). dRUGIM VOZMOZHNYM PODHODOM
YAVLYAETSYA ISPOLXZOVANIE PONYATIYA "SAMOORGANIZUYUSHCHEGOSYA FAJLA",
KOTOROE OBSUZHDALOSX V \S~6.1; VMESTO UPORYADOCHENIYA PO KLYUCHAM PROISHODIT
UPORYADOCHENIE PO VREMENI POSLEDNEGO OBRASHCHENIYA K ZAPISI.

v CELYAH |KONOMII VREMENI ZHELATELXNY BOLXSHIE~$M$, NO V |TOM SLUCHAE MNOGIE
SSYLKI BUDUT PUSTYMI, TAK CHTO B\'OLXSHAYA CHASTX PROSTRANSTVA, OTVODIMOGO POD
$M$~GOLOVNYH UZLOV, POTRATITSYA ZRYA. dLYA NEBOLXSHIH PO RAZMERU ZAPISEJ
NAPRASHIVAETSYA DRUGOJ PODHOD: MOZHNO NALOZHITX PROSTRANSTVO DLYA ZAPISEJ NA
PROSTRANSTVO DLYA GOLOVNYH UZLOV, OTVODYA V TABLICE MESTO POD
$M$~ZAPISEJ I $M$~SSYLOK, A NE POD $N$~ZAPISEJ I $M+N$~SSYLOK.
iNOGDA MOZHNO SOVERSHITX ODIN PROHOD PO DANNYM I VYYASNITX, KAKIE GOLOVNYE
UZLY BUDUT ISPOLXZOVATXSYA, VSTAVLYAYA NA SLEDUYUSHCHEM PROHODE "PEREPOLNYAYUSHCHIE"
ZAPISI V SVOBODNYE SHCHELI. chASTO, ODNAKO, |TO NEZHELATELXNO ILI NEVOZMOZHNO;
NAM HOTELOSX BY IMETX METOD, PRI KOTOROM KAZHDAYA ZAPISX OBRABATYVAETSYA
LISHX ODIN RAZ, PRI PERVOM POSTUPLENII V SISTEMU. sLEDUYUSHCHIJ ALGORITM,
PRINADLEZHASHCHIJ f.~uILXYAMSU [{\sl CACM,\/} {\bf 2}, 6 (June 1959), 21--24],
YAVLYAETSYA OBSHCHEPRINYATYM SPOSOBOM RESHENIYA |TOJ ZADACHI.

\alg C.(pOISK S VSTAVKOJ PO RASSEYANNOJ TABLICE S CEPOCHKAMI.) pREDLAGAEMYJ
ALGORITM POZVOLYAET OTYSKATX V TABLICE IZ $M$~|LEMENTOV DANNYJ KLYUCH~$K$.
eSLI $K$~NET V TABLICE I ONA NE POLNA, $K$ VSTAVLYAETSYA V NEE.

eLEMENTY TABLICY OBOZNACHAYUTSYA CHEREZ $|TABLE| [i]$, $0\le i\le M$, I MOGUT
BYTX DVUH RAZLICHNYH TIPOV: \emph{SVOBODNYJ} I~\emph{ZANYATYJ.} zANYATYJ UZEL
SODERZHIT KLYUCHEVOE POLE~$|KEY|[i]$, POLE SSYLKI~$|LINK|[i]$ I, VOZMOZHNO,
DRUGIE POLYA.

aLGORITM ISPOLXZUET HESH-FUNKCIYU~$h(K)$. dLYA OBLEGCHENIYA POISKA SVOBODNOGO
PROSTRANSTVA ISPOLXZUETSYA VSPOMOGATELXNAYA PEREMENNAYA~|R|; ESLI TABLICA
PUSTA, $|R|=M+1$; PO MERE PROVEDENIYA  VSTAVOK BUDET OSTAVATXSYA V SILE
UTVERZHDENIE, CHTO UZLY~$|TABLE|[j]$ ZANYATY DLYA VSEH~$j$ V DIAPAZONE~$|R|\le
j\le M$. uSLOVIMSYA, CHTO UZEL~$|TABLE|[0]$ VSEGDA BUDET SVOBODEN.

\st[hESHIROVANIE.] uSTANOVITX~$i\asg h(K)+1$. (tEPERX~$1\le i\le M$.)
\st[sPISOK?] eSLI UZEL~$|TABLE|[i]$ SVOBODEN, TO PEREJTI NA~\stp{6}.
(v PROTIVNOM SLUCHAE  |TOT UZEL  ZANYAT, I MY POSLEDUEM NA IMEYUSHCHIJSYA ZDESX
SPISOK ZANYATYH UZLOV).

%% 612
\st[sRAVNENIE.] eSLI $K=|KEY|[i]$, POISK ZAVERSHEN UDACHNO.

\st[pEREHOD K SLEDUYUSHCHEMU.] eSLI $|LINK|[i]\ne0$,
USTANOVITX~$i\asg|LINK|[i]$ I VERNUTXSYA NA~\stp{3}.

\st[nAJTI SVOBODNYJ UZEL.] (pOISK BYL NEUDACHNYM, I MY HOTIM NAJTI V
TABLICE SVOBODNOE MESTO.) uMENXSHATX~|R| DO TEH POR, POKA NE BUDET POLUCHENO
TAKOE ZNACHENIE, CHTO UZEL~$|TABLE|[|R|]$ SVOBODEN. eSLI~$|R|=0$, ALGORITM
ZAKANCHIVAETSYA PO PEREPOLNENIYU (SVOBODNYH UZLOV BOLXSHE NET); V PROTIVNOM
SLUCHAE USTANOVITX~$|LINK|[i]\asg|R|$, $i\asg|R|$.

\st[vSTAVITX NOVYJ KLYUCH.] pOMETITX~$|TABLE|[i]$ KAK ZANYATYJ UZEL
S~$|KEY|[i]\asg K$ I~$|LINK|[i]\asg0$.
\algend

v ALGORITME DOPUSKAETSYA SRASTANIE NESKOLXKIH SPISKOV, TAK CHTO POSLE
VSTAVKI V TABLICU ZAPISI PEREMESHCHATX NE NUZHNO.
\picture{rIS. 39.  pOISK S VSTAVKOJ PO RASSEYANNOJ TABLICE S CEPOCHKAMI.}
[sM., NAPRIMER, RIS.~40, GDE |SEKS| POPADAET V SPISOK, SODERZHASHCHIJ~|TO|
I~|FIRE|, TAK KAK POSLEDNIJ KLYUCH UZHE BYL VSTAVLEN V POZICIYU~9.]
\picture{rIS. 40. sROSSHIESYA SPISKI.}

chTOBY SRAVNITX DANNYJ I DRUGIE ALGORITMY |TOJ GLAVY, NAPISHEM SLEDUYUSHCHUYU
PROGRAMMU DLYA \MIX{} (PRI SOSTAVLENII
%%613
PROGRAMMY UCHITYVALOSX, CHTO SPISKI,  KAK PRAVILO, BUDUT KOROTKIMI).

\prog C.(pOISK S VSTAVKOJ PO RASSEYANNOJ TABLICE S CEPOCHKAMI.)
dLYA UDOBSTVA BUDEM SCHITATX, CHTO KLYUCHI SOSTOYAT IZ TREH BAJTOV, A UZLY IMEYUT
SLEDUYUSHCHIJ FORMAT:
\picture{rIS. STR. 613}
v KACHESTVE RAZMERA TABLICY~$M$ BERETSYA PROSTOE CHISLO;
$|TABLE|[i]$~HRANITSYA PO ADRESU~$|TABLE|+i$; $|rI1|\equiv i$,
$|rA|\equiv K$.
\code
KEY   &EQU  & 3:5
LINK  &EQU  & 0:2
START &LDX  & k             & 1     & C1. hESHIROVANIE.
      &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. sPISOK?
      &J2N  & 6F            & 1     & nA C6, ESLI V $|TABLE|[i]$ SVOBODNO.
      &smra & TABLE, 1(KEY) & A     & C3. sRAVNENIE.
      &JE   & SUCCESS       & A     & vYHOD, ESLI $K=|KEY|[i]$.
      &J2Z  & 5F            & A-S1  & nA C5, ESLI $|LINK|[i]=0$.
4H    &ENT1 & 0,2           & C-1   & C4. pEREHOD K SLEDUYUSHCHEMU.
      &smra & TABLE, 1(KEY) & C-1   & C3. sRAVNENIE.
      &JE   & SUCCESS       & C-1   & vYHOD, ESLI $K=|KEY|[i]$.
      &LD2  & TABLE,1(L1NK) & C-1-S2
      &J2NZ & 4B            & C-1-S2& pRODVIGATXSYA, ESLI $|LINK|[i]\ne0$.
5H    &LD2  & R             & A-S    & C5. nAJTI SVOBODNYJ UZEL.
      &DEC2 & 1             & T      & $|R|\asg|R|-1$.
      &LDX  & TABLE,2       & T
      &JXNN & *-2           & t      & pOVTORYATX, POKA ZANYAT $|TABLE|[|R|]$.
      &J2Z  & OVERFLOW      & A-S    & vYHOD, ESLI NET SVOBODN. UZLOV
      &ST2  & TABLE, 1(LINK)& A-S    & $|LINK|[i]\asg|R|$.
      &ENT1 & 0,2           & A-S    & $i\asg|R|$.
      &ST2  & R             & A-S    & iZMENITX~|R| V PAMYATI.
6H    &STZ  & TABLE, 1(LINK)& 1-S    & C6. vSTAVITX NOVYJ KLYUCH.
      &STA  & TABLE, 1(KEY) & 1-S    & $|KEY|[i]\asg K$.
\endcode
\progend
vREMYA RABOTY |TOJ PROGRAMMY OPREDELYAYUT SLEDUYUSHCHIE PARAMETRY:

\medskip
\item{$C=$}CHISLO |LEMENTOV TABLICU, ISSLEDUEMYH VO VREMYA POISKA;
%%614
\item{$A=$}1, ESLI PERVYJ ISPROBOVANNYJ UZEL OKAZALSYA ZANYATYM;

\item{$S=$}1 PRI UDACHNOM POISKE, 0 PRI NEUDACHNOM;

\item{$T=$}CHISLO |LEMENTOV TABLICY, PROSMATRIVAEMYH V PROCESSE POISKA
SVOBODNOGO PROSTRANSTVA.
\medskip
\noindent zDESX $S=S1+S2$, GDE~$S1=1$, ESLI PERVAYA PROBA BYLA
UDACHNOJ. sUMMARNOE VREMYA RABOTY FAZY POISKA PROGRAMMY~C
RAVNO~$(7C+4A+17-3S+2S1)u$, VSTAVKA NOVOGO KLYUCHA PRI~$S=0$ TREBUET
DOPOLNITELXNOGO VREMENI~$(8A+4T+4)u$.

pREDPOLOZHIM, CHTO V NACHALE RABOTY PROGRAMMY TABLICA SODERZHIT $N$~KLYUCHEJ,
I VVEDEM
$$
\alpha=N/M=\hbox{KO|FFICIENT ZAPOLNENIYA (ZAGRUZKI) TABLICY.}
\eqno (14)
$$
tOGDA SREDNEE ZNACHENIE~$A$ PRI NEUDACHNOM POISKE, OCHEVIDNO,
RAVNO~$\alpha$ (PRI SLUCHAJNOJ FUNKCII HESHIROVANIYA); V UPR.~39
DOKAZYVAETSYA, CHTO SREDNEE ZNACHENIE~$C$ PRI NEUDACHNOM POISKE SOSTAVLYAET
$$
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)
$$

tAKIM OBRAZOM, ESLI TABLICA ZAPOLNENA NAPOLOVINU, SREDNEE CHISLO PROB,
PROIZVODIMYH VO VREMYA NEUDACHNOGO POISKA,
PRIBLIZHENNO RAVNO~${1\over4}(e+2)\approx 1.18$; DAZHE ESLI TABLICA
ZAPOLNYAETSYA POLNOSTXYU, SREDNEE CHISLO PROB PRI VSTAVKE POSLEDNEGO |LEMENTA
DOSTAVLYAET LISHX OKOLO~${1\over4}(e^2+1)\approx 2.10$. kAK DOKAZYVAETSYA V
UPR.~40, SREDNEKVADRATICHNOE OTKLONENIE TAKZHE MALO. eTI VYKLADKI POKAZYVAYUT,
 CHTO PRI SLUCHAJNOJ FUNKCII HESHIROVANIYA \emph{SPISKI OSTAYUTSYA KOROTKIMI,
NESMOTRYA NA VOZMOZHNOSTX SRASTANIJ.} rAZUMEETSYA, $C$~MOZHET STATX RAVNYM~$N$,
 ESLI HESH-FUNKCIYA PLOHA ILI ESLI NAM ZDOROVO NE POVEZLO.

dLYA UDACHNOGO POISKA $A$~VSEGDA RAVNO~1. sREDNEE CHISLO PROB MOZHNO VYCHISLITX,
 PROSUMMIROVAV VELICHINY~$C+A$ PO PERVYM~$N$ NEUDACHNYM POISKAM I PODELIV
NA~$N$. pREDPOLAGAETSYA, CHTO VSE KLYUCHI RAVNOVEROYATNY. iMEEM
$$
\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
}
$$
dAZHE V SLUCHAE ZAPOLNENNOJ TABLICY V SREDNEM DLYA NAHOZHDENIYA |LEMENTA
PONADOBITSYA LISHX OKOLO $1.80$~PROBY! aNALOGICHNO (SM.~UPR.~42) SREDNEE
ZNACHENIE~$S1$ OKAZYVAETSYA RAVNYM
$$
S1_N=1-{1\over2}((N-1)/M)\approx 1-{1\over2}\alpha.
\eqno(17)
$$
%%615
nA PERVYJ VZGLYAD SHAG~C5 MOZHET POKAZATXSYA NE|FFEKTIVNYM, TAK KAK V NEM
POISK SVOBODNOJ POZICII PROIZVODITSYA POSLEDOVATELXNO. nO V
DEJSTVITELXNOSTI V PROCESSE ZAPOLNENIYA TABLICY SUMMARNOE CHISLO PROB V
SHAGE~C5 NE PREVYSHAET KOLICHESTVA |LEMENTOV V TABLICE; ZNACHIT, V SREDNEM NA
KAZHDUYU VSTAVKU TRATITSYA NE BOLEE ODNOJ TAKOJ PROBY! v UPR.~41 DOKAZYVAETSYA,
CHTO DLYA SLUCHAJNOGO NEUDACHIOGO POISKA~$T\approx \alpha e^\alpha$.

mOZHNO BYLO BY IZBEZHATX SRASTANIYA SPISKOV, SOOTVETSTVUYUSHCHIM OBRAZOM
MODIFICIROVAV ALGORITM~C, NO TOGDA PRISHLOSX BY PRIBEGNUTX K PEREMESHCHENIYU
ZAPISEJ. rASSMOTRIM, NAPRIMER, CHTO PROISHODIT PRI POPYTKE VSTAVITX~|SEKS|
V POZICIYU~9 (SM.~RIS.~40). chTOBY SPISKI OSTAVALISX RAZDELXNYMI, NUZHNO
PEREMESTITX~|FIRE|; PRI |TOM NEOBHODIMO NAJTI UZEL, SODERZHASHCHIJ SSYLKU
NA~|FIRE|. dLYA RESHENIYA |TOJ ZADACHI MOZHNO, KAK PREDLOZHIL aLLEN nXYU|LL
V~1962~G., VMESTO DVUHSVYAZEVYH ISPOLXZOVATX KOLXCEVYE SPISKI, TAK KAK V
KAZHDOM SPISKE NEMNOGO |LEMENTOV. oDNAKO |TO, VEROYATNO, ZAMEDLIT GLAVNYJ
CIKL POISKA, POSKOLXKU SHAG~C4 STANOVITSYA SLOZHNEE. v UPR.~34 POKAZANO,
CHTO V SLUCHAE NEPERESEKAYUSHCHIHSYA SPISKOV SREDNEE CHISLO PROB UMENXSHAETSYA DO
$$
\eqalignno{
C'_N&=\left(1-{1\over M}\right)^N+{N\over M}\approx e^{-\alpha}+\alpha
\qquad\hbox{(NEUDACHNYJ POISK);} & (18)\cr
C_N&=1+{N-1\over 2M}\approx 1+{1\over2}\alpha
\qquad\hbox{(UDACHNYJ POISK).} & (19) \cr
}
$$
vRYAD LI STOIT RADI TAKOGO ULUCHSHENIYA IZMENYATX ALGORITM.

s DRUGOJ STORONY, bATLER l|MPSON ZAMETIL, CHTO BOLXSHAYA CHASTX PROSTRANSTVA,
V DEJSTVITELXNOSTI ZANYATOGO SSYLKAMI, MOZHET BYTX S|KONOMLENA V METODE
CEPOCHEK, ESLI IZBAVITXSYA OT SRASTANIYA SPISKOV. eTO PRIVODIT K INTERESNOMU
ALGORITMU, OBSUZHDAYUSHCHEMUSYA V UPR.~13.

zAMETIM, CHTO METOD CEPOCHEK MOZHNO ISPOLXZOVATX I PRI~$N>M$, TAK CHTO
PEREPOLNENIE NE PREDSTAVLYAET SERXEZNOJ PROBLEMY. eSLI ISPOLXZUYUTSYA
RAZDELXNYE SPISKI, FORMULY~(18) I~(19) SPRAVEDLIVY DLYA~$\alpha>1$. kOGDA
ZHE SPISKI SRASTAYUTSYA, KAK V ALGORITME~C, MOZHNO POMESHCHATX PEREPOLNYAYUSHCHIE
|LEMENTY VO VSPOMOGATELXNYJ PUL PAMYATI. kAK DOKAZAL l.~gYUIBA, V
|TOM SLUCHAE SREDNEE CHISLO PROB PRI VSTAVKE $(M+L+1)\hbox{-GO}$~|LEMENTA
SOSTAVLYAET~$\left(L/2M+{1\over4}\right)((1+2/M)^M-1)+{1\over2}$.

\section rAZRESHENIE KOLLIZIJ "OTKRYTOJ ADRESACIEJ". dRUGOJ SPOSOB RESHENIYA
PROBLEMY KOLLIZIJ SOSTOIT V TOM, CHTOBY POLNOSTXYU OTKAZATXSYA OT SSYLOK I
PROSTO PROSMATRIVATX ODIN ZA DRUGIM RAZLICHNYE |LEMENTY TABLICY, POKA NE
BUDUT NAJDENY KLYUCH~$K$ ILI SVOBODNAYA POZICIYA. nE PLOHO BYLO BY IMETX
PRAVILO, SOGLASNO KOTOROMU KAZHDYJ KLYUCH~$K$ OPREDELYAET POSLEDOVATELXNOSTX
%%616
PROB, T.~E.~POSLEDOVATELXNOSTX POZICIJ V TABLICE, KOTORYE NUZHNO
PROSMATRIVATX VSYAKIJ RAZ PRI VSTAVKE ILI POISKE~$K$. eSLI MY, ISPOLXZUYA
OPREDELYAEMUYU~$K$ POSLEDOVATELXNOSTX PROB, NATOLKNEMSYA NA SVOBODNUYU POZICIYU,
 TO MOZHNO SDELATX VYVOD, CHTO $K$~NET V TABLICE, TAK KAK TA ZHE
POSLEDOVATELXNOSTX PROB VYPOLNYAETSYA KAZHDYJ RAZ PRI OBRABOTKE DANNOGO KLYUCHA.
 eTOT OBSHCHIJ KLASS METODOV u.~pETERSON NAZVAL \dfn{OTKRYTOJ
ADRESACIEJ} [{\sl IBM J.~Research \& Development,\/} {\bf 1} (1957), 130--146].

pROSTEJSHAYA SHEMA OTKRYTOJ ADRESACII, IZVESTNAYA KAK \dfn{LINEJNOE
OPROBOVANIE,} ISPOLXZUET CIKLICHESKUYU POSLEDOVATELXNOSTX
$$
h(K), h(K)-1, \ldots, 0, M-1, M-2, \ldots, h(K)+1
\eqno(20)
$$
I OPISYVAETSYA SLEDUYUSHCHIM OBRAZOM.

\alg L.(pOISK S VSTAVKOJ PO OTKRYTOJ RASSEYANNOJ TABLICE.)
aLGORITM POZVOLYAET RAZYSKATX DANNYJ KLYUCH~$K$ V TABLICE IZ $M$~UZLOV.
eSLI $K$~NET V TABLICE I ONA NE POLNA, KLYUCH~$K$ VSTAVLYAETSYA.

uZLY TABLICY OBOZNACHAYUTSYA CHEREZ~$|TABLE|[i]$, $0\le i<M$, I PRINADLEZHAT
DVUM RAZLICHNYM TIPAM UZLOV---\emph{SVOBODNYH} I~\emph{ZANYATYH}. zANYATYJ UZEL
SODERZHIT KLYUCH~$|KEY|[i]$ I, VOZMOZHNO, DRUGIE POLYA. zNACHENIE VSPOMOGATELXNOJ
PEREMENNOJ~|N| RAVNO CHISLU ZANYATYH UZLOV; |TA PEREMENNAYA RASSMATRIVAETSYA
KAK CHASTX TABLICY, I PRI VSTAVKE NOVOGO KLYUCHA EE ZNACHENIE UVELICHIVAETSYA NA~1.

dANNYJ ALGORITM ISPOLXZUET HESH-FUNKCIYU~$h(K)$ I LINEJNUYU
POSLEDOVATELXNOSTX PROB~(20) DLYA ADRESACII. mODIFIKACII |TOJ
POSLEDOVATELXNOSTI OBSUZHDAYUTSYA NIZHE.

\st[hESHIROVANIE.] uSTANOVITX $i\asg h(K)$. (tEPERX $0\le i< M$.)

\st[sRAVNITX.] eSLI UZEL~$|TABLE|[i]$ SVOBODEN, TO PEREJTI NA~\stp{4}. v
PROTIVNOM SLUCHAE, ESLI~$|KEY|[i]=K$, ALGORITM ZAKANCHIVAETSYA UDACHNO.

\st[pEREJTI K SLEDUYUSHCHEMU.] uSTANOVITX~$i\asg i-1$; ESLI TEPERX $i<0$,
USTANOVITX~$i\asg i+M$. vERNUTXSYA NA~\stp{2}.

\st[vSTAVITX.] (pOISK BYL NEUDACHNYM.) eSLI~$|N|=M-1$, ALGORITM
ZAKANCHIVAETSYA PO PEREPOLNENIYU. (v DANNOM ALGORITME SCHITAETSYA, CHTO
TABLICA POLNA PRI~$|N|=M-1$, A NE PRI~$|N|=M$; SM.~UPR.~15.) v PROTIVNOM
SLUCHAE USTANOVITX~$|N|\asg|N|+1$, OTMETITX, CHTO UZEL~$|TABLE|[i]$ ZANYAT I
USTANOVITX~$|KEY|[i]\asg K$.
\algend

nA RIS.~41 POKAZANO, CHTO PROISHODIT PRI VSTAVKE S POMOSHCHXYU ALGORITMA~L SEMI
"NORVEZHSKIH" KLYUCHEJ~(11), IMEYUSHCHIH KODY HESHIROVANIYA 2, 7, 1, 8, 2, 8, 1
SOOTVETSTVENNO. pOSLEDNIE TRI KLYUCHA---|FEM|, |SEKS| I~|SYV|---SMESHCHENY PO
SRAVNENIYU SO SVOIMI NACHALXNYMI ADRESAMI~$h(K)$.
%%617

\picture{rIS. 41. lINEJNAYA OTKRYTAYA ADRESACIYA.}
\prog L.(pOISK S VSTAVKOJ PO OTKRYTOJ RASSEYANNOJ TABLICE.)
pROGRAMMA RABOTAET S KLYUCHAMI, ZANIMAYUSHCHIMI POLNOE SLOVO; ODNAKO NULEVOJ
KLYUCH ISPOLXZOVATX NELXZYA, TAK KAK NULX OBOZNACHAET SVOBODNUYU POZICIYU V
TABLICE. (dRUGAYA VOZMOZHNOSTX SOSTOIT V TOM, CHTOBY NALOZHITX USLOVIE
NEOTRICATELXNOSTI KLYUCHEJ, A V SVOBODNYE POZICII ZAPISATX~$-1$.)
pREDPOLAGAETSYA, CHTO RAZMER TABLICY~$M$---PROSTOE CHISLO I CHTO
UZEL~$|TABLE|[i]$ IMEET ADRES~$|TABLE|+i$, $0\le i < M$. dLYA USKORENIYA
VNUTRENNEGO CIKLA V YACHEJKU~$|TABLE|-1$ POMESHCHEN~0.
yaCHEJKA~|VACANCIES| SODERZHIT ZNACHENIE~$M-1-N$; $|rA|\equiv K$, $|rI1|\equiv i$.

tAKZHE DLYA USKORENIYA VNUTRENNEGO CIKLA PROGRAMMY IZ NEGO VYNESENA
PROVERKA~"$i<0$", TAK CHTO V NEM OSTALISX LISHX SUSHCHESTVENNYE CHASTI
SHAGOV~\stp{2} I~\stp{3}. pOISKOVAYA FAZA DLITSYA $(7C+9E+21-4S)u$, A VSTAVKA
POSLE NEUDACHNOGO POISKA TREBUET DOPOLNITELXNO~$9u$.
\code
START & LDX & K         & 1    & L1. hESHIROVANIE.
      & 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. pEREJTI K SLEDUYUSHCHEMU.
3H    & DEC1& 1         & C+E-1& $i\asg i-1$.
2H    & CMPA& TABLE,1   & C+E  & L2. sRAVNITX.
      & JE  & SUCCESS   & C+E  & vYHOD, ESLI $K=|KEY|[i]$.
      & LDX & TABLE,1   & C+E-S
      & JXNZ& 3B        & C+E-S& nA L3, ESLI V $|TABLE|[i]$ ZANYATO.
      & J1N & 8B        & E+1-S& Ha L3 S $i\asg M$, ESLI~$i=-1$.
4H    & LDX & VACANCIES & 1-S  & L4. vSTAVITX,
      & JXZ & OVERFLOW  & 1-S  & vYHOD PO PEREPOLN., ESLI $N=M-1$.
      & DECX& 1         & 1-S
      & STX & VACANCIES & 1-S  & uVELICHITX $N$ NA~1.
      & STA & TABLE, 1  & 1-S  & $|TABLE|[i]\asg K$.
\endcode
\progend
%% 618
kAK I V PROGRAMME~C, PO PEREMENNOJ~$C$ MY SUDIM O KOLICHESTVE  PROB, PO
PEREMENNOJ~$S$---BYL LI POISK UDACHNYM. pEREMENNOJ~$E$  MOZHNO PRENEBRECHX, TAK
KAK ONA RAVNA~1, LISHX ESLI PROIZVODILASX PROBA FIKTIVNOGO
UZLA~$|TABLE|[-1]$; EE SREDNEE ZNACHENIE RAVNO~$(C-1)/M$.

eKSPERIMENTY S LINEJNYM OPROBOVANIEM POKAZYVAYUT, CHTO |TOT METOD RABOTAET
PREKRASNO, POKA TABLICA NE SLISHKOM ZAPOLNENA, NO V KONCE KONCOV PROCESS
ZAMEDLYAETSYA, DLINNYE SERII PROB STANOVYATSYA VSE BOLEE CHASTYMI. pRICHINU
TAKOGO POVEDENIYA MOZHNO PONYATX, RASSMOTREV SLEDUYUSHCHUYU
GIPOTETICHESKUYU RASSEYANNUYU TABLICU ($M=19$, $N= 9$):
\picture{rIS. STR. 618}
zASHTRIHOVANYE KVADRATY OBOZNACHAYUT ZANYATYE POZICII. kLYUCH~$K$,  KOTORYJ
DOLZHEN BYTX VSTAVLEN V TABLICU SLEDUYUSHCHIM, POPADET  V ODNU IZ DESYATI
SVOBODNYH POZICIJ, NO NE S RAVNYMI VEROYATNOSTYAMI. v SAMOM DELE, $K$ BUDET
VSTAVLEN V POZICIYU~$11$, ESLI  $11\le h(K)\le 15$, A V POZICIYU~8 ON
POPADET LISHX PRI~$h(K)=8$.  sLEDOVATELXNO, VEROYATNOSTX POPASTX V
POZICIYU~11 V PYATX RAZ
BOLXSHE, CHEM V POZICIYU~8; DLINNYE SPISKI STREMYATSYA STATX ESHCH¸
DLINNEE.

nO |TO YAVLENIE SAMO PO SEBE NE OB®YASNYAET OTNOSITELXNO PLOHOGO POVEDENIYA
LINEJNOGO OPROBOVANIYA, TAK KAK ANALOGICHNYJ FAKT SPRAVEDLIV I DLYA
ALGORITMA~C. (rOST SPISKA IZ CHETYREH |LEMENTOV VCHETVERO VEROYATNEE ROSTA
SPISKA IZ ODNOGO |LEMENTA.) nASTOYASHCHIE TRUDNOSTI VOZNIKAYUT PRI VSTAVKE V
YACHEJKU VRODE~4 ILI~16 (SM.~(21)); DVA RAZLICHNYH SPISKA OB®EDINYAYUTSYA.
zAMETIM, CHTO V ALGORITME~C SPISKI UDLINYAYUTSYA NE BOLEE CHEM NA ODIN |LEMENT.
sLEDOVATELXNO, HARAKTERISTIKI LINEJNOGO OPROBOVANIYA REZKO UHUDSHAYUTSYA,
KOGDA $N$~PRIBLIZHAETSYA K~$M$.

dALEE V |TOM PARAGRAFE MY DOKAZHEM, CHTO SREDNEE CHISLO PROB, PROIZVODIMYH
ALGORITMOM~L, PRIBLIZHENNO RAVNO
$$
\eqalignno{
C'_N&\approx {1\over 2}\left(1+\left({1\over 1-\alpha}\right)^2\right)
\rem{(NEUDACHNYJ POISK);} & (22) \cr
C_N&\approx {1\over 2}\left(1+{1\over 1-\alpha}\right)
\rem{(UDACHNYJ POISK),} & (23)\cr
}
$$
GDE $\alpha=N/M$~ESTX KO|FFICIENT ZAPOLNENIYA TABLICY. tAK CHTO, ESLI
TABLICA ZAPOLNENA MENXSHE CHEM NA~75\%, PROGRAMMA~L RABOTAET POCHTI TAK ZHE
BYSTRO, KAK I PROGRAMMA~C, HOTYA POSLEDNYAYA I RABOTAET S NEPRAVDOPODOBNO
KOROTKIMI KLYUCHAMI. s DRUGOJ STORONY, KOGDA $\alpha$~PRIBLIZHAETSYA K~1,
LUCHSHEE, CHTO MOZHNO SKAZATX O PROGRAMME~L, |TO TO, CHTO ONA RABOTAET MEDLENNO,
NO VERNO.

%%619
v SAMOM DELE, ESLI~$N=M-1$, V TABLICE IMEETSYA LISHX ODNO VAKANTNOE MESTO,
PO|TOMU SREDNEE CHISLO PROB DLYA NEUDACHNOGO POISKA RAVNO~$(M+1)/2$; MY
DOKAZHEM, CHTO SREDNEE CHISLO PROB DLYA UDACHNOGO POISKA V ZAPOLNENNOJ TABLICE
PRIBLIZHENNO RAVNO~$\sqrt{\pi M/8}$.

yaVLENIE SKUCHIVANIYA, KOTOROE DELAET LINEJNOE OPROBOVANIE DOROGOSTOYASHCHIM V
SLUCHAE POCHTI ZAPOLNENNYH TABLIC, USUGUBLYAETSYA PRI ISPOLXZOVANII
HESHIROVANIYA DELENIEM, ESLI VPOLNE VEROYATNA POYAVLENIE POSLEDOVATELXNYH
ZNACHENIJ
KLYUCHEJ~$\set{K, K+1, K+2,~\ldots}$, TAK KAK |TI KLYUCHI BUDUT IMETX
POSLEDOVATELXNYE HESH-KODY. hESHIROVANIE UMNOZHENIEM RASSEET TAKIE GRUPPY
DOSTATOCHNO HOROSHO.

dRUGOJ SPOSOB RAZRESHENIYA PROBLEMY POSLEDOVATELXNYH KODOV HESHIROVANIYA
SOSTOIT V TOM, CHTOBY V SHAGE~L3 VMESTO~$i\asg i-1$ USTANOVITX~$i\asg i-c$.
gODITSYA LYUBAYA POLOZHITELXNAYA VELICHINA~$c$, \emph{VZAIMNO PROSTAYA S~$M$},
TAK KAK MY PROVERIM VSE POZICII TABLICY. eTO IZMENENIE SDELAET
PROGRAMMU~L NESKOLXKO MEDLENNEE I NE RAZRESHIT PROBLEMY SKUCHIVANIYA, TAK
KAK PO-PREZHNEMU BUDUT OBRAZOVYVATXSYA GRUPPY ZAPISEJ, UDALENNYH DRUG OT
DRUGA NA~$c$; FORMULY~(22) I~(23) OSTANUTSYA V SILE. pRAVDA,
TEPERX POYAVLENIE POSLEDOVATELXNYH KLYUCHEJ~$\set{K, K+1, K+2,~\ldots}$
IZ POMEHI PREVRATITSYA V POMOSHCHX.

hOTYA FIKSIROVANNOE ZNACHENIE~$c$ NE USTRANYAET SKUCHIVANIYA, MOZHNO SUSHCHESTVENNO
ULUCHSHITX SITUACIYU, ESLI SDELATX~$c$ ZAVISYASHCHIM OT~$K$. eTA IDEYA PRIVODIT
K VAZHNOMU IZMENENIYU ALGORITMA~L, KOTOROE VPERVYE OTKRYL gYUI DE~bALXBIN
[DOKTORSKAYA DISSERTACIYA, Calif. Inst. of Technology (1968), 149--150].
\alg D.(oTKRYTAYA ADRESACIYA S DVOJNYM HESHIROVANIEM.)
eTOT ALGORITM POCHTI SOVPADAET S ALGORITMOM~L, NO ISPOLXZUET NESKOLXKO INUYU
POSLEDOVATELXNOSTX PROB, VYCHISLYAYA DVE HESH-FUNKCII~$h_1(K)$  I~$h_2(K)$.
kAK OBYCHNO, $h_1(K)$~POROZHDAET VELICHINY OT~0 DO~$M-1$ VKLYUCHITELXNO; NO
ZNACHENIYA~$h_2(K)$ DOLZHNY LEZHATX OT~1 DO~$M-1$ I BYTX \emph{VZAIMNO PROSTY
S~$M$}. (nAPRIMER, ESLI $M$---PROSTOE CHISLO, TO $h_2(K)$~MOZHET BYTX
\emph{LYUBOJ} VELICHINOJ OT~1 DO~$M-1$ VKLYUCHITELXNO, ILI, ESLI~$M=2^m$,
TO~$h_2(K)$ MOZHET BYTX LYUBYM \emph{NECHETNYM} CHISLOM MEZHDU~1 I~$2^m-1$.)

\st[pERVOE HESHIROVANIE.] uSTANOVITX~$i\asg h_1(K)$.
\st[pERVAYA PROBA.] eSLI UZEL~$|TABLE|[i]$ SVOBODEN, TO PEREJTI
NA~\stp{6}. v PROTIVNOM SLUCHAE, ESLI~$|KEY|[i]=K$, ALGORITM
ZAKANCHIVAETSYA UDACHNO.

\st[vTOROE HESHIROVANIE.] uSTANOVITX~$c\asg h_2(K)$.
\st[pEREJTI K SLEDUYUSHCHEMU.] uSTANOVITX~$i\asg i-c$; ESLI TEPERX~$i<0$,
USTANOVITX~$i\asg i+M$.
\st[sRAVNENIE.] eSLI UZEL~$|TABLE|[i]$ SVOBODEN, TO PEREJTI
%%620
NA~\stp{6}. v PROTIVNOM SLUCHAE, ESLI~$|KEY|[i]=K$, ALGORITM ZAKANCHIVAETSYA
UDACHNO; V PROTIVNOM SLUCHAE VERNUTXSYA NA~\stp{4}.
\st[vSTAVKA.] eSLI~$|N|=M-1$, ALGORITM ZAKANCHIVAETSYA PO PEREPOLNENIYU. v
PROTIVNOM SLUCHAE USTANOVITX~$|N|\asg |N|+1$, POMETITX UZEL~$|TABLE|[i]$
KAK ZANYATYJ I USTANOVITX~$|KEY|[i]\asg K$.
\algend

dLYA VYCHISLENIYA~$h_2(K)$ BYLO PREDLOZHENO NESKOLXKO SPOSOBOV:
eSLI $M$---PROSTOE CHISLO I~$h_1(K)=K \bmod M$, MOZHNO POLOZHITX~$h_2(K)=1+(K
\bmod (M-1))$; NO TAK KAK $M-1$~CHETNO, BYLO BY LUCHSHE POLOZHITX~$h_2(K)=1+(K
\bmod (M-2))$. eTO NAVODIT NA MYSLX O TAKOM VYBORE~$M$, CHTOBY~$M$ I~$M-2$
BYLI PROSTYMI CHISLAMI-BLIZNECAMI, NAPRIMER~1021 I~1019. mOZHNO
VZYATX~$h_2(K)=1+(\floor{K/M} \bmod (M-2))$, IBO CHASTNOE~$\floor{K/M}$
MOZHNO POLUCHITX V REGISTRE KAK POBOCHNYJ PRODUKT VYCHISLENIYA~$h_1(K)$.

eSLI~$M=2^m$ I ISPOLXZUETSYA HESHIROVANIE UMNOZHENIEM, $h_2(K)$~MOZHNO
POLUCHITX, PROIZVODYA SDVIG ESHCHE NA $m$~BITOV VLEVO I VYPOLNYAYA OPERACIYU "ILI"
S~1, TAK CHTO K POSLEDOVATELXNOSTI KOMAND~(5) NUZHNO DOBAVITX
$$
\mixcode
ENTA  & 0   &  oCHISTITX |rA|.
SLB   & m   &  sDVIG |rAX| NA $m$~BITOV VLEVO.
ORR   & =1= &  $|rA|\asg |rA|\lor 1$.
\endmixcode
\eqno(24)
$$
eTO BYSTREE METODA DELENIYA.

v KAZHDOM IZ PREDLOZHENNYH VYSHE METODOV $h_1(K)$ I~$h_2(K)$ YAVLYAYUTSYA
"NEZAVISIMYMI" V TOM SMYSLE, CHTO NA RAZLICHNYH KLYUCHAH ZNACHENIYA OBEIH
FUNKCIJ~$h_1$  I~$h_2$ SOVPADAYUT S VEROYATNOSTXYU~$O(1/M^2)$, A NE S
VEROYATNOSTXYU~$O(1/M)$. eMPIRICHESKIE PROVERKI POKAZYVAYUT, CHTO CHISLO PROB V
ALGORITME~D PRI NEZAVISIMYH HESH-FUNKCIYAH, V SUSHCHNOSTI, NE OTLICHIMO OT CHISLA
PROB, KOTOROE POTREBOVALOSX, ESLI BY KLYUCHI VSTAVLYALISX V TABLICU
SLUCHAJNO; "OKUCHIVANIYA", IMEYUSHCHEGO MESTO V ALGORITME~L, ZDESX PRAKTICHESKI NET.

mOZHNO TAKZHE DOPUSTITX ZAVISIMOSTX~$h_2(K)$ OT~$h_1(K)$ (KAK PREDLOZHIL V
1968~G.\ g.~kNOTT); NAPRIMER, ESLI $M$---PROSTOE CHISLO, POLOZHIM
$$
h_2(K)=\cases{
1, & ESLI $h_1(K)=0$;\cr
M-h_1(K), & ESLI $h_1(K)>0$.\cr
}
\eqno(25)
$$
eTOT METOD BYSTREE POVTORNOGO DELENIYA, NO ON VSE ZHE PRIVODIT K
\emph{VTORICHNOMU OKUCHIVANIYU,} TREBUYA NESKOLXKO BOLXSHE PROB IZ-ZA
UVELICHENIYA VEROYATNOSTI TOGO, CHTO DVA ILI BOLEE KLYUCHEJ POSLEDUYUT ODNIM I
TEM ZHE PUTEM. fORMULY, VYVEDENNYE NIZHE, MOZHNO ISPOLXZOVATX, CHTOBY
OPREDELITX, PEREVESHIVAET LI VYIGRYSH VO VREMENI HESHIROVANIYA POTERI NA PROBAH.

%% 621

aLGORITMY~L I~D OCHENX POHOZHI, NO IMEYUT I DOSTATOCHNO RAZLICHIJ, PO|TOMU
POLEZNO SRAVNITX VREMENA RABOTY SOOTVETSTVUYUSHCHIH PROGRAMM DLYA~\MIX.


\prog D.(oTKRYTAYA ADRESACIYA S DVOJNYM HESHIROVANIEM.)
tAK KAK |TA PROGRAMMA VESXMA NAPOMINAET PROGRAMMU~L, ONA PRIVODITSYA BEZ
KOMMENTARIEV. zDESX~$|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
     &smrh&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
sCHETCHIKI CHASTOT~$A$, $C$, $S1$, $S2$ IMEYUT TOT ZHE SMYSL, CHTO I
V PROGRAMME~C. sREDNEE ZNACHENIE PEREMENNOJ~$B$ PRIMERNO RAVNO~$(C-1)/2$.
(eSLI SUZITX DIAPAZON~$h_2(K)$, SKAZHEM,
DO~$1\le h_2(K)\le {1\over2} M$,
ZNACHENIE~$B$ SOSTAVILO BY LISHX~$(C-1)/4$, VEROYATNO, UVELICHENIE CHISLA PROB
NE SVEDET NA NET |TO UVELICHENIE SKOROSTI.) eSLI V TABLICE $N=\alpha M$~KLYUCHEJ,
SREDNEE ZNACHENIE~$A$, RAZUMEETSYA, RAVNO~$\alpha$ DLYA NEUDACHNOGO
POISKA I~1 DLYA UDACHNOGO. kAK I V ALGORITME~C, SREDNEE ZNACHENIE~$S1$ DLYA
NEUDACHNOGO POISKA SOSTAVLYAET~$1-{1\over2}((N-1)/M)\approx
1-{1\over2}\alpha$. tRUDNO TOCHNO OPREDELITX SREDNEE CHISLO PROB, ODNAKO
|MPIRICHESKIE PROVERKI POKAZYVAYUT HOROSHEE SOGLASIE S VYVEDENNYMI NIZHE
FORMULAMI DLYA "RAVNOMERNOGO OPROBOVANIYA":
$$
\eqalignno{
C'_N&={M+1\over M+1-N}\approx(1-\alpha)^{-1} \rem{(NEUDACHNYJ POISK)};&(26)\cr
C_N&={M+1\over N}(H_{M+1}-H_{M+1-N}) \approx-\alpha^{-1}\ln (1-\alpha)
\rem{(UDACHNYJ POISK)},&(27)\cr
}
$$
ESLI~$h_1(K)$ I~$h_2(K)$ NEZAVISIMY. kOGDA ZHE $h_2(K)$~ZAVISIT OT~$h_1(K)$,
 KAK V~(25), VTORICHNOE OKUCHIVANIE VYZYVAET UVELICHENIE SREDNIH
%%622
ZNACHENIJ DO
$$
\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
}
$$
(sM.~UPR.~44.) zAMETIM, CHTO, KOGDA TABLICA ZAPOLNYAETSYA, T.~E.~KOGDA $N
$~STREMITSYA K~$M$, ZNACHENIE~$C_N$ PRIBLIZHAETSYA K~$H_{M+1}-1$,
A~$C'_N$---K~$H_{M+1}-{1\over2}$; |TO MNOGO LUCHSHE, CHEM V SLUCHAE ALGORITMA~L,
NO NE STOLX HOROSHO, KAK V METODAH CEPOCHEK.

pOSKOLXKU V ALGORITME~L PROBY ZANIMAYUT NESKOLXKO MENXSHE VREMENI, DVOJNOE
HESHIROVANIE PREDPOCHTITELXNO LISHX PRI ZAPOLNENNOJ TABLICE. nA RIS.~42
SRAVNIVAYUTSYA SREDNIE VREMENA RABOTY PROGRAMM~L, D I MODIFICIROVANNOJ
PROGRAMMY~D (PRICHEM |TA MODIFIKACIYA VLECHET ZA SOBOJ VTORICHNOE SKUCHIVANIE):
MY ZAMENYAEM DOVOLXNO MEDLENNOE VYCHISLENIE~$h_2(K)$ V STROKAH~10--13 NA TRI
KOMANDY
$$
\mixcode
ENN2  & -M-1, 1 & $c\asg M-i$.
J1NZ  & *+2
ENT2  & 0       & eSLI $i=0$, $c\asg 1$.
\endmixcode
\eqno(30)
$$
\picture{rIS. 42.  vREMYA UDACHNOGO POISKA DLYA TREH SHEM OTKRYTOJ ADRESACII.}
%%623
v DANNOM SLUCHAE VTORICHNOE SKUCHIVANIE LUCHSHE NEZAVISIMOGO POVTORNOGO HESHIROVANIYA.

nA DVOICHNOJ evm MY MOGLI BY INYM SPOSOBOM USKORITX VYCHISLENIE~$h_2(K)$,
ZAMENIV STROKI~10--13, SKAZHEM, NA
$$
\mixcode
AND  & =511=   & $|rA|\asg |rA| \bmod 512$.
STA  & *+1(0:2)
ENT2 & *       & $c\asg |rA|+1$.
\endmixcode
\eqno(31)
$$
ESLI $M$---PROSTOE CHISLO, BOLXSHEE~512. eTA IDEYA, PREDLOZHENNAYA bELLOM I
kAM\'A [{\sl CACM,\/} {\bf 13} (1970), 675--677], NEZAVISIMO PRIDUMAVSHIMI
ALGORITM~D, POZVOLYAET IZBEZHATX VTORICHNOGO SKUCHIVANIYA BEZ ZATRAT NA
POVTORNOE DELENIE.

bYLO PREDLOZHENO MNOGO DRUGIH POSLEDOVATELXNOSTEJ PROB V KACHESTVE ULUCHSHENIJ
ALGORITMA~L, NO, PO-VIDIMOMU, NI ODNA IZ NIH NE LUCHSHE ALGORITMA~D. (bYTX
MOZHET, ISKLYUCHENIE SOSTAVLYAET METOD, OPISANNYJ V UPR.~20.)
\picture{ rIS. 43. sKOLXKO RAZ KOMPILYATOR ISHCHET IMENA PEREMENNYH V TIPICHNOM
SLUCHAE. iMENA VYPISANY SLEVA NAPRAVO V PORYADKE IH PERVOGO  POYAVLENIYA.}
\section iZMENENIE, PREDLOZHENNOE bRENTOM. rICHARD bRENT NASHEL TAKOJ SPOSOB
IZMENENIYA ALGORITMA~D, CHTOBY SREDNEE VREMYA UDACHNOGO POISKA OSTAVALOSX
OGRANICHENNYM PO MERE ZAPOLNENIYA TABLICY. eGO METOD OSNOVAN NA TOM FAKTE,
CHTO VO MNOGIH PRILOZHENIYAH
%%624
UDACHNYJ POISK PROIZVODITSYA GORAZDO CHASHCHE VSTAVOK; PO|TOMU ON PREDLAGAET
DELATX BOLXSHE RABOTY PRI VSTAVKE |LEMENTA, nepeMESHCHAYA ZAPISI, CHTOBY
UMENXSHITX OZHIDAEMOE VREMYA VYBORKI.
[{\sl CACM,\/} {\bf 16} (1973), 105--109.]

nAPRIMER, NA RIS.~43 POKAZANO, SKOLXKO RAZ TOT ILI INOJ IDENTIFIKATOR
VSTRECHALSYA V TIPICHNOJ PROCEDURE NA~PL/1. sUDYA PO |TIM DANNYM, KOMPILYATOR
S~PL/1, ISPOLXZUYUSHCHIJ RASSEYANNUYU TABLICU DLYA HRANENIYA IMEN PEREMENNYH,
BUDET ISKATX MNOGIE IMENA PYATX ILI BOLEE RAZ, A VSTAVLYATX IH LISHX ODNAZHDY.
 aNALOGICHNO bELL I~kAM\'A OBNARUZHILI, CHTO KOMPILYATOR S~kOBOLA ISPOLXZOVAL
SVOJ ALGORITM TABLIC SIMVOLOV $10988$~RAZ VO VREMYA KOMPILYACII PROGRAMMY I
SOVERSHIL LISHX $735$~VSTAVOK, T.~E.~NA ODIN NEUDACHNYJ POISK PRIHODILOSX
PRIMERNO 14~UDACHNYH.
iNOGDA TABLICA SOZDAETSYA TOLXKO ODIN RAZ (NAPRIMER, TABLICA SIMVOLICHESKIH
KODOV OPERACIJ V AVTOKODE) I ISPOLXZUETSYA POSLE |TOGO ISKLYUCHITELXNO DLYA
VYBORKI.

bRENT PREDLOZHIL SLEDUYUSHCHIM OBRAZOM IZMENITX PROCESS VSTAVKI V ALGORITME~D.
pREDPOLOZHIM, CHTO PRI NEUDACHNOM POISKE BYLI OPROBOVANY YACHEJKI
$$
p_0, p_1,~\ldots, p_{t-1}, p_t,
$$
GDE~$p_j=(h_1(K)-jh_2(K))\bmod M$ I UZEL~$|TABLE|[p_t]$ PUST. eSLI~$t\le
1$, MY, KAK OBYCHNO, VSTAVLYAEM~$K$ V POZICIYU~$p_t$, NO ESLI~$t\ge2$,
VYCHISLYAEM~$c_0=h_2(K_0)$, GDE~$K_0=|KEY|[p_0]$, I SMOTRIM, SVOBODNO LI
V~$|TABLE| [(p_0-c_0)\bmod M$]. eSLI USLOVIE VYPOLNENO, POMESHCHAEM V DANNYJ
UZEL SODERZHIMOE YACHEJKI~$|TABLE|[p_0]$ I VSTAVLYAEM~$K$ V POZICIYU~$p_0$. eTO
UVELICHIVAET VREMYA VYBORKI $K_0$ NA ODIN SHAG, NO UMENXSHAET VREMYA
VYBORKI~$K$ NA $t\ge2$~SHAGOV.  vYIGRYSH NALICO. aNALOGICHNO, ESLI
V~$|TABLE|[(p_0-c_0)\bmod M]$ ZANYATO I~$t\ge3$, MY PROBUEM YACHEJKU~$|TABLE|
[(p_0-2c_0)\bmod M]$;
ESLI I TAM ZANYATO, VYCHISLYAEM~$c_1=h_2(|KEY|[p_1])$ I PROBUEM
$|TABLE|[(p_1-c_1)\bmod M]$ I~T.~D. vOOBSHCHE,
PUSTX~$c_j=h_2(|KEY|[p_j])$ I~$p_{j,k}=(p_j-kc_j)\bmod M$; ESLI
POZICII~$|TABLE|[p_{j,k}]$ OKAZALISX ZANYATYMI PRI VSEH~$j, k$, TAKIH,
CHTO~$j+k<r$, I ESLI~$t\ge r+1$, PROSMATRIVAEM   UZLY~$|TABLE|[p_{0,r}]$,
$|TABLE|[p_{1, r-1}]$,~\dots, $|TABLE|[p_{r-1, 1}]$. eSLI PERVOJ SVOBODNOJ
OKAZALASX POZICIYA~$p_{j,r-j}$,
USTANAVLIVAEM~$|TABLE|[p_{j, r-j}]\asg |TABLE|[p_j]$ I
VSTAVLYAEM~$K$ V POZICIYU~$p_j$.

kAK YAVSTVUET IZ ANALIZA bRENTA, SREDNEE CHISLO PROB V PROCESSE UDACHNOGO
POISKA UMENXSHILOSX (SM.~RIS.~44) I EGO MAKSIMALXNOE ZNACHENIE PRIBLIZHENNO
RAVNO~$2.49$.

chISLO~$t+1$ PROB PRI NEUDACHNOM POISKE V REZULXTATE PREDLOZHENNOGO IZMENENIYA
NE UMENXSHILOSX; ONO OSTALOSX NA UROVNE,  UKAZANNOM FORMULOJ~(26), I
DOSTIGAET~$(M+1)/2$ DLYA ZAPOLNENNOJ  TABLICY. pRI VSTAVKE FUNKCIYU~$h_2$
PRIHODITSYA V SREDNEM VYCHISLYATX
%%625
$\alpha^2+\alpha^5+{1\over3}\alpha^6+\ldots$~RAZ. sOGLASNO ANALIZU
bRENTA, PRI~$\alpha\to 1$, |TA VELICHINA IMEET PORYADOK~$\sqrt{M}$. nAKONEC,
KOGDA MY RESHAEM, KAK PROIZVESTI VSTAVKU, SOVERSHAETSYA OKOLO
$\alpha^2+\alpha^4+{4\over3}\alpha^5+\alpha^6+\ldots$~DOPOLNITELXNYH PROB.

\section uDALENIYA. mNOGIE PROGRAMMISTY SVYATO VERYAT V ALGORITMY I
OCHENX UDIVLYAYUTSYA, OBNARUZHIV, CHTO \emph{OCHEVIDNYJ SPOSOB UDALENIYA ZAPISEJ
IZ RASSEYANNOJ TABLICY NE RABOTAET.} nAPRIMER, PRI POPYTKE UDALITX
KLYUCH~|EN| (SM.~RIS.~41) NELXZYA PROSTO POMETITX |TU POZICIYU V TABLICE KAK
SVOBODNUYU, IBO DRUGOJ KLYUCH~|FEM| VNEZAPNO OKAZHETSYA POTERYANNYM! (vSPOMNIM,
CHTO EN I FEM IMEYUT ODINAKOVYE HESH-KODY. pRI POISKE~|FEM| MY NATKNEMSYA NA
SVOBODNYJ UZEL, CHTO SVIDETELXSTVUET O TOM, CHTO POISK NEUDACHEN.)
aNALOGICHNOE SOOBRAZHENIE SPRAVEDLIVO DLYA ALGORITMA~C, V KOTOROM IMEET
MESTO SRASTANIE SPISKOV; PREDSTAVXTE SEBE UDALENIE KLYUCHEJ~|TO| I~|FIRE|
(SM.~RIS.~40).

vOOBSHCHE GOVORYA, MOZHNO PROIZVODITX UDALENIYA, POMESHCHAYA V SOOTVETSTVUYUSHCHUYU
YACHEJKU SPECIALXNOE ZNACHENIE, T.~E.~IMEYA TRI TIPA POZICIJ V TABLICE:
SVOBODNYE, ZANYATYE I UDALENNYE. pRI POISKE KLYUCHA UDALENNYE POZICII NUZHNO
TRAKTOVATX KAK ZANYATYE. v SLUCHAE NEUDACHNOGO POISKA KLYUCH MOZHNO VSTAVITX V
PERVUYU VSTRECHENNUYU UDALENNUYU ILI SVOBODNUYU POZICIYU.

oDNAKO |TA IDEYA PRIMENIMA TOLXKO PRI OCHENX REDKIH UDALENIYAH, POTOMU CHTO
ODNAZHDY ZANYATAYA POZICIYA NE MOZHET SNOVA STATX SVOBODNOJ. pOSLE DLINNOJ
POSLEDOVATELXNOSTI VSTAVOK I UDALENIJ VSE SVOBODNOE PROSTRANSTVO V KONCE
KONCOV ISCHEZNET I KAZHDYJ NEUDACHNYJ POISK BUDET TREBOVATX $M$~PROB!
kROME TOGO, PROBY POTREBUYUT BOLXSHE VREMENI, TAK KAK V SHAGE~D4
NEOBHODIMO PROVERYATX, NE VERNULOSX LI~$i$ K SVOEMU NACHALXNOMU ZNACHENIYU, A
CHISLO PROB PRI UDACHNOM POISKE VOZRASTET S~$C_N$ DO~$C'_N$.

eSLI ISPOLXZUETSYA LINEJNOE OPROBOVANIE (T.~E.~ALGORITM~L), MOZHNO
DEJSTVOVATX RACIONALXNEE, PRI USLOVII CHTO MY SOGLASNY POTRATITX NEKOTORYE
DOPOLNITELXNYE USILIYA NA UDALENIYA.

\alg R.(uDALENIE PRI LINEJNOM OPROBOVANII.)
nASTOYASHCHIJ ALGORITM UDALYAET ZAPISX IZ DANNOJ POZICII~$|TABLE| [i]$
OTKRYTOJ RASSEYANNOJ TABLICY, POSTROENNOJ S POMOSHCHXYU ALGORITMA~L.

\st[oSVOBODITX YACHEJKU.] oTMETITX YACHEJKU~$|TABLE|[i]$ KAK SVOBODNUYU I
USTANOVITX~$j\asg i$.

\st[uMENXSHITX~$i$.] uSTANOVITX~$i\asg i-1$ I, ESLI ZNACHENIE~$i$ STALO
OTRICATELXNYM, USTANOVITX~$i\asg i+M$.

\st[pROVERITX~$|TABLE|[i]$.] eSLI V~$|TABLE|[i]$ SVOBODNO, ALGORITM
ZAVERSHAETSYA.  v PROTIVNOM SLUCHAE USTANOVITX
%% 626
$r\asg h(|KEY| [i])$---PERVONACHALXNYJ HESH-KOD KLYUCHA, HRANYASHCHEGOSYA TEPERX V
POZICII~$i$. eSLI~$i\le r<j$, ILI~$r<j<i$, ILI~$j<i\le r$ (DRUGIMI
SLOVAMI, ESLI $r$~LEZHIT CIKLICHESKI MEZHDU~$i$ I~$j$), VERNUTXSYA NA~\stp{2}.

\st[pEREMESTITX ZAPISX.] uSTANOVITX~$|TABLE| [j]\asg |TABLE| [i]$ I
VERNUTXSYA NA~\stp{1}.
\algend

v UPR.~22 POKAZANO, CHTO |TOT ALGORITM NE VYZYVAET UHUDSHENIYA
HARAKTERISTIK, T.E.~SREDNEE CHISLO PROB, PREDSKAZANNOE FORMULAMI~(22)
I~(23), OSTAETSYA PREZHNIM. (bOLEE SLABYJ REZULXTAT DLYA UDALENIYA IZ DEREVA
BYL DOKAZAN V TEOREME~6.2.2H.) oDNAKO SPRAVEDLIVOSTX ALGORITMA~R SILXNO
ZAVISIT OT TOGO FAKTA, CHTO ISPOLXZUETSYA LINEJNOE OPROBOVANIE; V SLUCHAE
ALGORITMA~D NE SUSHCHESTVUET ANALOGICHNOJ PROCEDURY UDALENIYA.

rAZUMEETSYA, ESLI ISPOLXZUETSYA METOD CEPOCHEK I DLYA KAZHDOGO HESH-KODA IMEETSYA
OTDELXNYJ SPISOK, UDALENIE NE YAVLYAETSYA PROBLEMOJ, TAK KAK SVODITSYA PROSTO
K UDALENIYU IZ SVYAZANNOGO LINEJNOGO SPISKA. uDALENIYA DLYA ALGORITMA~C
OBSUZHDAYUTSYA V UPR.~23.

\section *aNALIZ ALGORITMOV. pRI HESHIROVANII MY POLAGAEMSYA NA
VEROYATNOSTNYE ZAKONY, PO|TOMU OSOBENNO VAZHNO ZNATX POVEDENIE METODOV
HESHIROVANIYA V SREDNEM. nAIHUDSHIJ SLUCHAJ V |TIH ALGORITMAH POCHTI
NEMYSLIMO PLOH, TAK CHTO NAM NEOBHODIMA UVERENNOSTX V TOM, CHTO POVEDENIE V
SREDNEM YAVLYAETSYA OCHENX HOROSHIM.

pREZHDE CHEM PRISTUPITX K ANALIZU LINEJNOGO OPROBOVANIYA I~T.~P., RASSMOTRIM
VESXMA PRIBLIZHENNUYU MODELX DANNOJ SITUACII, KOTORUYU MOZHNO NAZVATX
\dfn{RAVNOMERNYM HESHIROVANIEM} (SR.~S~W.~W.~Peterson, {\sl IBM J.~Research
\& Development,\/} {\bf 1} (1957), 135--136). v DANNOJ MODELI
PREDPOLAGAETSYA, CHTO KLYUCHI POPADAYUT
V SLUCHAJNYE POZICII TABLICY, TAK CHTO VSE $\perm{M}{N}$~VOZMOZHNYH
KONFIGURACIJ IZ $N$~ZANYATYH I~$M-N$~SVOBODNYH YACHEEK RAVNOVEROYATNY. eTA
MODELX SOVERSHENNO NE UCHITYVAET VLIYANIYA PERVICHNOGO ILI VTORICHNOGO
OKUCHIVANIYA; V SUSHCHNOSTI, PREDPOLAGAETSYA, CHTO ZANYATOSTX LYUBOJ YACHEJKI NE
ZAVISIT OT. ZANYATOSTI DRUGIH. dLYA RASSMATRIVAEMOJ MODELI VEROYATNOSTX TOGO,
CHTO DLYA VSTAVKI $(N+1)\hbox{-GO}$~|LEMENTA TREBUETSYA ROVNO $r$~PROB,
RAVNA CHISLU KONFIGURACIJ, V KOTORYH ZANYATO $r-1$~DANNYH YACHEEK, A
ESHCHE ODNA DANNAYA YACHEJKA SVOBODNA, DELENNOMU NA~$\perm{M}{N}$, T.~E.
$$
P_r=\perm{M-r}{N-r+1}\bigg/\perm{M}{N};
$$
SLEDOVATELXNO, SREDNEE CHISLO PROB DLYA RAVNOMERNOGO HESHIROVANIYA
%%627
SOSTAVLYAET
$$
\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
}
$$
(mY UZHE RESHALI, V SUSHCHNOSTI, TU ZHE ZADACHU, VOZNIKAYUSHCHUYU V SVYAZI SO SLUCHAJNOJ
VYBORKOJ; UPR.~3.4.2-5.) pOLAGAYA~$\alpha=N/M$, TOCHNUYU FORMULU DLYA~$C'_N$
MOZHNO PRIBLIZHENNO ZAMENITX NA
$$
{1\over 1-\alpha}=1+\alpha+\alpha^2+\alpha^3+\ldots\,.
\eqno(33)
$$
eTOMU RYADU MOZHNO DATX GRUBUYU INTUITIVNUYU INTERPRETACIYU:
S VEROYATNOSTXYU~$\alpha$ NUZHNA BOLEE CHEM ODNA PROBA, S
VEROYATNOSTXYU~$\alpha^2$---BOLEE CHEM DVE I~T.~D. sOOTVETSTVUYUSHCHEE SREDNEE
CHISLO PROB PRI UDACHNOM POISKE RAVNO
$$
\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
}
$$
kAK OTMECHALOSX VYSHE, MNOGOCHISLENNYE TESTY POKAZALI, CHTO ALGORITM~D S
DVUMYA NEZAVISIMYMI HESH-FUNKCIYAMI VEDET SEBYA,  PO SUSHCHESTVU, KAK RAVNOMERNOE
HESHIROVANIE, I DLYA VSEH PRAKTICHESKIH NUZHD MOZHNO ISPOLXZOVATX
FORMULY~(32)--(34). nA SAMOM DELE l.~gYUIBA I e.~sEMEREDI UDALOSX DOKAZATX
TRUDNUYU TEOREMU O TOM, CHTO DVOJNOE HESHIROVANIE ASIMPTOTICHESKI
(PRI~$M\to\infty$) |KVIVALENTNO RAVNOMERNOMU [BUDET OPUBLIKOVANO].

nA |TOM ANALIZ RAVNOMERNOGO HESHIROVANIYA ZAVERSHAETSYA. chTOBY IZUCHATX
LINEJNOE OPROBOVANIE I DRUGIE SPOSOBY RAZRESHENIYA KOLLIZII, NUZHNO STROITX
TEORIYU INYM, BOLEE REALISTICHESKIM SPOSOBOM. v VEROYATNOSTNOJ MODELI,
KOTORUYU MY BUDEM ISPOLXZOVATX DLYA |TOJ CELI, PREDPOLAGAETSYA, CHTO VSE
$M^N$~VOZMOZHNYH HESH-POSLEDOVATELXNOSTEJ
$$
a_1\ a_2\ \ldots\ a_N, \qquad 0\le a_j <M,
\eqno(35)
$$
RAVNOVEROYATNY. zDESX $a_j$~OBOZNACHAET PERVONACHALXNYJ HESH-ADRES KLYUCHA,
VSTAVLENNOGO V TABLICU V POZICIYU~$j$, kAK I VYSHE, SREDNEE
%%628
CHISLO PROB V SLUCHAE UDACHNOGO POISKA PRI LYUBOM DANNOM ALGORITME
OBOZNACHIM CHEREZ~$C_N$. eTO ESTX SREDNEE CHISLO PROB, NUZHNYH DLYA NAHOZHDENIYA
$k\hbox{-GO}$~KLYUCHA, USREDNENNOE PO~$1\le k\le N$ PRI RAVNOVEROYATNYH
KLYUCHAH I PO VSEM HESH-POSLEDOVATELXNOSTYAM~(35), KOTORYE TAKZHE SCHITAYUTSYA
RAVNOVEROYATNYMI. aNALOGICHNO, SREDNEE CHISLO PROB, NEOBHODIMYH DLYA VSTAVKI
$N\hbox{-GO}$~KLYUCHA, PRI USLOVII CHTO VSE POSLEDOVATELXNOSTI~(35)
RAVNOVEROYATNY, OBOZNACHIM CHEREZ~$C'_{N-1}$; |TO ESTX SREDNEE CHISLO PROB V
NEUDACHNOM POISKE, ESLI V TABLICE $N-1$~|LEMENTOV. eSLI ISPOLXZUETSYA
OTKRYTAYA ADRESACIYA, TO
$$
C_N={1\over N}\sum_{0\le k < N} C'_k,
\eqno (36)
$$
TAK CHTO, ZNAYA ODNU VELICHINU, MOZHNO POLUCHITX DRUGUYU, KAK BYLO SDELANO V~(34).

sTROGO GOVORYA, DAZHE |TA BOLEE PRAVILXNAYA MODELX IMEET DVA NEDOSTATKA.
vO-PERVYH, NE VSE HESH-POSLEDOVATELXNOSTI RAVNOVEROYATNY, POTOMU CHTO SAMI
KLYUCHI YAVLYAYUTSYA RAZLICHNYMI. eTO DELAET VEROYATNOSTX RAVENSTVA~$a_1=a_2$
NESKOLXKO MENXSHEJ, CHEM~$1/M$, ODNAKO RAZNOSTXYU OBYCHNO MOZHNO PRENEBRECHX,
TAK KAK KOLICHESTVO VSEH VOZMOZHNYH KLYUCHEJ V TIPICHNOM SLUCHAE MNOGO
BOLXSHE~$M$. (sM.~UPR.~24.) dALEE, HOROSHAYA HESH-FUNKCIYA BUDET
ISPOLXZOVATX NESLUCHAJNOSTX OBYCHNYH DANNYH, DELAYA RAVENSTVO~$a_1=a_2$
ESHCHE MENEE VEROYATNYM; V REZULXTATE NASHI OCENKI CHISLA PROB BUDUT,
 PESSIMISTICHESKIMI. dRUGAYA NETOCHNOSTX DANNOJ MODELI UKAZANA NA RIS.~43:
KLYUCHI, POYAVIVSHIESYA RANEE (ZA NEKOTORYMI ISKLYUCHENIYAMI), RAZYSKIVAYUTSYA
CHASHCHE. sLEDOVATELXNO, NASHI OCENKI~$C_N$ BUDUT VDVOJNE PESSIMISTICHESKIMI, A
ALGORITMY NA PRAKTIKE DOLZHNY RABOTATX NESKOLXKO LUCHSHE, CHEM PREDSKAZYVAET
NASH ANALIZ.

pOSLE |TOJ PREAMBULY MY GOTOVY VYPOLNITX "TOCHNYJ" ANALIZ LINEJNOGO OPROBOVANIYA%
\note{1}%
{zDESX AVTOR NE MOZHET UDERZHATXSYA OT BIOGRAFICHESKOGO ZAMECHANIYA.
vPERVYE PREDLAGAEMYJ VYVOD BYL SFORMULIROVAN MNOYU V 1962~G., VSKORE
POSLE NACHALA RABOTY NAD "iSKUSSTVOM PROGRAMMIROVANIYA DLYA evm". mOJ
PERVYJ USPESHNYJ ANALIZ NETRIVIALXNOGO ALGORITMA OKAZAL SILXNOE VLIYANIE NA
STRUKTURU |TIH KNIG. mOG LI YA DUMATX, CHTO PROJDET BOLEE DESYATI LET,
PREZHDE CHEM |TOT VYVOD POPADET V PECHATX!
}.
 chEREZ~$f(M,N)$ OBOZNACHIM CHISLO HESH-POSLEDOVATELXNOSTEJ~(35), TAKIH, CHTO
POZICIYA~0 TABLICY BUDET SVOBODNA POSLE VSTAVKI KLYUCHEJ S POMOSHCHXYU
ALGORITMA~L. iZ KRUGOVOJ SIMMETRII LINEJNOGO OPROBOVANIYA SLEDUET, CHTO
POZICIYA~0 SVOBODNA S TOJ ZHE VEROYATNOSTXYU, CHTO I LYUBAYA DRUGAYA POZICIYA,
T.~E.~S VEROYATNOSTXYU~$1-N/M$; INYMI SLOVAMI,
$$
f(M,N)=\left(1-{N\over M}\right)M^N.
\eqno(37)
$$
%%629
pO OPREDELENIYU POLAGAEM~$f(0,0)=1$. chEREZ~$g(M, N, k)$ OBOZNACHIM CHISLO
HESH-POSLEDOVATELXNOSTEJ~(35), TAKIH, CHTO ALGORITM OSTAVLYAET POZICIYU~0
SVOBODNOJ, POZICII S~1 PO~$k$ ZANYATYMI, A POZICIYU~$k+1$ SVOBODNOJ. iMEEM
$$
g(M, N, k)=\perm{N}{k}f(k+1, k)f(M-k-1, N-k),
\eqno (38)
$$
IBO VSE TAKIE POSLEDOVATELXNOSTI SOSTOYAT IZ DVUH PODPOSLEDOVATELXNOSTEJ.
oDNA (SODERZHASHCHAYA $k$~|LEMENTOV~$a_i\le k$) OSTAVLYAET POZICIYU~0 SVOBODNOJ I
POZICII S~1 PO~$k$ ZANYATYMI, A DRUGAYA (SODERZHASHCHAYA
$N-k$~|LEMENTOV~$a_j\ge k+1$) OSTAVLYAET POZICIYU~$k+1$ SVOBODNOJ. sUSHCHESTVUET
$f(k+1, k)$~POSLEDOVATELXNOSTEJ PERVOGO
TIPA I $f(M-k-1, N-k)$~VTOROGO I $\perm{N}{k}$~SPOSOBOV SMESHATX DVE
TAKIE PODPOSLEDOVATELXNOSTI. nAKONEC, POLOZHIM~$P_k$ RAVNYM VEROYATNOSTI
TOGO, CHTO PRI VSTAVKE $(N+1)\hbox{-GO}$~|LEMENTA PONADOBITSYA ROVNO
$(k+1)$~PROB; MOZHNO POKAZATX (SM.~UPR.~25), CHTO
$$
P_k=M^{-N}(g(M, N, k)+g(M, N, k+1)+\cdots+g(M, N, N)).
\eqno(39)
$$
tEPERX $C'_N=\sum_{0\le k\le N} (k+1)P_k$; PODSTANOVKA
SOOTNOSHENIJ~(36)--(39) I UPROSHCHENIYA DAYUT SLEDUYUSHCHIJ REZULXTAT.

\proclaim tEOREMA k. sREDNEE CHISLO PROB, NUZHNYH PRI ISPOLXZOVANII
ALGORITMA~L (ESLI SCHITATX, CHTO VSE~$M^N$
HESH-POSLEDOVATELXNOSTEJ~(35) RAVNOVEROYATNY), RAVNO
$$
\eqalignno{
C_N&={1\over2}(1+Q_0(M, N-1))  \rem{(UDACHNYJ POISK);} & (40)\cr
C'_N&={1\over2}(1+Q_1(M, N))     \rem{(NEUDACHNYJ POISK),} & (41)\cr
}
$$
GDE
$$
\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 pODROBNYE VYCHISLENIYA PROVEDENY V UPR.~27.\endmark

pOYAVLYAYUSHCHAYASYA V TEOREME FUNKCIYA~$Q_r(M, N)$ VYGLYADIT NE OCHENX IZYASHCHNO, NO V
DEJSTVITELXNOSTI RABOTATX S NEJ MOZHNO. iMEEM
$$
N^k-\perm{k}{2}N^{k-1}\le N(N-1)\ldots(N-k+1)\le N^k;
$$
%%630
SLEDOVATELXNO, ESLI~$N/M=\alpha$, TO
$$
\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
}
$$
T.~E.
$$
{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)
$$
eTO SOOTNOSHENIE DAET NAM HOROSHUYU OCENKU~$a_r(M, N)$, KOGDA $M$~VELIKO
I~$\alpha$ NE SLISHKOM BLIZKO K~1. (nIZHNYAYA OCENKA BLIZHE K ISTINE, CHEM
VERHNYAYA.) eSLI~$\alpha$ PRIBLIZHAETSYA K~1, FORMULA~(43) STANOVITSYA
BESPOLEZNOJ, NO, K SCHASTXYU, $a_0(M, M-1)$ ESTX FUNKCIYA~$a(M)$,
ASIMPTOTICHESKOE POVEDENIE KOTOROJ MY DETALXNO IZUCHILI V P.~1.2.11.3;
A~$a_1(M, M-1)$ PROSTO RAVNO~$M$ (UPR.~50).

g.~shAJ~ML.\ I~v.~sPRUT IZBRALI DRUGOJ PODHOD K ANALIZU LINEJNOGO
OPROBOVANIYA [{\sl CACM,\/} {\bf 5} (1962), 459--462]. hOTYA IH METOD DAET
LISHX PRIBLIZHENIE K TOCHNYM FORMULAM TEOREMY~K, ON PROLIVAET DOPOLNITELXNYJ
SVET NA ALGORITM, PO|TOMU MY KRATKO IZLOZHIM EGO. sNACHALA RASSMOTRIM
UDIVITELXNOE SVOJSTVO LINEJNOGO OPROBOVANIYA, VPERVYE OTMECHENNOE
u.~pETERSONOM V 1957~G.

\proclaim tEOREMA P. sREDNEE CHISLO PROB PRI UDACHNOM POISKE S
POMOSHCHXYU ALGORITMA~L NE ZAVISIT OT PORYADKA, V KOTOROM KLYUCHI BYLI
VSTAVLENY, A ZAVISIT LISHX OT TOGO, SKOLXKO KLYUCHEJ IMEYUT TOT ILI INOJ HESH-ADRES.

iNYMI SLOVAMI, LYUBOE PEREUPORYADOCHENIE HESH-POSLEDOVATELXNOSTI~$a_1$
$a_2$~\dots $a_N$ DAET POSLEDOVATELXNOSTX S TEM ZHE SREDNIM SMESHCHENIEM
KLYUCHEJ OT IH HESH-ADRESOV. (kAK UKAZANO VYSHE, MY PREDPOLAGAEM, CHTO VSE
KLYUCHI V TABLICE IMEYUT ODINAKOVUYU VAZHNOSTX. eSLI K NEKOTORYM IZ NIH
PROISHODYAT BOLEE CHASTYE OBRASHCHENIYA, METODOM, ANALOGICHNYM ISPOLXZOVANNOMU
V TEOREME~6.1S, MOZHNO DOKAZATX, CHTO RASPOLOZHENIE KLYUCHEJ OPTIMALXNO,
ESLI ONI VSTAVLYALISX V PORYADKE UBYVANIYA CHASTOT.)

\proof dOSTATOCHNO POKAZATX, CHTO OBSHCHEE CHISLO PROB, NEOBHODIMYH PRI VSTAVKE
KLYUCHEJ DLYA HESH-POSLEDOVATELXNOSTI~$a_1$ $a_2$~\dots $a_N$, RAVNO CHISLU
PROB DLYA POSLEDOVATELXNOSTI~$a_1$~\dots $a_{i-1}$ $a_{i+1}$ $a_i$
$a_{i+2}$~\dots $a_N$, $1\le i<N$. oCHEVIDNO, NUZHNO RASSMOTRETX LISHX SLUCHAJ,
 KOGDA $(i+1)\hbox{-J}$~KLYUCH VO VTOROJ POSLEDOVATELXNOSTI POPAL V POZICIYU,
ZANIMAEMUYU $i\hbox{-M}$~KLYUCHOM
%%631
V PERVOJ POSLEDOVATELXNOSTI. nO ESLI $i\hbox{-J}$
I~$(i+1)\hbox{-J}$~|LEMENTY PROSTO POMENYALISX MESTAMI, TO CHISLO PROB DLYA
$(i+1)\hbox{-GO}$~KLYUCHA UMENXSHILOSX NA STOLXKO, NA SKOLXKO UVELICHILOSX
CHISLO PROB DLYA $i\hbox{-GO}$.
\proofend

tEOREMA~P GLASIT, CHTO SREDNYUYU DLINU POISKA DLYA
HESH-POSLEDOVATELXNOSTI~$a_1$ $a_2$~\dots $a_N$ MOZHNO NAJTI, ZNAYA
CHISLA~$b_0$ $b_1$~\dots $b_{M-1}$, GDE $b_j$~ESTX KOLICHESTVO
|LEMENTOV~$a_i$, RAVNYH~$j$. pO |TOJ POSLEDOVATELXNOSTI MOZHNO OPREDELITX
"POSLEDOVATELXNOSTX PERENOSOV"~$c_0$ $c_1$~\dots $c_{M-1}$, GDE $c_j$---CHISLO
KLYUCHEJ, PRI VSTAVKE KOTORYH OPROBOVALISX OBE POZICII~$j$ I~$j-1$. eTA
POSLEDOVATELXNOSTX OPREDELYAETSYA PRAVILOM
$$
c_j=\cases{
0, & ESLI $b_j=c_{(j+1)\bmod M}=0$;\cr
b_j+c_{(j+1)\bmod M}-1 & V PROTIVNOM SLUCHAE.\cr
}
\eqno(44)
$$
pUSTX, NAPRIMER, $M=10$, $N=8$
I~$b_0\ldots{}b_9=0\ 3\ 2\ 0\ 1\ 0\ 0\ 0\ 2$;
TOGDA~$c_0\ldots{}c_9=2\ 3\ 1\ 0\ 0\ 0\ 0\ 1\ 2\ 3$, TAK KAK ODIN KLYUCH
NUZHNO PERENESTI IZ POZICII~2 V POZICIYU~1, TRI---IZ POZICII~1 V POZICIYU~0,
DVA---IZ POZICII~0 V POZICIYU~9 I~T.~D. iMEEM~$b_0+b_1+\cdots+b_{M-1}=N$, A
SREDNEE CHISLO PROB, TREBUYUSHCHIHSYA DLYA VYBORKI |TIH $N$~KLYUCHEJ, RAVNO
$$
1+(c_0+c_1+\cdots+c_{M-1})/N.
\eqno (45)
$$
kAZHETSYA, CHTO PRAVILO~(44) CIKLICHESKI OPREDELYAET CHISLA~$c$ CHEREZ SAMIH SEBYA,
 NO V DEJSTVITELXNOSTI PRI LYUBOM~$N<M$ SISTEMA IMEET EDINSTVENNOE RESHENIE (SM.~UPR.~32).

g.~shAJ I~v.~sPRUT ISPOLXZOVALI |TU IDEYU DLYA OPREDELENIYA VEROYATNOSTEJ~$q_k$
(VEROYATNOSTI TOGO, CHTO~$c_j=k$) CHEREZ VEROYATNOSTI~$p_k$ (VEROYATNOSTI TOGO,
CHTO~$b_j=k$). (eTI VEROYATNOSTI NE ZAVISYAT OT~$j$.) tAK,
$$
\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)
$$
I~T.~D., POSKOLXKU, NAPRIMER, VEROYATNOSTX TOGO, CHTO~$c_j=2$,
ESTX VEROYATNOSTX TOGO, CHTO~$b_j+c_{(j+1)\bmod M}=3$.
pUSTX~$B(z)=\sum p_kz_k$ I~$C(z)=\sum q_kz^k$---PROIZVODYASHCHIE FUNKCII DLYA
RASSMATRIVAEMYH VEROYATNOSTNYH RASPREDELENIJ; URAVNENIYA~(46) |KVIVALENTNY SOOTNOSHENIYU
$$
B(z)C(z)=p_0q_0+(q_0-p_0q_0)z+q_1z^2+\cdots=p_0q_0(1-z)+zC(z).
$$
tAK KAK~$B(1)=1$, MOZHNO NAPISATX~$B(z)=1+(z-1)D(z)$. oTSYUDA VYTEKAET, CHTO
$$
C(z)={p_0q_0\over 1-D(z)}={1-D(1)\over 1-D(z)},
\eqno(47)
$$
%%632
POSKOLXKU~$C(1)=1$. sLEDOVATELXNO, SREDNEE CHISLO PROB, NEOBHODIMYH DLYA
VYBORKI, V SOOTVETSTVII S~(45) SOSTAVIT
$$
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)
$$
v SILU PREDPOLOZHENIYA O RAVNOVEROYATNOSTI VSEH HESH-POSLEDOVATELXNOSTEJ IMEEM
$$
\eqalignno{
p_k &= \hbox{(vEROYATNOSTX TOGO, CHTO DLYA FIKSIROVANNOGO~$j$ V TOCHNOSTI
$k$~CHISEL~$a_i$ RAVNO~$j$)}=\cr
&=\perm{N}{k}\left({1\over M}^k\right)\left(1-{1\over M}\right)^{N-k}; &(49)\cr
}
$$
PO|TOMU
$$
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)
$$
I SREDNEE CHISLO PROB, SOGLASNO~(48), SOSTAVIT
$$
C_N={1\over2}\left(1+{M-1\over M-N}\right).
\eqno(51)
$$
pONYATNO LI CHITATELYU, POCHEMU |TOT OTVET OTLICHAETSYA OT REZULXTATA
TEOREMY~K? (sR.~S~UPR.~33.)

\section *iSSLEDOVANIE OPTIMALXNOSTI. mY IZUCHILI NESKOLXKO
POSLEDOVATELXNOSTEJ PROB DLYA OTKRYTOJ ADRESACII, I ESTESTVENNO SPROSITX,
KAKAYA IZ NIH YAVLYAETSYA "NAILUCHSHEJ IZ VOZMOZHNYH" V NEKOTOROM RAZUMNOM SMYSLE.
 iNTERESNUYU POSTANOVKU |TOJ ZADACHI PREDLOZHIL dZH.~uLXMAN [{\sl JACM,\/}
{\bf 19} (1972), 569--575]:
VMESTO VYCHISLENIYA "HESH-ADRESA"~$h(K)$ MOZHNO OTOBRAZITX KAZHDYJ KLYUCH~$K$ V
CELUYU PERESTANOVKU MNOZHESTVA~$\set{0, 1,~\ldots, M-1}$, PREDSTAVLYAYUSHCHUYU
SOBOJ POSLEDOVATELXNOSTX PROB PRI ISPOLXZOVANII~$K$. kAZHDOJ IZ
$M!$~PERESTANOVOK PRIPISYVAETSYA VEROYATNOSTX, I PREDPOLAGAETSYA, CHTO
OBOBSHCHENNAYA HESH-FUNKCIYA VYBIRAET KAZHDUYU PERESTANOVKU S |TOJ VEROYATNOSTXYU.
vOPROS STAVITSYA TAK: "kAK NUZHNO PRIPISATX PERESTANOVKAM VEROYATNOSTI,
CHTOBY POLUCHITX NAILUCHSHIE HARAKTERISTIKI, T.~E.~CHTOBY SOOTVETSTVUYUSHCHEE
SREDNEE CHISLO PROB~$C_N$ ILI~$C'_N$ BYLO MINIMALXNYM?"

eSLI, NAPRIMER, PRIPISATX KAZHDOJ PERESTANOVKE VEROYATNOSTX~$1/M!$, TO,
KAK LEGKO VIDETX, POLUCHITSYA V TOCHNOSTI POVEDENIE  \emph{RAVNOMERNOGO
HESHIROVANIYA} (SM.~(32), (34)). oDNAKO uLXMAN
POSTROIL PRIMER S~$M=4$ I~$N=2$, V KOTOROM~$C'_N$ MENXSHE~${5\over3}$
(|TO ZNACHENIE POLUCHAETSYA PRI RAVNOMERNOM HESHIROVANII). oN PRIPISAL
NENULEVYE VEROYATNOSTI LISHX SLEDUYUSHCHIM SHESTI PERESTANOVKAM:
%%633
$$
\matrix{
\hbox{pERESTANOVKA} & \hbox{vEROYATNOSTX} & \hbox{pERESTANOVKA} & \hbox{vEROYATNOSTX}\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)
$$
gRUBO GOVORYA, NA PERVOM SHAGE MY PREDPOCHITAEM~2 I~3, A NA VTOROM---0 I~1.
sREDNEE CHISLO PROB, NEOBHODIMYH DLYA VSTAVKI
TRETXEGO |LEMENTA, OKAZYVAETSYA
RAVNYM~${5\over3}-{1\over9}\varepsilon+O(\varepsilon^2)$, CHTO
MENXSHE~${5\over3}$ PRI MALOM POLOZHITELXNOM~$\varepsilon$.

oDNAKO PRI TAKOM RASPREDELENII
VEROYATNOSTEJ~$C'_1={23\over18}+O(\varepsilon)$,
A |TO BOLXSHE~${5\over4}$ (ZNACHENIE~$C'_1$ DLYA RAVNOMERNOGO HESHIROVANIYA).
uLXMAN DOKAZAL, CHTO PRI LYUBOM SPOSOBE PRIPISYVANIYA VEROYATNOSTEJ, TAKOM,
CHTO~$C'_N<(M+1)/(M+1-N)$ PRI NEKOTOROM~$N$, VSEGDA SUSHCHESTVUET~$n<N$, TAKOE,
 CHTO~$C'_n > (M+1)/(M+1-n)$;
NELXZYA VSE VREMYA POBEZHDATX RAVNOMERNOE HESHIROVANIE.

v DEJSTVITELXNOSTI V KACHESTVE MERY LUCHSHE PODHODIT NE~$C'_N$, A CHISLO PROB
PRI \emph{UDACHNOM} POISKE~$C_N$. pERESTANOVKI~(52) NE DAYUT ULUCHSHENIYA~$C_N$
NI PRI KAKOM~$N$, I KAZHETSYA VESXMA RAZUMNYM PREDPOLOZHITX, CHTO NIKAKOE
PRIPISYVANIE PERESTANOVKAM VEROYATNOSTEJ NE MOZHET SDELATX~$C_N$ MENXSHE
"RAVNOMERNOGO" ZNACHENIYA~$((M+1)/N) (H_{M+1}-H_{M+1-N})$.

kAK OKAZYVAETSYA, |TO UTVERZHDENIE OCHENX TRUDNO DOKAZATX GLAVNYM OBRAZOM
POTOMU, CHTO POLUCHITX |FFEKT RAVNOMERNOGO HESHIROVANIYA MOZHNO MNOGIMI
SPOSOBAMI; MY NE OBYAZANY PRIPISYVATX KAZHDOJ PERESTANOVKE VEROYATNOSTX~$1/M!$.
nAPRIMER, SLEDUYUSHCHEE RASPREDELENIE PRI~$M=4$ |KVIVALENTNO RAVNOMERNOMU HESHIROVANIYU:
$$
\matrix{
\hbox{pERESTANOVKA} & \hbox{vEROYATNOSTX} & \hbox{pERESTANOVKA} & \hbox{vEROYATNOSTX}\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)
$$
(OSTALXNYM 16~PERESTANOVKAM PRIPISYVAETSYA NULEVAYA VEROYATNOSTX).

sLEDUYUSHCHAYA TEOREMA HARAKTERIZUET \emph{VSE} RASPREDELENIYA VEROYATNOSTEJ,
KOTORYE DAYUT POVEDENIE RAVNOMERNOGO HESHIROVANIYA:

\proclaim tEOREMA~U. pRIPISYVANIE PERESTANOVKAM VEROYATNOSTEJ SDELAET VSE
$\perm{M}{N}$~KONFIGURACIJ ZANYATYH I SVOBODNYH YACHEEK POSLE N~VSTAVOK
RAVNOVEROYATNYMI DLYA~$0<N<M$ TOGDA I TOLXKO TOGDA, KOGDA
%%634
SUMMA VEROYATNOSTEJ, PRIPISANNYH VSEM PERESTANOVKAM, PERVYE $N$~|LEMENTOV
KOTORYH PRINADLEZHAT DANNOMU $N\hbox{-|LEMENTNOMU}$ MNOZHESTVU,
RAVNA~$1\big/\perm{M}{N}$ DLYA VSEH~$N$ I VSEH $N\hbox{-|LEMENTNYH}$ MNOZHESTV.

nAPRIMER, SUMMA VEROYATNOSTEJ, PRIPISANNYH KAZHDOJ IZ
$3!(M-3)!$~PERESTANOVOK, NACHINAYUSHCHIHSYA S CHISEL~$\set{0, 1,2}$, STOYASHCHIH V
NEKOTOROM PORYADKE, DOLZHNA SOSTAVLYATX~$1\big/\perm{M}{3}=3!(M-3)!/M!$.
zAMETXTE, CHTO (53)~UDOVLETVORYAET USLOVIYU TEOREMY.

\proof pUSTX~$A\le \set{0, 1,~\ldots, M-1}$, I PUSTX~$\Pi(A)$ ESTX
MNOZHESTVO VSEH PERESTANOVOK, PERVYE $\Abs{A}$~|LEMENTOV KOTORYH
PRINADLEZHAT~$A$. sUMMU VEROYATNOSTEJ, PRIPISANNYH |TIM  PERESTANOVKAM,
OBOZNACHIM CHEREZ~$S(A)$. sIMVOLOM~$P_k(A)$ OBOZNACHIM VEROYATNOSTX TOGO,
CHTO PERVYE $\Abs{A}$~KLYUCHEJ, VSTAVLENNYH PROCEDUROJ OTKRYTOJ ADRESACII,
ZAJMUT YACHEJKI, OPREDELENNYE MNOZHESTVOM~$A$, I CHTO POSLEDNYAYA VSTAVKA
POTREBUET ROVNO $k$~PROB;
POLOZHIM~$P(A)=P_1(A)+P_2(A)+\cdots$. dOKAZATELXSTVO PROVODITSYA INDUKCIEJ
PO~$N\ge 1$; PREDPOLAGAETSYA, CHTO
$$
P(A)=S(A)=1\bigg/\perm{M}{n}
$$
DLYA VSEH MNOZHESTV~$A$ S~$\Abs{A}=n<N$. pUSTX $B$ ESTX
$N\hbox{-|LEMENTNOE}$ MNOZHESTVO. tOGDA
$$
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}),
$$
GDE $\Pr(\pi)$~ESTX VEROYATNOSTX, PRIPISANNAYA PERESTANOVKE~$\pi$, a
 $\pi_k$---EE $k\hbox{-J}$~|LEMENT. v SILU INDUKTIVNOGO PREDPOLOZHENIYA
$$
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),
$$
CHTO RAVNYAETSYA
$$
\perm{N}{k}\bigg/\perm{M}{N-1}\perm{M}{k},
\rem{ESLI $k<N$;}
$$
SLEDOVATELXNO,
$$
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
A |TO RAVNYAETSYA~$1\big/\perm{M}{N}$ TOGDA I TOLXKO TOGDA, KOGDA
$S(B)$~IMEET TREBUEMOE ZNACHENIE.
\proofend

\section vNESHNIJ POISK. mETODY HESHIROVANIYA VPOLNE PODHODYAT DLYA VNESHNEGO
POISKA NA ZAPOMINAYUSHCHIH USTROJSTVAH S PRYAMYM DOSTUPOM TIPA DISKOV ILI
BARABANOV. dLYA TAKIH PRILOZHENIJ, KAK I V P.~6.2.4, MY HOTIM MINIMIZIROVATX
CHISLO OBRASHCHENIJ K FAJLU, I |TO DVOYAKO VLIYAET NA VYBOR ALGORITMOV:

\enumerate
\li rAZUMNO POTRATITX BOLXSHE VREMENI NA VYCHISLENIE HESH-FUNKCII, POTOMU
CHTO RASPLATA ZA PLOHOE HESHIROVANIE MNOGO BOLXSHE STOIMOSTI DOPOLNITELXNOGO
VREMENI, NUZHNOGO DLYA AKKURATNOJ RABOTY.

\li zAPISI OBYCHNO SGRUPPIROVANY V BLOKI, CHTOBY ZA ODIN RAZ IZVLEKATX IZ
VNESHNEJ PAMYATI NESKOLXKO ZAPISEJ.
\enumend

oBYCHNO FAJL DELITSYA NA $M$~BLOKOV PO $b$~ZAPISEJ V KAZHDOM. kOLLIZII NE
VYZYVAYUT ZATRUDNENIJ, POKA NE POYAVITSYA BOLEE $b$~KLYUCHEJ S DANNYM
HESH-ADRESOM. pO-VIDIMOMU, NAILUCHSHIMI BUDUT SLEDUYUSHCHIE TRI PODHODA K
RAZRESHENIYU KOLLIZIJ.

A) {\sl rAZDELXNYE CEPOCHKI.\/} eSLI V ODIN I TOT ZHE BLOK POPADAET BOLXSHE
$b$~ZAPISEJ, V KONCE PERVOGO BLOKA MOZHNO VSTAVITX SSYLKU NA
"PEREPOLNYAYUSHCHUYU" ZAPISX. pEREPOLNYAYUSHCHIE ZAPISI HRANYATSYA V SPECIALXNOJ
OBLASTI. oBYCHNO NET SMYSLA IMETX BLOKI V OBLASTI PEREPOLNENIYA, TAK KAK
VOZNIKAET SRAVNITELXNO MALO PEREPOLNENII; TAKIM OBRAZOM, DOBAVLYAYUSHCHIESYA
ZAPISI OBYCHNO SVYAZYVAYUTSYA DRUG S DRUGOM, I NA $(b+k)\hbox{-YU}$~ZAPISX
SPISKA TRATITSYA $1+k$~OBRASHCHENIJ K VNESHNEMU USTROJSTVU. chASTO POLEZNO
OSTAVITX NEKOTOROE PROSTRANSTVO NA KAZHDOM "CILINDRE" DISKOVOGO FAJLA,
CHTOBY BOLXSHINSTVO OBRASHCHENIJ PROISHODILO K ODNOMU I TOMU ZHE CILINDRU.

hOTYA TAKOJ METOD OBRABOTKI PEREPOLNENII KAZHETSYA NE|FFEKTIVNYM, CHISLO
PEREPOLNENII STATISTICHESKI DOSTATOCHNO MALO, I SREDNEE VREMYA POISKA
OKAZYVAETSYA OCHENX HOROSHIM. v TABL.~2 I~3 PRIVODITSYA SREDNEE CHISLO
OBRASHCHENIJ KAK FUNKCIYA OT KO|FFICIENTA  ZAPOLNENIYA
$$
\alpha=N/Mb,
\eqno(54)
$$
GDE $\alpha$~FIKSIROVANO I $m, N\to\infty$. kAK NI STRANNO, NO
PRI~$\alpha=1$ ASIMPTOTICHESKOE CHISLO OBRASHCHENIJ V SLUCHAE NEUDACHNOGO POISKA
RASTET S ROSTOM~$b$.

B) {\sl sRASTAYUSHCHIESYA CEPOCHKI.\/} vMESTO OTVEDENIYA OTDELXNOJ
OBLASTI PEREPOLNENIYA, MOZHNO PRISPOSOBITX ALGORITM~C DLYA RABOTY S VNESHNIMI
FAJLAMI. eSHCHE NE ZAPOLNENNYE BLOKI MOZHNO SVYAZATX V DVUHSVYAZEVYJ SPISOK
SVOBODNOGO PROSTRANSTVA. sOGLASNO
%%636
\htable{tABLICA 2}%
{sREDNEE CHISLO OBRASHCHENIJ PRI NEUDACHNOM POISKE S POMOSHCHXYU RAZDELXNYH CEPOCHEK}%
{\hfill#\bskip&&\hfill\bskip$#$\bskip\hfill\cr
\noalign{\hrule}
 &\multispan{10}\hfill\hbox{kO|FFICIENT ZAPOLNENIYA, $\alpha$}\hfill\cr
rAZMER BLOKA~$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}}%
|TOJ SHEME, KAZHDYJ BLOK SODERZHIT SCHETCHIK CHISLA SVOBODNYH POZICIJ; BLOK
UDALYAETSYA IZ SPISKA, LISHX ESLI |TOT SCHETCHIK OBRASHCHAETSYA V~0. mOZHNO
ISPOLXZOVATX "BLUZHDAYUSHCHIJ UKAZATELX" DLYA RASPREDELENIYA PEREPOLNENII
(SR.~S UPR.~2.5-6), CHTOBY V RAZLICHNYH SPISKAH PO VOZMOZHNOSTI FIGURIROVALI
RAZLICHNYE BLOKI PEREPOLNENIYA. vEROYATNO, POLEZNO IMETX OTDELXNYE SPISKI
SVOBODNOGO PROSTRANSTVA DLYA BLOKOV NA KAZHDOM CILINDRE DISKOVOGO FAJLA.

eTOT METOD ESHCHE NE PROANALIZIROVAN, NO ON DOLZHEN OKAZATXSYA VESXMA POLEZNYM.

\htable{tABLICA 3}%
{sREDNEE CHISLO OBRASHCHENII PRI UDACHNOM POISKE S POMOSHCHXYU RAZDELXNYH CEPOCHEK}%
{\hfill#\bskip&&\hfill\bskip$#$\bskip\hfill\cr
\noalign{\hrule}
 &\multispan{10}\hfill\hbox{kO|FFICIENT ZAPOLNENIYA, $\alpha$}\hfill\cr
rAZMER BLOKA~$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 oTKRYTAYA ADRESACIYA.\/} mOZHNO OBOJTISX I BEZ SSYLOK, ISPOLXZUYA
"OTKRYTYJ" METOD. dLYA VNESHNEGO POISKA LINEJNOE OPROBOVANIE, VEROYATNO,
LUCHSHE SLUCHAJNOGO, IBO VELICHINU~$c$ MOZHNO VYBRATX TAK, CHTOBY MINIMIZIROVATX
SKRYTYE ZADERZHKI MEZHDU POSLEDOVATELXNYMI OBRASHCHENIYAMI. pOSTROENNAYA VYSHE
PRIBLIZHENNAYA TEORETICHESKAYA MODELX LINEJNOGO OPROBOVANIYA MOZHET BYTX
OBOBSHCHENA DLYA UCHETA VLIYANIYA BLOKOV; ONA POKAZYVAET, CHTO
%%637
\htable{tABLICA 4}%
{sREDNEE CHISLO OBRASHCHENIJ PRI UDACHNOM POISKE S POMOSHCHXYU LINEJNOGO OPROBOVANIYA}%
{\hfill#\bskip&&\hfill\bskip$#$\bskip\hfill\cr
\noalign{\hrule}
 &\multispan{10}\hfill\hbox{kO|FFICIENT ZAPOLNENIYA, $\alpha$}\hfill\cr
rAZMER BLOKA~$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}}%
LINEJNOE OPROBOVANIE DEJSTVITELXNO UDOVLETVORITELXNO, POKA TABLICA NE
SLISHKOM POLNA. iZ TABL.~4 VIDNO, CHTO PRI~$\alpha=90\%$ I~$b=50$ SREDNEE
CHISLO OBRASHCHENIJ DLYA UDACHNOGO POISKA SOSTAVLYAET LISHX~$1.04$. eTO DAZHE
\emph{LUCHSHE,} CHEM $1.08$~OBRASHCHENIYA, KOTOROE TREBUETSYA V METODE CEPOCHEK~(A)
S TEM ZHE RAZMEROM BLOKA!

aNALIZ METODOV~(A) I~(C) VESXMA INTERESEN I S MATEMATICHESKOJ TOCHKI
ZRENIYA; MY PRIVEDEM ZDESX LISHX REZULXTATY, POSKOLXKU DETALXNOMU
ISSLEDOVANIYU POSVYASHCHENY UPR.~49 I~55. fORMULY SODERZHAT DVE FUNKCII, TESNO
SVYAZANNYE S $Q\hbox{-FUNKCIYAMI}$ TEOREMY~$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)
$$
I
$$
\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
}
$$
s POMOSHCHXYU |TIH FUNKCIJ MOZHNO VYRAZITX SREDNEE CHISLO OBRASHCHENIJ,
NEOBHODIMYH PRI NEUDACHNOM POISKE S POMOSHCHXYU METODA~(A)
$$
C'_N=1+\alpha b t_b(\alpha)+O\left({1\over M})\right)
\eqno(57)
$$
($M, N\to\infty$), I SOOTVETSTVUYUSHCHEE CHISLO PRI UDACHNOM
POISKE
$$
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)
$$
eTO SOGLASUETSYA S DANNYMI TABL.~2 I~3.

pOSKOLXKU METOD CEPOCHEK~(A) TREBUET OTDELXNOJ OBLASTI PEREPOLNENIYA,
SLEDUET OCENITX VOZMOZHNOE KOLICHESTVO PEREPOLNENIJ. iH SREDNEE CHISLO
SOSTAVLYAET~$M(C_n'-1)=N t_b(\alpha)$, TAK KAK
%%638
$C'_N-1$~ESTX CHISLO PEREPOLNENIJ V LYUBOM DANNOM SPISKE. pO|TOMU TABL.~2
MOZHNO POLXZOVATXSYA DLYA NAHOZHDENIYA RAZMERA |TOJ OBLASTI. pRI
FIKSIROVANNOM~$\alpha$ I~$M\to\infty$ SREDNEKVADRATICHNOE OTKLONENIE OBSHCHEGO
CHISLA PEREPOLNENIJ BUDET PRIBLIZITELXNO PROPORCIONALXNO~$\sqrt{M}$.

aSIMPTOTICHESKIE ZNACHENIYA~$C'_N$ I~$C_N$ PRIVEDENY V UPR.~53, NO |TI
PRIBLIZHENIYA NE OCHENX HOROSHI PRI MALYH~$b$ ILI BOLXSHIH~$\alpha$; K
SCHASTXYU, RYAD DLYA~$R(\alpha, n)$ SHODITSYA OCHENX BYSTRO DAZHE PRI
BOLXSHIH~$\alpha$, TAK CHTO MOZHNO BEZ BOLXSHOGO TRUDA OPERIROVATX TOCHNYMI
FORMULAMI. mAKSIMUM~$C_N$ I~$C'_N$ DOSTIGAETSYA PRI~$\alpha=1$ I VYRAZHAETSYA
PRI~$b\to\infty$ KAK
$$
\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
}
$$
SOGLASNO PRIBLIZHENIYU sTIRLINGA I ANALIZU FUNKCII~$R(n)=R(1,n)-1$,
PROVEDENNOMU V P.~1.2.11.3.

sREDNEE CHISLO OBRASHCHENIJ PRI UDACHNOM POISKE S POMOSHCHXYU \emph{LINEJNOGO}
OPROBOVANIYA IMEET UDIVITELXNO PROSTOJ VID:
$$
C_N\approx 1+t_b(\alpha)+t_{2b}(\alpha)+t_{3b}(\alpha)+\ldots\,.
\eqno(61)
$$
eTO SOOTNOSHENIE MOZHNO POYASNITX SLEDUYUSHCHIM OBRAZOM: SREDNEE CHISLO OBRASHCHENIJ
PRI POISKE VSEH $N$~KLYUCHEJ RAVNO~$NC_N$, A |TO ESTX~$N+T_1+T_2+\ldots$,
GDE $T_k$~OBOZNACHAET SREDNEE CHISLO KLYUCHEJ, POISK KOTORYH TREBUET BOLEE
$k$~OBRASHCHENIJ. tEOREMA~P GLASIT, CHTO, NE IZMENYAYA~$C_N$, KLYUCHI MOZHNO
VSTAVLYATX V LYUBOM PORYADKE; OTSYUDA SLEDUET, CHTO $T_k$~RAVNO SREDNEMU CHISLU
PEREPOLNYAYUSHCHIH ZAPISEJ, KOTORYE IMELISX BY PRI ISPOLXZOVANII METODA
CEPOCHEK S $M/k$~BLOKAMI RAZMERA~$kb$, T.~E.~$T_k=Nt_{kb}(\alpha)$, CHTO I
UTVERZHDALOSX. dALXNEJSHEE UTOCHNENIE FORMULY~(61) PROVEDENO V UPR.~55.

oTLICHNOE OBSUZHDENIE PRAKTICHESKIH SOOBRAZHENIJ PO POSTROENIYU VNESHNIH
RASSEYANNYH TABLIC DAL chARLXZ oLSON
[{\sl Proc. ACM Nat'1 Conf.,\/} {\bf 24} (1969), 539--549]. rABOTA
SODERZHIT NESKOLXKO POLEZNYH PRIMEROV; V NEJ UKAZYVAETSYA, CHTO KOLICHESTVO
PEREPOLNYAYUSHCHIH ZAPISEJ ZNACHITELXNO UVELICHIVAETSYA, ESLI FAJL SLUZHIT OB®EKTOM
CHASTYH VSTAVOK I UDALENIJ BEZ PERERAZMESHCHENIYA ZAPISEJ. pREDSTAVLEN ANALIZ
|TOJ SITUACII, VYPOLNENNYJ SOVMESTNO oLSONOM I DE~pEJSTEROM.

\section sRAVNENIE METODOV. iTAK, MY IZUCHILI MNOGO METODOV POISKA;
CHEM ZHE NAM RUKOVODSTVOVATXSYA PRI VYBORE NAILUCHSHEGO IZ NIH;
DLYA KONKRETNOGO PRILOZHENIYA? tRUDNO V NESKOLXKIH SLOVAH OPISATX VSE, CHTO
NAM HOTELOSX BY UCHESTX PRI VYBORE METODA POISKA, ODNAKO SLEDUYUSHCHIE
SOOBRAZHENIYA, POZHALUJ, NAIBOLEE
%%639
\picture{rIS.~44. sRAVNENIE METODOV RAZRESHENIYA KOLLIZIJ: PREDELXNYE
ZNACHENIYA SREDNEGO CHISLA PROB PRI~$M\to\infty$. (A)---NEUDACHNYJ POISK
(KO|FFICIENT ZAPOLNENIYA~$\alpha=N/M$);
(b)---UDACHNYJ POISK. ($L$---LINEJNOE OPROBOVANIE=ALGORITM~L; $U2$---SLUCHAJNOE
ONROBOVANIE SO VTORICHNYM OKUCHIVANIEM; $U$---RAVNOMERNOE
HESHIROVANIE$\approx$ALGORITM~D; $B$---ALGORITM~D S IZMENENIEM bRENTA;
$C$---METOD CEPOCHEK SO SRASTANIEM=ALGORITM~C; $S$---RAZDELXNYE CEPOCHKI;
$SO$---RAZDELXNYE CEPOCHKI S UPORYADOCHENNYMI SPISKAMI.)
}
%%640
VAZHNY, ESLI MY ZAINTERESOVANY V SOKRASHCHENII VREMENI POISKA I OB®EMA
ZANIMAEMOJ PAMYATI.

nA RIS.~44 POKAZANY REZULXTATY PROVEDENNOGO ANALIZA. vIDNO, CHTO RAZLICHNYE
SPOSOBY RAZRESHENIYA KOLLIZIJ PRIVODYAT K RAZLICHNOMU CHISLU PROB. nO |TO ESHCHE
NE VSE, TAK KAK S IZMENENIEM METODA MENYAETSYA VREMYA PROBY, CHTO ZAMETNO
OTRAZHAETSYA NA VREMENI RABOTY (SM.~RIS.~42). pRI LINEJNOM OPROBOVANII CHASHCHE,
 CHEM V DRUGIH METODAH, PROISHODIT OBRASHCHENIE K TABLICE, ZATO |TOT METOD
PROST. bOLEE TOGO, NELXZYA SKAZATX, CHTO DAZHE LINEJNOE OPROBOVANIE SOVSEM UZH
NIKUDA NE GODITSYA: ESLI TABLICA ZAPOLNENA NA 90\%, ALGORITM~L TREBUET V
SREDNEM MENEE $5.5$~PROBY DLYA OBNARUZHENIYA SLUCHAJNOGO |LEMENTA. (oDNAKO
SREDNEE CHISLO PROB PRI VSTAVKE \emph{NOVOGO} |LEMENTA S POMOSHCHXYU
ALGORITMA~L RAVNO~$50.5$, ESLI TABLICA POLNA NA 90\%.)

iZ RIS.~44 VIDNO, CHTO METODY CEPOCHEK VESXMA |KONOMNY S TOCHKI ZRENIYA CHISLA
PROB, NO POTREBNOSTX V DOPOLNITELXNOM PROSTRANSTVE PAMYATI DLYA POLEJ SSYLOK
INOGDA (PRI NEBOLXSHOM RAZMERE ZAPISEJ) DELAET BOLEE PRIVLEKATELXNOJ
OTKRYTUYU ADRESACIYU. nAPRIMER, ESLI NUZHNO SDELATX VYBOR MEZHDU TABLICEJ S
CEPOCHKAMI NA 500~|LEMENTOV I TABLICEJ S OTKRYTOJ ADRESACIEJ NA
1000~|LEMENTOV, TO POSLEDNYAYA, OCHEVIDNO, PREDPOCHTITELXNEE, IBO ONA
OBESPECHIVAET |FFEKTIVNYJ POISK SREDI 500~ZAPISEJ I SPOSOBNA VMESTITX V DVA
RAZA BOLXSHE DANNYH. s DRUGOJ STORONY, POROJ V SILU RAZMERA ZAPISEJ ILI
IH FORMATA PROSTRANSTVO POD POLYA SSYLOK DOSTAETSYA FAKTICHESKI BESPLATNO
(SR.~S~UPR.~65).

kAK SOOTNOSYATSYA METODY HESHIROVANIYA S DRUGIMI STRATEGIYAMI POISKA,
IZUCHENNYMI V |TOJ GLAVE? sRAVNIVAYA IH PO SKOROSTI, MOZHNO UTVERZHDATX, CHTO
METODY HESHIROVANIYA LUCHSHE, ESLI CHISLO ZAPISEJ VELIKO, POSKOLXKU SREDNEE
VREMYA POISKA DLYA METODOV HESHIROVANIYA OSTAETSYA OGRANICHENNYM
PRI~$N\to\infty$ V SLUCHAE, KOGDA TABLICA NE STANOVITSYA SLISHKOM ZAPOLNENNOJ.
 nAPRIMER, PROGRAMME~L NUZHNO LISHX 55~EDINIC VREMENI DLYA UDACHNOGO POISKA V
TABLICE, ZAPOLNENNOJ NA~90\%; |TO BYSTREE SAMOJ BYSTROJ IZ IZVESTNYH NAM
\MIX-PROGRAMM BINARNOGO POISKA (SM.~UPR.~6.2.1-24), ESLI~$N$ BOLXSHE~600
ILI OKOLO TOGO, I PLATITX ZA |TO PRIHODITSYA LISHX 11\%~PROSTRANSTVA
PAMYATI. bOLEE TOGO, BINARNYJ POISK GODITSYA LISHX DLYA FIKSIROVANNYH TABLIC,
 V TO VREMYA KAK RASSEYANNYE TABLICY DOPUSKAYUT |FFEKTIVNYE PROCEDURY VSTAVKI.

mY MOZHEM TAKZHE SRAVNITX PROGRAMMU~L S METODAMI POISKA PO DEREVU,
DOPUSKAYUSHCHIMI DINAMICHESKIE VSTAVKI. pROGRAMMA~L PRI~$\alpha=0.9$ BYSTREE
PROGRAMMY~6.2.2T, ESLI $N$~PREVYSHAET PRIBLIZITELXNO~90, I BYSTREE
PROGRAMMY~6.3D (UPR.~6.3-9), ESLI $N$~PREVYSHAET PRIMERNO~75.

%%641
tOLXKO ODIN METOD |TOJ GLAVY V SLUCHAE UDACHNOGO POISKA VESXMA |FFEKTIVEN I
FAKTICHESKI NE DAET PERERASHODA PAMYATI, A IMENNO ALGORITM~D S IZMENENIEM
bRENTA. oN POZVOLYAET POMESTITX $N$~ZAPISEJ V TABLICU RAZMERA~$M=N+1$ I NAHODITX
LYUBUYU ZAPISX V SREDNEM ZA $2{1\over2}$~PROBY. nE NUZHNO DOPOLNITELXNOGO
PROSTRANSTVA DLYA POLEJ SSYLOK I~T.~P.; ODNAKO NEUDACHNYJ POISK BUDET
KRAJNE MEDLENNYM---ON POTREBUET OKOLO ${1\over2}N$~PROB.

tAKIM OBRAZOM, HESHIROVANIE IMEET SVOI PREIMUSHCHESTVA. s DRUGOJ STORONY,
POISK V RASSEYANNYH TABLICAH VSE ZHE USTUPAET IZUCHENNYM RANEE METODAM PO
TREM VAZHNYM PUNKTAM.

\medskip
a)~pOSLE NEUDACHNOGO POISKA V RASSEYANNOJ TABLICE MY ZNAEM LISHX TO, CHTO
NUZHNOGO KLYUCHA TAM NET. mETODY POISKA, OSNOVANNYE NA SRAVNENIYAH, VSEGDA
DAYUT BOLXSHE INFORMACII; ONI POZVOLYAYUT NAJTI NAIBOLXSHIJ $\hbox{KLYUCH} \le K$
ILI NAIMENXSHIJ $\hbox{KLYUCH}\ge K$ , CHTO VAZHNO VO MNOGIH PRILOZHENIYAH
(NAPRIMER, DLYA INTERPOLYACII ZNACHENIJ FUNKCII PO HRANYASHCHEJSYA TABLICE).
eTI ZHE METODY MOZHNO ISPOLXZOVATX I DLYA NAHOZHDENIYA VSEH KLYUCHEJ, LEZHASHCHIH
\emph{MEZHDU} DVUMYA ZADANNYMI VELICHINAMI~$K$ I~$K'$. dALEE, ALGORITMY
POISKA PO DEREVU~\S~6.2 POZVOLYAYUT LEGKO RASPECHATATX SODERZHIMOE TABLICY V
VOZRASTAYUSHCHEM PORYADKE BEZ SPECIALXNOJ SORTIROVKI, A |TO INOGDA BYVAET NUZHNO.

\medskip
b)~chASTO DOVOLXNO TRUDNO RASPREDELITX PAMYATX DLYA RASSEYANNYH TABLIC; POD
HESH-TABLICU NUZHNO OTVESTI OPREDELENNUYU OBLASTX PAMYATI, A RAZMER EE NE
VSEGDA YASEN. eSLI OTVESTI SLISHKOM MNOGO PAMYATI, TO TAKAYA RASTOCHITELXNOSTX
OTRAZITSYA NA DRUGIH SPISKAH ILI NA DRUGIH POLXZOVATELYAH evm, NO
ESLI OTVESTI MALO MESTA, TABLICA PEREPOLNITSYA! pRI PEREPOLNENII RASSEYANNOJ
TABLICY, VEROYATNO, LUCHSHE VSEGO "REHESHIROVATX" EE, T.~E.~OTVESTI BOLXSHE
PROSTRANSTVA I IZMENITX HESH-FUNKCIYU, A ZATEM VSTAVITX ZAPISI V BOLXSHUYU
TABLICU. f.~hOPGUD
[{\sl Comp. Bulletin,\/} {\bf 11} (1968), 297--300] PREDLOZHIL REHESHIROVATX
TABLICU, ESLI KO|FFICIENT ZAPOLNENIYA DOSTIGNET~$\alpha$, ZAMENYAYA~$M$
NA~$d_0 M$; S POMOSHCHXYU PRIVEDENNOGO VYSHE ANALIZA I HARAKTERISTIK DANNYH
MOZHNO OPREDELITX KRITICHESKUYU TOCHKU, KOGDA REHESHIROVANIE STANOVITSYA DESHEVLE
DALXNEJSHEJ RABOTY S TOJ ZHE TABLICEJ, I TEM SAMYM VYBRATX ZNACHENIYA
PARAMETROV~$\alpha_0$ I~$d_0$. (zAMETIM, CHTO METOD CEPOCHEK SVOBODEN OT
MUCHITELXNYH PEREPOLNENII I NE NUZHDAETSYA V REHESHIROVANII, ODNAKO PRI
FIKSIROVANNOM~$M$ I RASTUSHCHEM~$N$ VREMYA POISKA STANOVITSYA
PROPORCIONALXNYM~$N$.) nAPROTIV, ALGORITMY POISKA SO VSTAVKOJ PO DEREVU NE
IZOBILUYUT TYAGOSTNYMI REHESHIROVANIYAMI; DEREVXYA RASTUT NE BOLXSHE, CHEM |TO
NEOBHODIMO. pRI RABOTE S VIRTUALXNOJ PAMYATXYU NUZHNO,
%% 642
PO VSEJ VEROYATNOSTI, ISPOLXZOVATX POISK PO DEREVU ILI CIFROVOJ POISK
PO DEREVU VMESTO SOZDANIYA BOLXSHIH RASSEYANNYH TABLIC, VYZYVAYUSHCHIH PODKACHKU
NOVOJ STRANICY POCHTI PRI KAZHDOM HESHIROVANII KLYUCHA.

\medskip
c)~nAKONEC, PRI ISPOLXZOVANII METODOV HESHIROVANIYA NUZHNO SVYATO VERITX V
TEORIYU VEROYATNOSTEJ, IBO ONI |FFEKTIVNY LISHX V SREDNEM, A NAIHUDSHIJ SLUCHAJ
PROSTO UZHASEN! kAK I V SITUACII S DATCHIKAMI SLUCHAJNYH CHISEL, MY NE MOZHEM
BYTX POLNOSTXYU UVERENNYMI V TOM, CHTO PRI PRIMENENII K NOVOMU MNOZHESTVU
DANNYH HESH-FUNKCIYA BUDET RABOTATX UDOVLETVORITELXNO. pO|TOMU RASSEYANNAYA
PAMYATX NE VSEGDA PODHODIT DLYA RABOTY V REALXNOM MASSHTABE VREMENI, NAPRIMER
DLYA UPRAVLENIYA DVIZHENIEM TRANSPORTA, POSKOLXKU NA KARTU
POSTAVLENY CHELOVECHESKIE ZHIZNI. aLGORITMY SBALANSIROVANNOGO
DEREVA (P.~6.2.3 I~6.2.4) GORAZDO BEZOPASNEE, VEDX ONI IMEYUT
GARANTIROVANNUYU VERHNYUYU GRANICU VREMENI POISKA.

\section iSTORIYA. pO-VIDIMOMU, VPERVYE IDEYU HESHIROVANIYA VYSKAZAL g.~lAN. v
YANVARE 1953~G., SOSTAVLYAYA ODIN IZ VNUTRENNIH DOKUMENTOV FIRMY~IBM, ON
PREDLOZHIL ISPOLXZOVATX METOD CEPOCHEK; |TO YAVILOSX TAKZHE ODNOJ IZ PERVYH
PUBLIKACIJ PO SVYAZANNYM LINEJNYM SPISKAM. oN UKAZAL NA ZHELATELXNOSTX
ISPOLXZOVANIYA DLYA VNESHNEGO POISKA BLOKOV, SODERZHASHCHIH BOLEE
ODNOGO |LEMENTA. vSKORE POSLE |TOGO e.~lIN PRODVINUL ANALIZ lANA NEMNOGO
DALXSHE I PREDLOZHIL METOD OBRABOTKI PEREPOLNENII S POMOSHCHXYU "VYROZHDAYUSHCHIHSYA
ADRESOV"; NAPRIMER, PRI PEREPOLNENII PERVICHNOGO BLOKA 2748~ZAPISI
POPADAYUT VO VTORICHNYJ BLOK~274; ESLI I ON PEREPOLNILSYA, ISPOLXZUETSYA
TRETICHNYJ BLOK~27 I~T.~D. pREDPOLAGAETSYA, CHTO ESTX 10000~PERVICHNYH BLOKOV,
1000~VTORICHNYH, 100~TRETICHNYH I~T.~D. pERVONACHALXNO PREDLOZHENNYE lANOM
HESH-FUNKCII BYLI LITERNO-CIFROVYMI;
NAPRIMER, SKLADYVALISX PO MODULYU~10 PARY SOSEDNIH CIFR KLYUCHA, TAK
CHTO~31415926 SZHIMALOSX DO~4548.

pRIMERNO V |TO ZHE VREMYA IDEYA HESHIROVANIYA POYAVILASX U DRUGOJ GRUPPY
SOTRUDNIKOV FIRMY~IBM: dZHIN eMDEL, eLEJN bO|M, n.~rOCHESTERA I aRTURA
s|MYU|LYA, STROIVSHIH AVTOKODNUYU PROGRAMMU DLYA IBM~701. dLYA RAZRESHENIYA
PROBLEMY KOLLIZIJ eMDEL VYSKAZALA IDEYU OTKRYTOJ ADRESACII S LINEJNYM
OPROBOVANIEM.

v OTKRYTOJ PECHATI HESHIROVANIE VPERVYE BYLO OPISANO aRNOLXDOM dUMI
[{\sl Computers and Automation,\/} {\bf 5}, 12 (December 1956), 6--9].
iMENNO ON VPERVYE UPOMYANUL IDEYU DELENIYA NA PROSTOE CHISLO I ISPOLXZOVANIYA
OSTATKA V KACHESTVE HESH-ADRESA. v STATXE dUMI UPOMINAETSYA METOD CEPOCHEK,
ODNAKO OTKRYTOJ ADRESACII V NEJ NET. a.~p.~eRSHOV V 1957~G. NEZAVISIMO
OTKRYL LINEJNUYU OTKRYTUYU ADRESACIYU [{\sl dan sssr,\/} {\bf 118} (1958),
427--430];
%%643
ON OPUBLIKOVAL |MPIRICHESKIE REZULXTATY O CHISLE PROB, SPRAVEDLIVO
PREDPOLOZHIV, CHTO PRI~$N/M<2/3$ SREDNEE CHISLO PROB DLYA UDACHNOGO POISKA $<2$.

kLASSICHESKAYA STATXYA u.~pETERSONA
[{\sl IBM J.~Research \& Development,\/} {\bf 1} (1957), 130--146] BYLA
PERVOJ VAZHNOJ RABOTOJ PO VOPROSU POISKA V BOLXSHIH FAJLAH. pETERSON
OPREDELIL OTKRYTUYU ADRESACIYU V OBSHCHEM SLUCHAE, PROANALIZIROVAL
HARAKTERISTIKI RAVNOMERNOGO HESHIROVANIYA I PRIVEL
MNOGOCHISLENNYE STATISTICHESKIE DANNYE O POVEDENII LINEJNOJ OTKRYTOJ
ADRESACII PRI RAZLICHNYH RAZMERAH BLOKOV, PODMETIV UHUDSHENIE
HARAKTERISTIK, VOZNIKAYUSHCHEE PRI UDALENII |LEMENTOV. dRUGOJ VSESTORONNIJ
OBZOR PREDMETA SHESTXYU GODAMI POZZHE OPUBLIKOVAL vERNER bUHHOLXC [{\sl IBM
Systems J.,\/} {\bf 2} (1963), 86--111]; ON NAIBOLEE OSNOVATELXNO IZUCHIL
HESH-FUNKCII.

k |TOMU VREMENI LINEJNOE OPROBOVANIE BYLO EDINSTVENNYM TIPOM SHEMY
OTKRYTOJ ADRESACII, OPISANNYM V LITERATURE, HOTYA NESKOLXKIMI AVTORAMI
NEZAVISIMO BYLA RAZRABOTANA DRUGAYA SHEMA, OSNOVANNAYA NA NEODNOKRATNOM
SLUCHAJNOM OPROBOVANII S POMOSHCHXYU NEZAVISIMYH HESH-FUNKCIJ (SM.~UPR.~48). v
TECHENIE NESKOLXKIH SLEDUYUSHCHIH LET HESHIROVANIE STALO ISPOLXZOVATXSYA OCHENX
SHIROKO, NO O NEM EDVA LI BYLO OPUBLIKOVANO CHTO-NIBUDX NOVOE. zATEM rOBERT
mORRIS NAPISAL OKAZAVSHIJ BOLXSHOE VLIYANIE OBZOR PREDMETA [{\sl CACM,\/}
{\bf 11} (1968), 38--44], V KOTOROM ON VVEL IDEYU SLUCHAJNOGO OPROBOVANIYA
(SO VTORICHNYM SKUCHIVANIEM). sTATXYA mORRISA ZAVERSHILA USILIYA, PRIVEDSHIE K
SOZDANIYU ALGORITMA~D I EGO USOVERSHENSTVOVANIJ.

iNTERESNO OTMETITX, CHTO SLOVO "HESHIROVANIE" ("hashing") V EGO NYNESHNEM
ZNACHENII, VEROYATNO, NE POYAVLYALOSX V PECHATI DO KONCA 60-H GODOV, HOTYA K
TOMU VREMENI V RAZNYH CHASTYAH SVETA ONO UZHE STALO OBSHCHEPRINYATYM ZHARGONOM.
pO-VIDIMOMU, VPERVYE |TO SLOVO BYLO ISPOLXZOVANO V KNIGE hELLERM|NA
[Digital Computers System Principles (New York, 1967), 152]. iZ PRIMERNO
60~DOKUMENTOV, OTNOSYASHCHIHSYA K 1953--1967~GG., IZUCHENNYH AVTOROM
PRI NAPISANII DANNOGO PARAGRAFA, SLOVO "HESHIROVANIE" VSTRECHAETSYA LISHX
ODNAZHDY---V NEOPUBLIKOVANNOM DOKUMENTE FIRMY, SOSTAVLENNOM u.~pETERSONOM
(1961~G.). kAK PO VOLSHEBSTVU, GLAGOL "HESHIROVATX" (to hash) V SEREDINE
60-H GODOV STAL STANDARTNYM TERMINOM DLYA PREOBRAZOVANIYA KLYUCHA, HOTYA
ISPOLXZOVATX TAKOE NEDOSTOJNOE SLOVO V PECHATI NIKTO NE OSMELIVALSYA DO 1967~G.!

\excercises
\ex[20] pREDPOLOZHIM, CHTO   BAJTY 1, 2, 3 KLYUCHA~$K$ SODERZHAT KODY LITER,
MENXSHIE~30. v KAKIH PREDELAH ZAKLYUCHENO SODERZHIMOE~|rI1|, KOGDA
DOSTIGAETSYA INSTRUKCIYA~|9H| V TABL.~1?

\ex[20] nAJDITE DOVOLXNO IZVESTNOE ANGLIJSKOE SLOVO, KOTOROE MOZHNO
DOBAVITX V TABL.~1 BEZ IZMENENIYA PROGRAMMY.

%%644
\ex[23] oB®YASNITE, POCHEMU PROGRAMMU V TABL.~1 NELXZYA ZAMENITX NA
BOLEE PROSTUYU, NACHINAYUSHCHUYUSYA SO SLEDUYUSHCHIH PYATI INSTRUKCIJ:
\medskip
\centerline{|LD1  K(1:1)| ILI~|LD1N  K(1:1)|}
\centerline{|LD2  K(2:2)| ILI~|LD2N  K(2:2)|}
\centerline{
\vbox{
 \hbox{\strut|INC1  $a$, 2|}
 \hbox{\strut|LD2   K(3:3)|}
 \hbox{\strut|J2Z   9F|}
}}
\medskip
NI PRI KAKOJ KONSTANTE~$a$, UCHITYVAYA, CHTO RAZNYE KLYUCHI NE MOGUT IMETX
ODINAKOVYE HESH-ADRESA.

\ex[m30] sKOLXKO CHELOVEK NUZHNO PRIGLASITX NA VECHERINKU, CHTOBY S
VEROYATNOSTXYU $>{1\over2}$ NASHLISX \emph{TROE,} IMEYUSHCHIE ODIN I TOT ZHE
DENX ROZHDENIYA?

\ex[15] mISTER tUPICA PISAL KOMPILYATOR S fortranA, ISPOLXZUYA DESYATICHNUYU
MASHINU \MIX, I PERED NIM VSTALA ZADACHA SOZDANIYA TABLICY SIMVOLOV DLYA
HRANENIYA IMEN PEREMENNYH KOMPILIRUEMOJ PROGRAMMY. dLINA |TIH IMEN
OGRANICHENA DESYATXYU LITERAMI. oN RESHIL ISPOLXZOVATX RASSEYANNUYU TABLICU
S~$M=100$ I BYSTRUYU HESH-FUNKCIYU~$h(K)=\hbox{KRAJNNJ LEVYJ BAJT~$K$}$.
hOROSHO LI |TO?

\ex[15] rAZUMNO LI ZAMENITX PERVYE DVE INSTRUKCII V~(3) NA~|LDA K|;
|ENTX 0|?

\ex[vm30] \exhead(pOLINOMIALXNOE HESHIROVANIE.) cELX NASTOYASHCHEGO
UPRAZHNENIYA---RASSMOTRETX POSTROENIE MNOGOCHLENOV~$P(x)$ TIPA~(10), KOTORYE
PREOBRAZUYUT $n\hbox{-BITOVYE}$ KLYUCHI V $m\hbox{-BITOVYE}$ ADRESA I PRI
|TOM RAZNYE KLYUCHI, OTLICHAYUSHCHIESYA NE BOLEE CHEM $t$~BITAMI, POLUCHAT RAZNYE
ADRESA. pO ZADANNYM ZNACHENIYAM~$n$, $t\le n$, I CELOMU CHISLU~$k$, TAKOMU,
CHTO~$n$ DELIT~$2^k-1$, MY POSTROIM MNOGOCHLEN, STEPENX OT KOTOROGO
YAVLYAETSYA FUNKCIEJ~$n$, $t$ I~$k$. (oBYCHNO, ESLI |TO NEOBHODIMO,
$n$~UVELICHIVAETSYA, PO|TOMU $k$~MOZHNO VYBRATX DOSTATOCHNO MALYM.)

pUSTX $S$---MINIMALXNOE MNOZHESTVO CELYH CHISEL, TAKOE,
CHTO~$\set{1,2,~\ldots, t}\subseteq S$ I~$(2j) \bmod n \in S$ DLYA
VSEH~$j\in S$. nAPRIMER, ESLI~$n=15$, $k=4$, $t=6$, IMEEM~$S=\set{1, 2, 3,
4, 5, 6, 8, 10, 12, 9}$. oPREDELIM TEPERX MNOGOCHLEN~$P(x)= \prod_{j\in S}
(x-\alpha^j)$, GDE $\alpha$~ESTX |LEMENT PORYADKA~$n$ KONECHNOGO
POLYA~$GF(2^k)$, A KO|FFICIENTY~$P(x)$ VYCHISLYAYUTSYA V |TOM POLE. sTEPENX~$m$
MNOGOCHLENA~$P(x)$ RAVNA CHISLU |LEMENTOV V~$S$.
eSLI~$\alpha^j$---KORENX~$P(x)$, TO I~$\alpha^2j$---KORENX; OTSYUDA SLEDUET,
CHTO KO|FFICIENTY~$P(x)$ UDOVLETVORYAYUT SOOTNOSHENIYU~$p^2_i=p_i$, T.~E.~ONI
RAVNY~0 ILI~1.

dOKAZHITE, CHTO ESLI~$R(x)=r_{n-1}x^{n-1}+\cdots+r_1x+r_0$---NENULEVOJ
MNOGOCHLEN PO MODULYU~2 S NE BOLEE CHEM $t$~NENULEVYMI KO|FFICIENTAMI,
TO~$R(x)$ NE KRATEN~$P(x)$ PO MODULYU~2. [oTSYUDA SLEDUET, CHTO
SOOTVETSTVUYUSHCHAYA HESH-FUNKCIYA VEDET SEBYA OBESHCHANNYM OBRAZOM.]

\ex[m34] \exhead(tEOREMA O TREH DLINAH.) pUSTX~$\theta$---IRRACIONALXNOE
CHISLO, LEZHASHCHEE MEZHDU~0 I~1, PREDSTAVLENIE KOTOROGO V VIDE PRAVILXNOJ
NEPRERYVNOJ DROBI (OBOZNACHENIYA P.~4.5.3) ESTX~$\theta=/a_1, a_2, a_3,
~\ldots/$. pUSTX~$q_0=0$, $p_0=1$, $q_1=1$, $p_1=0$
I~$q_{k+1}=a_kq_k+q_{k-1}$, $p_{k+1}=a_kp_k+p_{k-1}$ PRI~$k\ge1$.
oBOZNACHIM~$x \bmod 1=x-\floor{x}$ CHEREZ~$\{x\}$, A~$x-\ceil{x}+1$
CHEREZ~$\{x\}^+$. bUDEM NUMEROVATX OTREZKI V TOM PORYADKE, KAK ONI
POLUCHAYUTSYA PRI POSLEDOVATELXNYH VSTAVKAH V INTERVAL~$[0, 1]$
TOCHEK~$\{\theta\}$, $\{2\theta\}$, $\{3\theta\}$,~\dots, TAK CHTO PERVYJ
OTREZOK DANNOJ DLINY IMEET NOMER~0, VTOROJ---NOMER~1 I~T.~D. dOKAZHITE, CHTO
VSE SLEDUYUSHCHIE UTVERZHDENIYA VERNY.
lEVYM KONCOM INTERVALA NOMER~$s$ DLINY~$\{t\theta\}$,
GDE~$t=rq_k+q_{k-1}$, $0\le r<a_k$, $k$~CHETNO, a~$0\le s <q_k$,
SLUZHIT TOCHKA~$\{s\theta\}$, A PRAVYM---TOCHKA~$\{(s+t)\theta\}^+$.
lEVYM KONCOM INTERVALA NOMER~$s$ DLINY~$1-\{t\theta\}$,
GDE~$t=rq_k+q_{k-1}$, $0 \le r < a_k$, $k$~NECHETNO I~$0 \le s < q_k$,
SLUZHIT TOCHKA~$\{(s+t)\theta\}$, A PRAVYM---TOCHKA~$\{s\theta\}^+$.
lYUBOE NATURALXNOE CHISLO MOZHNO EDINSTVENNYM OBRAZOM PREDSTAVITX V
VIDE~$n=rq_k+q_{k-1}+s$ PRI~$k\ge 1$, $1 \le r \le a_k$, $0 \le s < q_k$.
v |TIH OBOZNACHENIYAH PERED VSTAVKOJ TOCHKI~$\{n\theta\}$ IMEETSYA $n$~INTERVALOV:
%%645
PERVYE $s$~INTERVALOV (S NOMERAMI~0,~\dots, $s-1$) DLINY~$\{(-1)^k(rq_k+q_{k-1})\theta\}$;
PERVYE $n-q_k$~INTERVALOV (S NOMERAMI~0,~\dots, $n-q_k-1$) DLINY~$\{(-1)^k q_k\theta\}$;
POSLEDNIE $q_k-s$~INTERVALOV (S NOMERAMI~$s$,~\dots, $q_k-1$) DLINY~$\{(-1)^k((r-1)q_k+q_{k-1})\theta\}$.

oPERACIYA VSTAVKI~$\{n\theta\}$ USTRANYAET INTERVAL NOMER~$s$ POSLEDNEGO
TIPA I PREOBRAZUET EGO V INTERVAL NOMER~$s$ PERVOGO TIPA I INTERVAL
NOMER~$n-q_k$ VTOROGO TIPA.

\ex[M30] tEOREMA~S UTVERZHDAET, CHTO PRI POSLEDOVATELXNYH VSTAVKAH
TOCHEK~$\{\theta\}$, $\{2\theta\}$,~\dots V INTERVAL~$[0, 1]$ KAZHDAYA NOVAYA
TOCHKA RAZBIVAET ODIN IZ
NAIBOLXSHIH IMEYUSHCHIHSYA INTERVALOV. eSLI INTERVAL~$[a, c]$ RAZBIT TAKIM
OBRA|OM NA DVE
CHASTI~$[a, b]$, $[b, c]$, MY NAZOVEM |TO \dfn{PLOHIM RAZBIENIEM,} KOGDA
ODNA IZ CHASTEJ BOLEE CHEM VDVOE DLINNEE DRUGOJ, T.~E.~KOGDA $b-a>2(c-b)$
ILI~$c-b>2(b-a)$.

dOKAZHITE, CHTO ESLI~$\theta\ne \phi^{-1}$ ILI~$\theta\ne\phi^{-2}$, TO PRI
NEKOTOROM~$n$ TOCHKA~$\{n\theta\}$ DAET PLOHOE RAZBIENIE; ESLI
ZHE~$\theta=\phi^{-1}$ ILI~$\theta=\phi^{-2}$, TO PLOHIH RAZBIENIJ NE POLUCHAETSYA.

\ex[m43] (r.~gR|HEM.) dOKAZHITE ILI OPROVERGNITE SLEDUYUSHCHEE
\emph{PREDPOLOZHENIE O $3d$~DLINAH:} ESLI~$\theta$, $\alpha_1$,~\dots,
$\alpha_d$--- VESHCHESTVENNYE CHISLA, PRICHEM~$\alpha_1=0$, ESLI~$n_1$,~\dots,
$n_d$---NATURALXNYE CHISLA I ESLI TOCHKI~$\{n\theta+\alpha_i\}$ VSTAVLYAYUTSYA V
INTERVAL~$[0, 1]$ PRI~$0\le n < n_i$, $1\le i\le d$, TO
$n_1+\cdots+n_d$~POLUCHAYUSHCHIHSYA INTERVALOV (VOZMOZHNO, PUSTYH) IMEYUT NE BOLEE
$3d$~RAZLICHNYH DLIN.

\ex[16] oBYCHNO UDACHNYE POISKI PROIZVODYATSYA CHASHCHE NEUDACHNYH rAZUMNO LI
STROKI~12--13 PROGRAMMY~C POMENYATX MESTAMI SO STROKAMI~10--11?

\rex[21] pOKAZHITE, CHTO MOZHNO TAK PEREPISATX PROGRAMMU~C, CHTO VO
VNUTRENNEM CIKLE OSTANETSYA LISHX ODNA INSTRUKCIYA USLOVNOGO PEREHODA.
sRAVNITE VREMENA RABOTY MODIFICIROVANNOJ I PERVONACHALXNOJ PROGRAMM.

\ex[24] \exhead(sOKRASHCHENNYE KLYUCHI.) pUSTX $h(K)$---HESH-FUNKCIYA, a
$g(K)$---TAKAYA FUNKCIYA OT~$K$, CHTO, ZNAYA~$h(K)$ I~$g(K)$, MOZHNO NAJTI~$K$.
nAPRIMER, PRI HESHIROVANII DELENIEM MOZHNO POLOZHITX~$h(K)=K \bmod M$
I~$g(K)=\floor{K/M}$; V MULXTIPLIKATIVNOM HESHIROVANII V KACHESTVE~$h(K)$
MOZHNO VZYATX STARSHIE RAZRYADY~$(AK/w)\bmod 1$, A V KACHESTVE~$g(K)$---OSTALXNYE
RAZRYADY.

pOKAZHITE, CHTO PRI ISPOLXZOVANII METODA CEPOCHEK BEZ NALOZHENIYA V KAZHDOJ
ZAPISI VMESTO~$K$ DOSTATOCHNO HRANITX~$g(K)$. (eTO INOGDA |KONOMIT
PROSTRANSTVO, NEOBHODIMOE DLYA POLEJ SSYLOK.) iZMENITE ALGORITM~C, CHTOBY
ON MOG RABOTATX S TAKIMI SOKRASHCHENNYMI KLYUCHAMI, USTRANIV NALOZHENIE SPISKOV,
 NO NE ISPOLXZUYA VSPOMOGATELXNYH YACHEEK PAMYATI DLYA "PEREPOLNYAYUSHCHIH" ZAPISEJ.

\ex[24] (e.~eLXKOK.) pOKAZHITE, CHTO BOLXSHAYA RASSEYANNAYA TABLICA
MOZHET ISPOLXZOVATX OBSHCHUYU S DRUGIMI SVYAZANNYMI SPISKAMI PAMYATX. pUSTX
KAZHDOE SLOVO SPISOCHNOJ PAMYATI SODERZHIT DVUHBITOVOE POLE~|TAG|, IMEYUSHCHEE
SLEDUYUSHCHIJ SMYSL:
{\medskip\narrower
\item{$|TAG|(|P|)=0$} OBOZNACHAET SLOVO V SPISKE SVOBODNOGO PROSTRANSTVA;
$|LINK|(|P|)$~UKAZYVAET NA SLEDUYUSHCHEE SVOBODNOE SLOVO.
%
\item{$|TAG|(|P|)=1$} OBOZNACHAET ISPOLXZUEMOE SLOVO, NE YAVLYAYUSHCHEESYA CHASTXYU
RASSEYANNOJ TABLICY; FORMAT OSTALXNYH POLEJ |TOGO SLOVA PROIZVOLEN.
%
\item{$|TAG|(|P|)=2$} OBOZNACHAET SLOVO V RASSEYANNOJ TABLICE;
$|LINK|(|P|)$~UKAZYVAET NA DRUGOE SLOVO. vSYAKIJ RAZ, KOGDA PRI OBRABOTKE
SPISKA, NE YAVLYAYUSHCHEGOSYA CHASTXYU RASSEYANNOJ TABLICY, MY DOSTIGAEM SLOVA
S~$|TAG|(|P|)=2$, NUZHNO USTANOVITX~$P\asg|LINK|(|P|)$ DO POLUCHENIYA SLOVA
S~$|TAG|(|P|)\le 1$. (dLYA |FFEKTIVNOSTI MOZHNO IZMENITX ODNU IZ
PREDSHESTVUYUSHCHIH SSYLOK; TOGDA NE PRIDETSYA SNOVA I SNOVA PERESKAKIVATX CHEREZ
ODNI I TE ZHE |LEMENTY RASSEYANNOJ TABLICY.)
\medskip}

pOKAZHITE, KAK OPREDELITX PODHODYASHCHIE ALGORITMY DLYA VSTAVKI I VYBORKI KLYUCHEJ
IZ TAKOJ KOMBINIROVANNOJ TABLICY, PREDPOLAGAYA, CHTO V SLOVE
S~$|TAG|(|P|)=2$ IMEETSYA ESHCHE ODNO POLE SSYLKI~$|AUX|(|P|)$.

\ex[16] pOCHEMU V ALGORITMAH~L I~D RAZUMNO FIKSIROVATX
PEREPOLNENIE PRI~$N=M-1$, A NE PRI~$N=M$?
%%646

\ex[10] v PROGRAMME~L GOVORITSYA, CHTO $K$~NE DOLZHNO RAVNYATXSYA~0. a VDRUG NA
SAMOM DELE ONA RABOTAET DAZHE PRI~$K=0$?

\ex[15] pOCHEMU NE POLOZHITX PROSTO~$h_2(K)=h_1(K)$ V~(25), ESLI~$h_1(K)\ne0$?

\rex[21] dEJSTVITELXNO LI~(31) PREDPOCHTITELXNEE~(30) V KACHESTVE
ZAMENY STROK~10--13 PROGRAMMY~D? dAJTE OTVET, ISHODYA IZ SREDNIH
ZNACHENIJ~$A$, $S1$ I~$C$.

\ex[40] pROVERXTE |MPIRICHESKI VOZDEJSTVIE OGRANICHENIYA OBLASTI
ZNACHENIJ~$h_2(K)$ V ALGORITME~D TAK, CHTO: (a)~$1\le h_2(K)\le r$ PRI~$r=1$,
 2, 3,~\dots, 10;
(b)~$1\le h_2(K)\le\rho M$ PRI $\rho={1\over10}$, ${2\over10}$,
${3\over10}$,~\dots, ${9\over10}$.

\ex[m25] (r.~kRUTAR.) iZMENITE ALGORITM~D SLEDUYUSHCHIM OBRAZOM, USTRANYAYA
HESH-FUNKCIYU~$h_2(K)$: V SHAGE~D3 USTANOVITX~$c\asg 0$, A V NACHALE
SHAGA~D4 USTANOVITX~$c\asg c+1$. dOKAZHITE, CHTO, ESLI~$M=2^m$,
SOOTVETSTVUYUSHCHAYA POSLEDOVATELXNOSTX PROB~$h_1(K)$, $(h_1(K)-1)\bmod M$,
~\dots, $\left(h_1(K)-\perm{M}{2}\right)\bmod M$ BUDET
PERESTANOVKOJ MNOZHESTVA~$\set{0, 1,~\dots, M-1}$. kAK |TOT METOD, BUDUCHI
ZAPROGRAMMIROVANNYM DLYA MASHINY~\MIX, VYGLYADIT PO SRAVNENIYU S TREMYA
PROGRAMMAMI, RASSMATRIVAEMYMI NA RIS.~42, ESLI POVEDENIE ANALOGICHNO
SLUCHAJNOMU OPROBOVANIYU SO VTORICHNYM OKUCHIVANIEM?

\rex[20] pREDPOLOZHIM, CHTO MY HOTELI BY UDALITX ZAPISX IZ TABLICY,
 POSTROENNOJ S POMOSHCHXYU ALGORITMA~D, POMECHAYA SOOTVETSTVUYUSHCHUYU POZICIYU
KAK UDALENNUYU. sLEDUET LI PRI |TOM UMENXSHATX ZNACHENIE PEREMENNOJ~$N$,
UPRAVLYAYUSHCHEJ ALGORITMOM~D?

\ex[27] dOKAZHITE, CHTO ALGORITM~R OSTAVLYAET TABLICU TOCHNO V TAKOM ZHE VIDE,
KAK ESLI BY $|KEY|[i]$ NE BYL SPERVA VSTAVLEN.

\rex[23] pRIDUMAJTE ALGORITM, ANALOGICHNYJ ALGORITMU~R, DLYA
UDALENIYA |LEMENTOV IZ RASSEYANNOJ TABLICY CEPOCHEK, POSTROENNOJ S POMOSHCHXYU
ALGORITMA~C.

\ex[m20] pREDPOLOZHIM, CHTO MNOZHESTVO VSEH VOZMOZHNYH KLYUCHEJ SOSTOIT IZ
$MP$~|LEMENTOV, PRICHEM ROVNO $P$~KLYUCHEJ IMEYUT DANNYJ HESH-ADRES. (v
REALXNYH SLUCHAYAH $P$~OCHENX VELIKO; NAPRIMER, ESLI KLYUCHAMI YAVLYAYUTSYA
PROIZVOLXNYE DESYATIZNACHNYE CHISLA, A~$M=10^3$, TO~$P=10^7$.) pREDPOLOZHIM,
CHTO~$M\ge7$ I~$N=7$. pUSTX IZ MNOZHESTVA VSEH VOZMOZHNYH KLYUCHEJ SLUCHAJNYM
OBRAZOM VYBIRAYUTSYA SEMX RAZLICHNYH |LEMENTOV. vYRAZITE CHEREZ~$M$ I~$P$
TOCHNUYU VEROYATNOSTX POLUCHENIYA HESH-POSLEDOVATELXNOSTI 1~2~6~2~1~6~1
(T.~E.~$h(K_1)=1$, $h(K_2)=2$,~\dots, $h(K_7)=1$).

\ex[M19] oB®YASNITE, POCHEMU VERNA FORMULA~(39).

\ex[M20] sKOLXKO HESH-POSLEDOVATELXNOSTEJ $a_1\ a_2~\ldots a_9$ PRI
ISPOLXZOVANII LINEJNOGO OPROBOVANIYA DADUT KARTINU ZANYATYH YACHEEK~(21)?

\ex[m27] zAVERSHITE DOKAZATELXSTVO TEOREMY~K. [\emph{uKAZANIE:} PUSTX
$$
s(n,x,y)=\sum_{k\ge0}\perm{n}{k}(x+k)^{k+1}(y-k)^{n-k-1}(y-n);
$$
ISPOLXZUJTE BINOMIALXNUYU TEOREMU aBELYA [FORMULA~(1.2.6-16)] DLYA
DOKAZATELXSTVA TOGO, CHTO~$s(n, x, y)=x(x+y)^n+ns(n-1, x+1, y-1)$]

\ex[M30] v TE DAVNIE VREMENA, KOGDA evm BYLI GORAZDO MEDLENNEE NYNESHNIH,
PO MIGANIYU LAMPOCHEK MOZHNO BYLO SUDITX, S KAKOJ SKOROSTXYU RABOTAET
ALGORITM~L. kOGDA TABLICA STANOVILASX POCHTI POLNOJ, ODNI
|LEMENTY OBRABATYVALISX OCHENX BYSTRO, A DRUGIE VESXMA MEDLENNO.

eTI NABLYUDENIYA NAVODYAT NA MYSLX O TOM, CHTO, ESLI ISPOLXZUETSYA LINEJNOE
OPROBOVANIE, SREDNEKVADRATICHNOE OTKLONENIE VELICHINY~$C'_N$ DOVOLXNO
VELIKO. nAJDITE FORMULU, VYRAZHAYUSHCHUYU DISPERSIYU CHEREZ FUNKCII~$Q_r$,
OPREDELENNYE V TEOREME~K, I OCENITE EE PRI~$N=\alpha M$ I~$M\to\infty$.

\ex[M21] \exhead(zADACHA O STOYANKE.) nA NEKOJ ULICE S ODNOSTORONNIM
DVIZHENIEM IMEETSYA $m$~MEST DLYA STOYANKI, RASPOLOZHENNYH V RYAD I
PERENUMEROVANNYH OT~1 DO~$m$. mUZH VEZET V AVTOMOBILE SVOYU DREMLYUSHCHUYU ZHENU.
vNEZAPNO ZHENA PROSYPAETSYA I TREBUET NEMEDLENNO OSTANOVITXSYA. oN POSLUSHNO
OSTANAVLIVAETSYA
%%647
NA PERVOM SVOBODNOM MESTE, NO ESLI NET SVOBODNYH MEST, K KOTORYM
MOZHNO POD®EHATX, NE POVORACHIVAYA OBRATNO (T.~E.~ESLI ZHENA PROSNULASX, KOGDA
MASHINA DOSTIGLA $k\hbox{-GO}$~MESTA DLYA STOYANKI, NO VSE "POZICII"~$k$,
$k+1$,~\dots, $m$ ZANYATY), MUZH PRINOSIT SVOI IZVINENIYA I EDET DALXSHE

pREDPOLOZHIM, CHTO |TO PROISHODIT S $n$~RAZLICHNYMI MASHINAMI, PRICHEM
$j-\hbox{YA}$~ZHENA PROSYPAETSYA V MOMENT, KOGDA MASHINA NAHODITSYA PERED
MESTOM~$a_j$. sKOLXKO IMEETSYA TAKIH POSLEDOVATELXNOSTEJ~$a_1$~\dots{}$a_n$,
 PRI KOTORYH VSE MASHINY UDACHNO PRIPARKUYUTSYA, PREDPOLAGAYA, CHTO
PERVONACHALXNO ULICA PUSTA I NIKTO SO STOYANKI NE UEZZHAET? nAPRIMER,
ESLI~$m=n=9$
I~$a_1\ldots{}a_9=3\ 1\ 4\ 1\ 5\ 9\ 2\ 6\ 5$, AVTOMOBILI RASPOLOZHATSYA
SLEDUYUSHCHIM OBRAZOM:
\picture{rIS. STR. 647}
[uKAZANIE: VOSPOLXZUJTESX ANALIZOM LINEJNOGO OPROBOVANIYA.]

\ex[m28] (dZHON~rIORDAN.) pOKAZHITE, CHTO V ZADACHE O STOYANKE IZ
UPR.~29 PRI~$n=m$ VSE MASHINY PRIPARKUYUTSYA TOGDA I TOLXKO TOGDA, KOGDA
SUSHCHESTVUET PERESTANOVKA~$p_1$ $p_2$~\dots{} $p_n$ MNOZHESTVA~$\set{1, 2,
~\ldots, P}$, TAKAYA,
CHTO~$a_j\le p_j$ DLYA VSEH~$j$.

\ex[m40] eSLI V ZADACHE O STOYANKE (UPR.~29) $n=m$, CHISLO RESHENIJ
OKAZYVAETSYA RAVNYM~$(n+1)^{n-1}$, A IZ UPR.~2.3.4.4-22 MY ZNAEM, CHTO |TO
ESTX CHISLO SVOBODNYH, DEREVXEV NAD~$n+1$~RAZLICHNYMI VERSHINAMI! nAJDITE
INTERESNUYU ZAVISIMOSTX MEZHDU POSLEDOVATELXNOSTYAMI OSTANOVOK I DEREVXYAMI.

\ex[m26] dOKAZHITE, CHTO SISTEMA URAVNENIJ~(44) IMEET EDINSTVENNOE
RESHENIE~$(C_0, C_1,~\ldots, C_{M-1})$ PRI LYUBYH CELYH
NEOTRICATELXNYH~$b_0$, $b_1$,~\dots, $b_{M-1}$, SUMMA KOTORYH MENXSHE~$M$.
pOSTROJTE ALGORITM DLYA NAHOZHDENIYA |TOGO RESHENIYA.

\ex[m23] oB®YASNITE, POCHEMU~(51) VSEGO LISHX PRIBLIZHENIE K
ISTINNOMU SREDNEMU CHISLU PROB, PROIZVODIMYH ALGORITMOM~L. [kAKIE
NESTROGOSTI BYLI DOPUSHCHENY PRI VYVODE~(51)?]

\ex[m22] cELX |TOGO UPRAZHNENIYA---ISSLEDOVATX SREDNEE, CHISLO PROB V
RASSEYANNOJ TABLICE CEPOCHEK, KOGDA SPISKI OSTAYUTSYA RAZDELXNYMI, KAK NA
RIS~38.
(a)~chEMU RAVNA VEROYATNOSTX~$P_{Nk}$ TOGO, CHTO DANNYJ SPISOK IMEET
DLINU~$k$, ESLI $M^N$~HESH-POSLEDOVATELXNOSTEJ~(35) RAVNOVEROYATNY?
(b)~nAJDITE PROIZVODYASHCHUYU FUNKCIYU~$P_N(z)\sum_{k\ge0} P_{Nk} z^k$.
(c)~vYRAZITE CHEREZ |TU PROIZVODYASHCHUYU FUNKCIYU
SREDNEE CHISLO PROB PRI UDACHNOM I NEUDACHNOM POISKE. (pREDPOLAGAETSYA,
CHTO NEUDACHNYJ POISK V SPISKE DLINY~$k$ TREBUET $k+\delta_{k0}$~PROB.)

\ex[m21] (pRODOLZHENIE UPR.~34.) nAJDITE SREDNEE CHISLO PROB PRI NEUDACHNOM
POISKE, ESLI OTDELXNYE SPISKI UPORYADOCHENY PO ZNACHENIYAM KLYUCHEJ.

\ex[m22] nAJDITE DISPERSIYU CHISLA PROB DLYA METODA RAZDELXNYH CEPOCHEK, ESLI
POISK BYL NEUDACHNYM. (sM.~(18).)

\rex[m29] nAJDITE DISPERSIYU CHISLA PROB DLYA METODA RAZDELXNYH CEPOCHEK, ESLI
POISK BYL UDACHNYM. (sM.~(19).)

\ex[m32] \exhead(iSPOLXZOVANIE DEREVXEV PRI HESHIROVANII.) iSKUSNYJ
PROGRAMMIST MOG BY POPYTATXSYA ISPOLXZOVATX V METODE CEPOCHEK BINARNYE
DEREVXYA POISKA VMESTO LINEJNYH SPISKOV, KOMBINIRUYA TAKIM OBRAZOM
ALGORITM~6.2.2t
S HESHIROVANIEM. pROANALIZIRUJTE SREDNEE CHISLO PROB, NUZHNYH |TOMU
KOMBINIROVANNOMU ALGORITMU I V SLUCHAE UDACHNOGO, I V SLUCHAE NEUDACHNOGO
POISKA. [\emph{uKAZANIE:} SR.~S FORMULOJ~(5.2.1-11).]

\ex[M30] cELX |TOGO UPRAZHNENIYA---PROANALIZIROVATX SREDNEE CHISLO PROB V
ALGORITME~C (SRASTAYUSHCHIESYA CEPOCHKI). oBOZNACHIM CHEREZ~$c(k_1, k_2, k_3,
~\dots)$ KOLICHESTVO HESH-POSLEDOVATELXNOSTEJ~(35), ZASTAVLYAYUSHCHIH ALGORITM~C
OBRAZOVATX ROVNO $k_1$~SPISKOV DLINY~1, $k_2$~SPISKOV DLINY~2 I T.~D.;
$k_1+2k_2+3k_3+\ldots=N$.  nAJDITE REKURRENTNOE SOOTNOSHENIE, OPREDELYAYUSHCHEE
|TI CHISLA, I ISPOLXZUJTE
%%648
EGO PRI VYVODE PROSTOJ FORMULY DLYA SUMMY
$$
S_N=\sum_{\scriptstyle j\ge 1\atop \scriptstyle k_1+k_2+\ldots=N}k_jc(k_1,
k_2, \ldots).
$$

kAK SVYAZANA VELICHINA $S_N$ S CHISLOM PROB VO VREMYA NEUDACHNOGO POISKA S
ISPOLXZOVANIEM ALGORITMA~C?

\ex[M33] nAJDITE DISPERSIYU CHISLA PROB, PROIZVODIMYH V ALGORITME~C,  ESLI
POISK BYL NEUDACHNYM (SM.~(15).)

\ex[m40] pROANALIZIRUJTE, SKOLXKO RAZ V SREDNEM |R|~UMENXSHAETSYA NA~1 PRI
VSTAVKE $(N+1)\hbox{-GO}$~|LEMENTA S POMOSHCHXYU ALGORITMA~C. (oBOZNACHIM |TO CHISLO
CHEREZ~$T_N$.)

\ex[m20] vYVEDITE~(17).

\ex[m42] pROANALIZIRUJTE MODIFIKACIYU ALGORITMA~C, ISPOLXZUYUSHCHUYU TABLICU
RAZMERA~$M'\ge M$. dLYA HESHIROVANIYA ISPOLXZUYUTSYA LISHX PERVYE~$M$ POZICIJ,
TAK CHTO PERVYE $M'-M$~SVOBODNYH UZLOV, NAJDENNYH V SHAGE~C5, RASPOLOZHATSYA V
DOPOLNITELXNOJ CHASTI TABLICY. kAKOJ VYBOR~$M$ PRI FIKSIROVANNOM~$M'$,
$1\le M \le M'$, DAET NAILUCHSHIE HARAKTERISTIKI?

\ex[m43] \exhead(sLUCHAJNOE OPROBOVANIE S VTORICHNYM SKUCHIVANIEM.) cELX
|TOGO  UPRAZHNENIYA---OPREDELITX SREDNEE CHISLO PROB V SHEME OTKRYTOJ ADRESACIJ
 S POSLEDOVATELXNOSTXYU OPROBOVANIJ
$$
h(K), (h(K)+p_1)\bmod M, (h(K)+p_2)\bmod M, \ldots, (h(K)+p_{M-1})\bmod M,
$$
GDE $p_1$ $p_2$~\dots $p_{M-1}$---SLUCHAJNO-VYBRANNAYA PERESTANOVKA
MNOZHESTVA~$\set{1, 2,~\ldots, M-1}$, ZAVISYASHCHAYA OT~$h(K)$. iNYMI SLOVAMI, U
VSEH KLYUCHEJ S ODINAKOVYM ZNACHENIEM~$h(K)$ ODNA I TA ZHE POSLEDOVATELXNOSTX
OPROBOVANIJ, A $(M-1)!^M$~VOZMOZHNYH VYBOROV $M$~POSLEDOVATELXNOSTEJ PROB S
|TIM SVOJSTVOM RAVNOVEROYATNY.

mOZHNO TOCHNO SMODELIROVATX SITUACIYU, ESLI NAD PERVONACHALXNO PUSTYM
 LINEJNYM MASSIVOM RAZMERA~$m$ VYPOLNITX SLEDUYUSHCHUYU PROCEDURU. dELAEM
$n$~RAZ  TAKUYU OPERACIYU:
{\medskip\narrower

s VEROYATNOSTXYU~$p$ ZAJMEM KRAJNYUYU LEVUYU SVOBODNUYU POZICIYU. v PROTIVNOM
SLUCHAE (T.~E.\ S~VEROYATNOSTXYU~$q=1-p$) VYBEREM LYUBUYU POZICIYU TABLICY,
KROME KRAJNEJ LEVOJ, PRICHEM VSE $m-1$~POZICIJ RAVNOVEROYATNY. eSLI
VYBRANNAYA POZICIYA SVOBODNA, ZAJMEM EE; V PROTIVNOM SLUCHAE VYBEREM
\emph{LYUBUYU} SVOBODNUYU POZICIYU (VKLYUCHAYA SAMUYU LEVUYU) I ZAJMEM EE, SCHITAYA,
 CHTO VSE SVOBODNYE POZICII RAVNOVEROYATNY.
\medskip}
nAPRIMER, ESLI~$m=5$ I~$n=3$, TO POSLE VYPOLNENIYA OPISANNOJ
PROCEDURY KONFIGURACIYA (ZANYATO, ZANYATO, SVOBODNO, ZANYATO, SVOBODNO)
POLUCHAETSYA S VEROYATNOSTXYU
$$
{7\over 192}qqq+{1\over6}pqq+{1\over6}qpq+{11\over64}qqp+{1\over3}ppq+{1\over4}pqp+{1\over4}qpp.
$$
(eTA PROCEDURA SOOTVETSTVUET SLUCHAJNOMU OPROBOVANIYU S VTORICHNYM
SKUCHIVANIEM, KOGDA~$p=1/m$, IBO MOZHNO PERENUMEROVATX |LEMENTY TABLICY TAK,
CHTO NEKOTORAYA POSLEDOVATELXNOSTX PROB SOVPADET S~0, 1, 2,~\dots, A VSE
OSTALXNYE BUDUT SLUCHAJNYMI.)

nAJDITE FORMULU DLYA SREDNEGO CHISLA ZANYATYH POZICIJ V LEVOM KONCE MASSIVA
(DVE V PRIVEDENNOM PRIMERE). oPREDELITE TAKZHE ASIMPTOTICHESKOE ZNACHENIE
|TOJ VELICHINY PRI~$p=1/m$, $n=\alpha(m+1)$, $m\to\infty$.

\ex[m43] rESHITE ANALOG UPR.~44 S \emph{TRETICHNYM SKUCHIVANIEM,} KOGDA
POSLEDOVATELXNOSTX PROB NACHINAETSYA S~$h_1(K)$, $(h_1(K)+h_2(K))\bmod M$;
VYBOR DALXNEJSHIH PROB SLUCHAEN I ZAVISIT LISHX OT~$h_1(K)$ I~$h_2(K)$
(T.~E.~$(M-2)!^{M(M-1)}$ VOZMOZHNYH VYBOROV POSLEDOVATELXNOSTEJ PROB S |TIM
SVOJSTVOM SCHITAYUTSYA
%%649
RAVNOVEROYATNYMI). yaVLYAETSYA LI PREDLAGAEMAYA PROCEDURA ASIMPTOTICHESKI
|KVIVALENTNOJ RAVNOMERNOMU OPROBOVANIYU?

\ex[M42] nAJDITE~$C'_N$ I~$C_N$ DLYA METODA OTKRYTOJ ADRESACII,
ISPOLXZUYUSHCHEGO POSLEDOVATELXNOSTX PROB
$$
h(K), 0, 1, \ldots, h(K-1), h(K)+1, \ldots, M-1.
$$
\ex[M25] kAKOE SREDNEE CHISLO PROB POTREBUETSYA DLYA OTKRYTOJ ADRESACII S
POSLEDOVATELXNOSTXYU PROB
$$
h(K), h(K)-1, h(K)+1, h(K)-2, h(K)+2,\ldots\,?
$$
eTA POSLEDOVATELXNOSTX BYLA ODNAZHDY PREDLOZHENA IZ-ZA TOGO, CHTO VSE
RASSTOYANIYA MEZHDU POSLEDOVATELXNYMI PROBAMI PRI CHETNOM~$M$ RAZLICHNY
[\emph{uKAZANIE: NEBOLXSHAYA  HITROSTX SUSHCHESTVENNO OBLEGCHIT ZADACHU.}]

\rex[M21] dANA BESKONECHNAYA POSLEDOVATELXNOSTX VZAIMNO NEZAVISIMYH
 SLUCHAJNYH HESH-FUNKCIJ~$h_n(K)$. pROANALIZIRUJTE METOD OTKRYTOJ ADRESACII,
V KOTOROM PROBUYUTSYA POZICII~$h_1(K)$, $h_2(K)$, $h_3(K)$,~$\ldots\,$.
zAMETXTE, CHTO VOZMOZHNO POVTORNOE OPROBOVANIE ODNOJ I TOJ ZHE POZICII,
NAPRIMER ESLI~$h_1(K)=h_2(K)$, NO |TO VESXMA MALOVEROYATNO.

\ex[vm24] oBOBSHCHIV UPR.~34 NA SLUCHAJ $b$~ZAPISEJ V BLOKE, OPREDELITE
SREDNEE CHISLO PROB (T.~E.~OBRASHCHENIJ K FAJLU) $C_N$ I~$C'_N$ PRI
ISPOLXZOVANII RAZDELXNYH CEPOCHEK, PREDPOLAGAYA, CHTO NEUDACHNYJ POISK V
SPISKE IZ $k$~|LEMENTOV TREBUET~$\min(1, k-b+1)$~PROB. vMESTO TOCHNYH
VEROYATNOSTEJ~$P_{Nk}$ IZ UPR.~34 VOSPOLXZUJTESX \dfn{PRIBLIZHENIEM pUASSONA}
$$
\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
}
$$
SPRAVEDLIVYM PRI~$N=\rho M$, $M\to\infty$.

\ex[M20] pOKAZHITE, CHTO V OBOZNACHENIYAH~(42) $Q_1(M, N)=M-(M-N-1)Q_0(M, N)$.
[\emph{uKAZANIE:} DOKAZHITE SNACHALA, CHTO $Q_1(M, N)=(N+1)Q_0(M, N)-NQ_0(M, N-1)$.]

\ex[BM16] vYRAZITE FUNKCIYU~$R(\alpha, n)$, OPREDELENNUYU V~(55), CHEREZ
FUNKCIYU~$Q_0$, OPREDELENNUYU V~(42).

\ex[vm20] dOKAZHITE, CHTO~$Q_0(M,N)=\int_0^\infty e^{-t}(1+t/M)^N\,dt.$

\ex[vm20] dOKAZHITE, CHTO FUNKCIYU~$R(\alpha, n)$ MOZHNO VYRAZITX CHEREZ
NEPOLNUYU GAMMA-FUNKCIYU, I ISPOLXZUJTE REZULXTAT UPR.~1.2.11.3-9 DLYA
NAHOZHDENIYA ASIMPTOTICHESKOGO ZNACHENIYA~$R(\alpha, n)$ S TOCHNOSTXYU
DO~$O(n^{-2})$) PRI~$n\to\infty$ I FIKSIROVANNOM~$\alpha<1$.

\ex[40] iSSLEDUJTE POVEDENIE ALGORITMA~C, ESLI EGO PRISPOSOBITX K
VNESHNEMU POISKU TAK, KAK |TO OPISANO V TEKSTE.

\ex[vm43] oBOBSHCHITE MODELX shAYA---sPRUTA, OBSUZHDAVSHUYUSYA POSLE TEOREMY~P, NA
SLUCHAJ $M$~BLOKOV RAZMERA~$b$. dOKAZHITE, CHTO~$C(z)=Q(z)/(B(z)-z^b)$, GDE
$Q(z)$---MNOGOCHLEN STEPENI~$b$ I~$Q(1)=0$. pOKAZHITE, CHTO SREDNEE CHISLO PROB
RAVNO
$$
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),
$$
GDE~$q_1$~\dots$q_{b-1}$ SUTX KORNI MNOGOCHLENA~$Q(z)/(z-1)$. zAMENIV
BINOMIALXNOE RASPREDELENIE VEROYATNOSTEJ~$B(z)$ PRIBLIZHENIEM
pUASSONA~$P(z)=e^{b\alpha(z-1)}$, GDE $\alpha=N/Mb$, I ISPOLXZOVAV
LAGRANZHEVU FORMULU OBRASHCHENIYA (SR. S FORMULOJ~(2.3.4.4-9) I UPR.~4.7-8),
PRIVEDITE OTVET K VIDU~(61).

\ex[M48] oBOBSHCHITE TEOREMU~K, POLUCHIV TOCHNYJ ANALIZ LINEJNOGO OPROBOVANIYA
PRI ISPOLXZOVANII BLOKOV RAZMERA~$b$.

%%650
\ex[m47] dAET LI PRIPISYVANIE POSLEDOVATELXNOSTYAM PROB
ODINAKOVYH VEROYATNOSTEJ MINIMALXNOE ZNACHENIE~$C_N$ SREDI VSEH METODOV
OTKRYTOJ ADRESACII?

\ex[M21] (s.~dZHONSON.) nAJDITE DESYATX PERESTANOVOK
MNOZHESTVA~$\set{0, 1, 2, 3, 4}$, |KVIVALENTNYH RAVNOMERNOMU HESHIROVANIYU V
SMYSLE TEOREMY~U.

\ex[m25] dOKAZHITE, CHTO ESLI PRIPISYVANIE VEROYATNOSTEJ
PERESTANOVKAM |KVIVALENTNO RAVNOMERNOMU HESHIROVANIYU (V SMYSLE TEOREMY~U),
TO CHISLO PERESTANOVOK S NENULEVYMI VEROYATNOSTYAMI PREVZOJDET~$M^a$ PRI
LYUBOM FIKSIROVANNOM POKAZATELE~$a$, ESLI $M$~DOSTATOCHNO VELIKO.

\ex[M48] bUDEM GOVORITX, CHTO SHEMA OTKRYTOJ ADRESACII VKLYUCHAET
\emph{EDINSTVENNOE HESHIROVANIE,} ESLI ISPOLXZUETSYA ROVNO
$M$~POSLEDOVATELXNOSTEJ PROB, NACHINAYUSHCHIHSYA SO VSEH VOZMOZHNYH
ZNACHENIJ~$h(K)$ I VSTRECHAYUSHCHIHSYA S VEROYATNOSTXYU~$1/M$.

chTO ASIMPTOTICHESKI LUCHSHE (V SMYSLE MINIMALXNOSTI~$C_N$): NAILUCHSHAYA SHEMA
S EDINSTVENNYM HESHIROVANIEM ILI SLUCHAJNYE SHEMY, ANALIZIROVAVSHIESYA V UPR.~44?

\ex[m46] yaVLYAETSYA LI METOD, ANALIZIROVAVSHIJSYA V UPR.~46,
NAIHUDSHEJ VOZMOZHNOJ SHEMOJ S EDINSTVENNYM HESHIROVANIEM? (sR.~S~UPR.~60.)

\ex[m49] nASKOLXKO HOROSHA MOZHET BYTX SHEMA S EDINSTVENNYM HESHIROVANIEM,
ESLI SHAGI~$p_1$ $p_2$~\dots $p_{M-1}$ (OBOZNACHENIYA UPR.~44) FIKSIROVANY I
NE ZAVISYAT OT~$K$? (pRIMERAMI TAKIH METODOV SLUZHAT LINEJNOE OPROBOVANIE I
POSLEDOVATELXNOSTI, RASSMATRIVAVSHIESYA V UPR.~20 I~47.)

\ex[m25] eSLI V RASSEYANNOJ TABLICE PROIZVODYATSYA SLUCHAJNYE VSTAVKI I
UDALENIYA, TO SKOLXKO NUZHNO V SREDNEM NEZAVISIMYH VSTAVOK, CHTOBY VSE
$M$~POZICIJ POBYVALI V ZANYATOM SOSTOYANII?

\ex[M46] pROANALIZIRUJTE OZHIDAEMOE POVEDENIE ALGORITMA~R. sKOLXKO RAZ V
SREDNEM BUDET VYPOLNYATXSYA SHAG~R4?

\rex[20] \exhead(kLYUCHI PEREMENNOJ DLINY.) vO MNOGIH PRILOZHENIYAH
RASSEYANNYH TABLIC KLYUCHI MOGUT SOSTOYATX IZ PROIZVOLXNOGO CHISLA LITER. v
TAKOM SLUCHAE NELXZYA PROSTO ZAPOMNITX KLYUCH V TABLICE, KAK |TO DELALOSX V
PROGRAMMAH DANNOGO PARAGRAFA. pRIDUMAJTE HOROSHIJ SPOSOB ISPOLXZOVANIYA
RASSEYANNYH TABLIC DLYA HRANENIYA KLYUCHEJ PEREMENNOJ DLINY, ESLI RABOTA
VEDETSYA NA MASHINE~\MIX.

%% 651
\bye