Erinevus lehekülje "Räsifunktsioon" redaktsioonide vahel

resümee puudub
 
1990-te aastate alguseni venekeelses kirjanduses oli tänu Andrei Jeršovi töödele kasutatud termini "räsimine" ekvivalendina sõna "järjestus", ning kollisioonide jaoks kasutati terminit "konflikt". Tänapäeval on jäänud vaid sõna "räsimine".
 
== Räsifunktsioonide liigid ==
Hea räsifunktsioon peab vastama kahele tingimusele:
* Olema kiiresti arvutatav;
* Minimiseerima kollisioonide arvu.
 
Määratletuseks oletame, et võtide arv on <math>K</math>, ja räsifunktsioonil <math>h(K)</math> on mitte rohkem, kui <math>M</math> erinevaid tähendusi:
 
<math>0<h(k)<M</math>
"Halva" räsifunktsiooni näitena võib tuua funktsiooni <math>M=1000</math>, mis kümnekohalisele [[Naturaalarv|naturaalarvule]] <math>K</math> vastastab kolm numbri <math>K</math> kahekümnenda ruudu keskest valitud arvu. Tundub, et räsikoodide tähendused peaksid ühtlaselt jaotuma «000» ja «999» vahel, kuid reaalsete andmete jaoks selline meetod sobib vaid juhul, kui võtmetel pole suurt nullide arvu vasakul ja paremal.{{sfn|Дональд Кнут. Искусство программирования}}
 
Kuid on olemas mitu lihtsamaid ja kindlamaid meetodeid, millele tuginevad paljud räsifunktsioonid.
 
=== Jagamisele rajatud räsifunktsioonid ===
Esimene meetod seisneb selles, et me kasutame räsina jagamise <math>M</math>-ga jääki, kus <math>M</math> on kõikide võimalike räside arv:
 
: <math>h(K) = K \mod M </math>
 
Seejuures on ilmselge, et paaris-<math>M</math> puhul funktsiooni tähendus on ka paarisarvuline, paaris-<math>K</math> puhul, ning paaritu - paaritu puhul, mis võib viia failiandmete olulise nihutuseni. Samuti ei tasu kasutada <math>M</math>-na arvuti arvutamise aluse astet, kuna räsikood sõltub ainult <math>K</math> arvu mitmetest paremal asuvatest numbritest, mis viib suure kollisioonide arvuni. Praktikal tavaliselt valitakse hariliku (alg-) <math>M</math> - enamikul juhtudest selline valik on täitsa rahuldav.
 
Veel tasuks mainida räsimise meetodit, mis on rajatud mooduliga kaks jagamisele polünoomile. Antud meetodi puhul <math>M</math> peab samuti olema kahe aste, ning binaarvõtid (<math>K=k_{n-1}k_{n-2}...k_{0}</math>) on kujutatud polünoomidena. Sel juhul räsikoodina võetakse tegurite tähendusi polünoomist, mis on saadud nagu jääk <math>K</math> jagamisest eelnevalt valitud polünoomiga <math>P</math> astmes <math>m</math>:
 
: <math>K(x) \mod P(x) = h_{m-1}x^{m-1}+h_{1}x+h_{0} </math>
: <math> h(x)=h_{m-1}...h_{1}h_{0}</math>
 
Õigesti valitud <math>P(x)</math> puhul selline viis tagab kollisioonide peaaegu sarnaste võtmete vahel puudumise.{{snf|Дональд Кнут. Искусство программирования}}
 
=== Räsimise multiplikaatne skeem ===
Teine meetod seisneb mingi terve konstandi <math>A</math>, mis on vastastikult harilik <math>w</math>-ga, valimises, kus <math>w</math> on masinsõna abil esindatavate tähenduste arv (IBM PC arvutites see on <math>2^{32}</math>). Siis võib võtta järgmist räsifunktsiooni:
 
: <math>h(k) = \left[ M \left\lfloor \frac{A}{w}*K \right\rfloor \right]</math>
 
Sel juhul, kahendsüsteemiga arvutil <math>M</math> on kahe aste ning <math>h(K)</math> koosneb korrutise <math>A*K</math> parempoolsetest vanematest bittidest.
 
Nende kahe meetodite eeliste hulgas tasub mainida, et nad kasulikul viisil kasutavad seda, et reaalsed võtmed pole juhuslikud, näiteks juhul, kui võtmed kujutavad endast aritmeetilist progressiooni (näiteks nimede «NIMI1», «NIMI2», «NIMI3» järjestust). Multiplikaatne meetod näitab aritmeetilist progressiooni kui erinevate räsitähenduste lähtestatud aritmeetilist progressiooni, mis vähendab kollisioonide arvu võrreldes juhusliku olukorraga.
 
Selle meetodi üks variatsioonidest on Fibonacci arvu räsimine, mis põhineb kuldlõige omadustel. <math>A</math> arvuna võetakse lähedasemat <math>\varphi^{-1}*w</math> arvule algarvu, mis on vastastikult harilik <math>w</math>-ga.
 
 
==Vaata ka==
101

muudatust