Paisktabeli visualiseerija

Sisesta võtmed ja jälgi, kuidas need lahtritele määratakse. Vaata, mis juhtub kollisioonide korral.

Näidisarvutus — Paisktabeli visualiseerija

Täituvustegur alfa	0.75
Praegune käitumine	5 kollisioon(i)
Lisasondeerimised	15
Keskmine sondeerimiste arv	3.5
Kollisiooni tõenäosus	85%

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

„Kõik põrkuvad“ eelseadel ei ole katki räsifunktsioon, vaid vale tabeli suurus 🖖

Selle võtmed on 0, 8, 16, 24, 32 ja 40 ning tabelis on 8 pesa. Kõik need võtmed on kaheksa kordsed, nii et key mod 8 saadab kõik kuus pesasse 0 ja tabel taandub üheks ainsaks loendiks. Räsifunktsioonis ei ole midagi valesti: see teeb täpselt seda, mida lubab. Viga on selles, et tabeli suurusel on võtmete mustriga ühine tegur. Just selles seisneb kogu algarvuliste tabelisuuruste argument — suurus 8 on kaitsetu võtmete vastu, mis astuvad kaheksa haaval, samas kui algarv ei paku tegurit, millele langeda. Vaheta sondeerimise eelseadetele ja vaata, kuidas sama põrget kahel eri moel käsitletakse.

Hüppa otse õigesse pessa 🖖

Räsitabel on massiiv koos reegliga, mida nimetatakse räsifunktsiooniks. See teisendab iga võtme pesa numbriks. Selle asemel et kirjeid ükshaaval läbi vaadata, arvutatakse kohe, millisesse pessa element kuulub. Seetõttu püsib otsing kiire ka miljonite võtmete korral. Kiirus sõltub sellest, kui ühtlaselt võtmed jaotuvad. Lisa mõned võtmed ja vaata, kui kiiresti kaks neist samasse pessa satuvad.

Kui kollisioonist saab relv 🖖

Kuna räsitabel muutub aeglaseks lineaarseks otsinguks, kui liiga palju võtmeid satub samasse pessa — täpselt see halvim juht, mille saad üleval esile kutsuda —, võib ründaja, kes teab su räsifunktsiooni, luua tuhandeid võtmeid, mis meelega kokku põrkavad. 2011. aastal halvas see 'hash-flooding' võte veebiservereid keeltes PHP, Java, Python ja Ruby ühe pahatahtliku päringuga. Lahenduseks olid juhusliku seemnega räsifunktsioonid nagu SipHash, mis on tänaseks paljudes keeltes standard.

RÄSITABELID — KUHU VÕTI SATUB JA MIS JUHTUB, KUI KAKS SATUVAD KOKKU

Millist kokkupõrke juhtumit sa käsitled?

Räsitabel on O(1) ainult seni, kuni võtmed jaotuvad laiali. Kõik otsustab kaks küsimust: kas räsifunktsioon hajutab su võtmeid, ja kui kaks siiski põrkuvad, kas riputad teise sama pesa külge või lähed uut pesa otsima? Täituvustegur α = n/m ütleb, kui sageli põrkeid tuleb; strateegia ütleb, mis iga põrge maksab.

Kokkupõrkeid pole — juhtum, mida O(1) lubadus eeldab h(k) = k mod m, α = n/m

Kõik võtmed ühes pesas — ahelmeetod muutub loendiks O(n)

Lineaarne sondeerimine — avatud adresseerimine ja esmane kobardumine (h + i) mod m

Ruutsondeerimine — kobaraid pole, aga lisamine võib ebaõnnestuda (h + i²) mod m

Kokkupõrkeid pole — juhtum, mida O(1) lubadus eeldab

Mida sa tead: Iga võti satub eri pessa. Täituvustegur α = n/m on alla 1 ja räsi jaotab võtmed ühtlaselt üle tabeli.

Sondeerimisreegel: h(k) = k mod m, α = n/m

Näidisarvutus: võtmed 0–5 tabelisse m = 8 valemiga h(k) = k mod 8 → pesad 0–5, igaühele üks sondeerimine: α = 0,75 ja keskmine täpselt 1,00 sondeerimist

Ava see juhtum: Kollisioone pole

Kokkupõrkeid pole — juhtum, mida O(1) lubadus eeldab. Kuus võtit, kuus eri pesa, igaühele üks sondeerimine — jälgida tulebki ainult täituvust. Iga võti satub eri pessa. Täituvustegur α = n/m on alla 1 ja räsi jaotab võtmed ühtlaselt üle tabeli. — Kuus võtit, kuus eri pesa, igaühele üks sondeerimine — jälgida tulebki ainult täituvust.

Kõik võtmed ühes pesas — ahelmeetod muutub loendiks

Mida sa tead: Kõik võtmed on tabeli suuruse kordsed, nii et k mod m annab kõigile sama pesa. Ahelmeetod salvestab nad ikka, aga ühte ainsasse ahelasse.

Sondeerimisreegel: O(n)

Näidisarvutus: võtmed 0, 8, 16, 24, 32, 40 tabelisse m = 8 → kõik satuvad pessa 0; nende lisamine maksab 1+2+3+4+5+6 = 21 sondeerimist, keskmiselt 3,50

Ava see juhtum: Kõik kollideeruvad

Kõik võtmed ühes pesas — ahelmeetod muutub loendiks. Kõik kuus võtit pesas 0: räsitabelist on saanud ahelloend. Kõik võtmed on tabeli suuruse kordsed, nii et k mod m annab kõigile sama pesa. Ahelmeetod salvestab nad ikka, aga ühte ainsasse ahelasse. — Kõik kuus võtit pesas 0: räsitabelist on saanud ahelloend.

Lineaarne sondeerimine — avatud adresseerimine ja esmane kobardumine

Mida sa tead: Ahelaid pole: kokkupõrke korral liigutakse ühe pesa kaupa edasi, kuni leidub vaba. Iga kirje elab tabelis endas.

Sondeerimisreegel: (h + i) mod m

Näidisarvutus: võtmed 3, 11, 19, 6, 14, 22 tabelisse m = 8 → pesad 3, 4, 5, 6, 7, 0 sondeerimistega 1, 2, 3, 1, 2, 3: keskmine 2,00 ja kuus kirjet moodustavad ühe katkematu ploki

Ava see juhtum: Lineaarne sondeerimine

Lineaarne sondeerimine — avatud adresseerimine ja esmane kobardumine. Hõivatud pesad sulavad üheks plokiks; ploki sisse räsitud võti peab kõndima selle lõppu. Ahelaid pole: kokkupõrke korral liigutakse ühe pesa kaupa edasi, kuni leidub vaba. Iga kirje elab tabelis endas. — Hõivatud pesad sulavad üheks plokiks; ploki sisse räsitud võti peab kõndima selle lõppu.

Ruutsondeerimine — kobaraid pole, aga lisamine võib ebaõnnestuda

Mida sa tead: Kokkupõrke korral hüpatakse i² pesa kaupa, mitte i kaupa. See lõhub kobarad, kuid sondeerimisjada ei külasta enam iga pesa.

Sondeerimisreegel: (h + i²) mod m

Näidisarvutus: samad võtmed tabelisse m = 8 → 3, 4, 7, 6, 2 — ja siis 22 kukub täiesti läbi: kui m on kahe aste, võtab i² mod 8 ainult väärtused 0, 1 ja 4, nii et kolm pesa ongi kõik, kuhu jõuab

Ava see juhtum: Ruutsondeerimine

Ruutsondeerimine — kobaraid pole, aga lisamine võib ebaõnnestuda. Sondeerimisjada hüppab ja kordub: pesad jäävad tühjaks ja viimasel võtmel pole kuhugi minna. Kokkupõrke korral hüpatakse i² pesa kaupa, mitte i kaupa. See lõhub kobarad, kuid sondeerimisjada ei külasta enam iga pesa. — Sondeerimisjada hüppab ja kordub: pesad jäävad tühjaks ja viimasel võtmel pole kuhugi minna.

Ülesanded täielikult lahendatud

75% täituvusega tabel keskmiselt 3,5 kontrolliga otsingu kohta 5 sammu
Tabel on 75% täis ja vajab otsingu kohta keskmiselt 3,5 proovimist. Lineaarse proovimise standardvalem ennustab selle täiteastme juures tulemuseks 2,5. Selgita välja, kumb neist kahest eksib.
1. Kumbki ei eksi ja põhjus peitub võtmetes. Räsi igaüks neist kuuest tabeli enda funktsiooniga ja igaüks neist tagastab väärtuse 3 — need moodustavad aritmeetilise jada vahega 8 ning tabelis on täpselt 8 pesa.
  
  $h (k) = k mod 8 : 3, 11, 19, 27, 35, 43 ⟼ 3, 3, 3, 3, 3, 3$
2. Täitetegur on ikka aus 0,75: kuus võtit kaheksas pesas. See lihtsalt ei ütle midagi selle kohta, kuhu need läksid.
  
  $α = \frac{n}{m} = \frac{6}{8} = 0.75$
3. Nõnda on proovimisjada halvim võimalik. Esimene võti maandub vabale kohale; teine liigub ühe pesa võrra; kolmas kaks. Kuus võtit nõuavad 1 + 2 + … + 6 = 21 proovimist, millest 15 on paneeli teatatud lisatöö.
  
  $probes = 1, 2, 3, 4, 5, 6 ⟹ \sum = 21, extra = 21 - 6 = 15$
4. See teeb otsingu kohta keskmiselt 3,5 proovimist.
  
  $\overset{p}{ˉ} = \frac{21}{6} = 3.5$
5. Õpikujärgne hinnang eeldab, et võtmed hajuvad ühtlaselt, ning kui α = 0,75, annab see tulemuseks 2,5. Vahe 2,5 ja 3,5 vahel ei ole viga — see on hind räsifunktsiooni eest, mis jagab tabeli suurusega ühist tegurit, rakendatuna võtmetele, mis jagavad seda samuti.
  
  $\frac{1}{2} (1 + \frac{1}{1 - α}) = \frac{1}{2} (1 + 4) = 2.5 (random keys) < 3.5$
Vastus

Tööriist kuvab α = 0,75, lisatööks 15 proovimist ja keskmiseks 3,5. Õppetund on selles, et täitetegur on küll see tuntud arv, kuid vale asi, mida üksinda jälgida: see on siin identne tabeliga, kus on kuus hästi hajutatud võtit, mis nõuaks 2,5 proovimist. Muutus võtmekogumi ja mooduli vastastikmõju. Seetõttu valitaksegi tabeli suuruseks algarvud ning seetõttu muudab struktuuri räsimine väljaga, mis juhtumisi on mahutavuse kordne, O(1) keerukuse O(n) keerukuseks, kusjuures iga näitaja näib ikka korras olevat. Muuda suurust 8-lt 7-le ja vaata, kuidas keskmine kokku kukub.

$\overset{p}{ˉ} = 3.5 observed vs 2.5 predicted : α is not the whole story$
Päris räsikaardi suuruse muutmine täitumusteguril 0,75 6 sammu
Paneel paneb 6 võtit 8 pesasse, täituvus 0,75, ja teatab 3,5 sondeerimisest. Edukas otsing maksab sellise täituvuse juures umbes 2,5 — mugav. Miks siis iga päris räsitabel suurendab end just 0,75 juures, selle asemel et täis saada?
1. Alusta sealt, kus paneel on. Kolmveerand täis, mis kõlab mõistliku mälukasutusena.
  
  $α = \frac{n}{m} = \frac{6}{8} = 0.75$
2. Edukas otsing on rahustav arv: keskmiselt vaatad läbi umbes kaks ja pool pesa, enne kui otsitav võti välja tuleb.
  
  $S (α) \approx \frac{1}{2} (1 + \frac{1}{1 - α}) = \frac{1}{2} (1 + 4) = 2.5$
3. Ebaõnnestunud otsing järgib teist valemit, ja kogu vastus peitub selles erinevuses. Möödalask peab tõestamiseks jooksma hõivatud pesade rea lõpuni — seepärast läheb vahe liige ruutu, mitte lineaarselt.
  
  $U (α) \approx \frac{1}{2} (1 + \frac{1}{( 1 - α ) ^{2}}) = \frac{1}{2} (1 + 16) = 8.5$
4. Tõsta täituvust veidi ja loe, mida ruut teeb. 0,75 pealt 0,90 peale kõlab tagasihoidliku muutusena.
  
  $U (0.90) = \frac{1}{2} (1 + 100) = 50.5, U (0.95) = \frac{1}{2} (1 + 400) = 200.5$
5. Võrdle sama sammu peal kahte kasvukiirust. Tabamuse hind veidi enam kui kahekordistub; möödalasu hind kuuekordistub.
  
  $α : 0.75 \to 0.90 ⟹ S : 2.5 \to 5.5 (\times 2.2), U : 8.5 \to 50.5 (\times 5.9)$
6. Niisiis tabel hoopis kahekordistub. Iga võti räsitakse uuesti, mis maksab m operatsiooni, aga ostab m lisalisamist enne, kui see uuesti juhtub.
  
  $m \to 2 m ⟹ α \to \frac{α}{2}, \frac{m}{m} = O (1)$
Vastus

Möödalask maksab 0,75 juures 8,5 sondeerimist, 0,90 juures 50,5 ja 0,95 juures 200,5. Just seepärast on 0,75 ühes standardteegis teise järel suurendamise lävi — vähem kompromiss mälu ja kiiruse vahel kui viimane punkt enne järsakut. Ja määrav on möödalask, sest möödalasuga algab iga lisamine ja möödalasust koosneb tervenisti iga tulemuseta otsing. Rahustav 2,5 kirjeldab juhtumit, mille pärast sa niikuinii ei muretsenud.

$U (α) = \frac{1}{2} (1 + \frac{1}{( 1 - α ) ^{2}}) : 2.5 (0.50), 8.5 (0.75), 50.5 (0.90), 200.5 (0.95)$

Õpitee

Kui kaks asja jõuavad sama väärtuseni

Allikad (1)

Hashing, collision resolution and why table size matters, at length: Donald E. Knuth, The Art of Computer Programming, Volume 3: Sorting and Searching, 2nd edition, §6.4. Addison-Wesley, 1998. ISBN 978-0-201-89685-5.

42Mathi meeskond · Uuendatud 2026-07-27

Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud. Toimetamispõhimõtted · Parandused

Kõik Arvutustehnika õppetunnid →

Näiteülesanded

Kollisioone pole - Võtmed 0 kuni 5 tabelis suurusega 8: kuus eri pesa, iga võtme jaoks üks kontroll ja mitte ühtegi kollisiooni. Täitetegur on juba 0,75.
Kõik kollideeruvad - Iga võti jagub arvuga 8, seega räsitakse kõik kuus pessa 0 ning ahelas on kuus elementi. Keskmiselt tuleb kontrollida 3,5 pesa. Sellest arvust algab ka lahendusnäide.
Lineaarne sondeerimine - Võtmed 3, 11 ja 19 tahavad kõik pessa 3; võtmed 6, 14 ja 22 pessa 6. Lineaarse sondeerimisega paigutuvad kõik kuus, kontrollides vastavalt 1, 2, 3, 1, 2 ja 3 pesa. Keskmine on 2.
Ruutsondeerimine - Samad kuus võtit, kuid ruutsondeerimisega jääb viimane paigutamata. Ruutude jäägid mooduli 8 järgi on ainult 0, 1 ja 4, seega jõuab jada pesast 6 üksnes pesadesse 6, 7 ja 2. Pesad 0, 1 ja 5 jäävad samal ajal tühjaks.