Räsitabel (hash-tabel) — definitsioon, toimimine ja rakendused

Räsitabel on üks teabe salvestamise vahend. Arvutiteaduses nimetatakse neid teabe ehk andmete jälgimise vahendeid andmestruktuurideks. Räsitabel on andmestruktuur, mis kasutab andmete asukoha jälgimiseks räsifunktsiooni. Igal salvestataval informatsioonil on nimi, mida nimetatakse võtmeks. Näiteks võib võtmeks olla inimese nimi. Igale nimele vastab üks andmestik, mida nimetatakse väärtuseks, näiteks isiku telefoninumber.

Andmeid hoitakse teises andmestruktuuris, mida nimetatakse massiiviks, mis on nagu mitu kasti ehk ämbrit, mis hoiavad andmeid reas. Igal kastil on number, mis algab 0-st ja loeb ülespoole.

Hash-tabeli mõte on välja selgitada, millisesse kasti andmed paigutada, kasutades ainult selle nime. See tähendab, et olenemata sellest, kui palju lahtreid on täidetud, saate alati kiiresti leida teabe, kui teil on selle nimi. Hash-tabel kasutab hash-funktsiooni, et arvata selle nime põhjal välja, millisesse numbrisse andmed panna. Hash-funktsioon loeb nime ja annab tagasi numbri.

Hea Hash-tabel leiab teabe alati sama kiiresti, olenemata sellest, kui palju andmeid sinna sisestatakse. Paljud Hash-tabelid võimaldavad kasutajal ka sisestada võtme/väärtuse paarid (nimi ja selle andmed) ja võtta need sama kiirusega välja.

Kuidas räsitabel täpselt töötab

Räsitabeli põhietapid on:

Räsifunktsiooni rakendamine: võtmele (näiteks tekstile) rakendatakse räsifunktsioon, mis annab tagasi arvu (räsiväärtuse).
Indeksi leidmine: räsiväärtust muudetakse sobivaks indeksiks massiivi pikkuse põhjal (tavaliselt indeks = hash(key) mod capacity).
Andmete paigaldamine või otsimine: indeksi juures salvestatakse või loetakse võtmele vastav väärtus.

Räsifunktsioon peaks olema kiire, deterministlik (iga sama võtme puhul annab sama tulemuse) ja võimalikult hästi võtmeid ühtlaselt jaotama, et vähendada kokkupõrkeid.

Kokkupõrked ja nende lahendused

Kuna erinevad võtmed võivad anda sama indeksi (räsiväärtuse jagamisel massiivi suurusega), tekivad kokkupõrked. Levinumad strateegiad nende käsitlemiseks:

Eraldamine ahelana (separate chaining): iga massiivi lahter hoiab viidet (nt lingitud nimekirja või dünaamilise massiivi) kõigile võtme/väärtuse paaridele, mis antud indeksiga kokku satuvad. Otsimine tähendab reaalselt läbivaatamist selle väikse loendi sees.
Avatud leidmine (open addressing): kui sihtindeks on hõivatud, otsitakse järgmine vaba koht vastavalt mingile reeglile (nt lineaarne probing, kvadratiivne probing, double hashing). Kustutamine ja otsing nõuavad tavaliselt tombstone-märgendite kasutamist.

Iga strateegia toob kaasa erinevaid jõudlus- ja mäluomadusi: ahelad vajavad lisamälu linkide/struktuuride jaoks, avatud leidmine võib saavutada kompaktsema mälukasutuse, kuid raske deleetimise korral tekivad keerukused.

Tõhusus ja keerukus

Keskmine aeg (otsing/sisestus/kustutus): tavaliselt O(1) (amortisatsiooni silmas pidades), kui räsifunktsioon jagab võtmed ühtlaselt ja laadur (load factor) hoitakse madalana.
Halvim juhtum: O(n) — võib juhtuda, kui palju võtmeid satuvad samasse ahelasse või räsifunktsioon teeb halva jaotuse (või ründaja tekitab spetsiifilisi võtmeid).
Laadimisfaktor (load factor): saadetakse kui elementide arv jagatud massiivi mahutavusega. Kõrge laadimisfaktor suurendab kokkupõrkeid ja vähendab jõudlust, mistõttu paljud teostused teevad automaatse suurendamise (rehashing), kui laadimisfaktor läheb üle teatud piiri.
Ruumiline keerukus: tavaliselt O(n) elementide hoidmiseks ehk massiivi ja täiendavate struktuuride jaoks.

Disaini valikud ja parimad tavad

Vali räsifunktsioon vastavalt võtmete tüübile: tekstistringide puhul kasutatakse tihti mitmesuguseid kombineeritud bitikäärimise ja kordistamise meetodeid; krüptograafilised räsifunktsioonid annavad hea jaotuse, kuid on aeglasemad — tavaliselt pole neid vaja tavaliste andmestruktuuride jaoks.
Hoidke laadimisfaktor mõistlikul tasemel (tavaliselt 0.5–0.75) ja rehashige (suurendage massiivi pikkust ja arvutage indeksid uuesti), kui elementide arv kasvab oluliselt.
Kui vajate järjestatud läbimist või deterministlikku halvimatel juhtudel head töötlemist, sobib pigem tasakaalustatud otsingupuu (nt red-black tree) kui räsitabel.
Arvestage kulu-kasuga: räsitabelid on kiired otsinguks, kuid võtmejärjestuse hoidmiseks või väikese mäluga süsteemides võib olla mõistlik teisi struktuure kaaluda.
Avatud leidimisel arvestage kustutamise keerukusega (tombstone) ja võimalik vajadus perioodiliseks ümberpaigutamiseks, et tihendada struktuuri.

Rakendused ja näited

Räsitabeleid kasutatakse laialdaselt, sest nad võimaldavad kiiret ligipääsu võtme-põhiselt. Levinud kasutusalad:

Assotsiatiivsed massiivid ja sõnastikud (dictionary, map).
Andmebaasid ja vahemälud (cache) — kiire otsingu ja duplikaadi kontrolli jaoks.
Unikaalsuse kontroll (nt kogumite implementatsioonid), loendurid ja sagedusanalüüs teksti töötlemisel.
Indekseerimine ja mitmesugused andmestruktuuri põhiselt optimeeritud algoritmid (nt lühim tee, graafitöötlus, kui vaja kiiret tipu otsingut vms).

Praktiline näide: telefoniraamat, kus võtmed on inimeste nimed ja väärtused telefoninumbrid — räsitabel leiab kiirelt, millises positsioonis antud nimega kirje asub, ilma et peaks kogu nimekirja läbi otsima.

Lisamärkused

Räsitabeli reaalne jõudlus sõltub suuresti räsifunktsiooni kvaliteedist ja andmete omadustest.
Räsitabel ei säilita võtmete loomulikku järjekorda — kui järjestus on oluline, tuleb selle jaoks kasutada teisi strukture või lisavälju.
Turvalisuse aspekt: avalikud räsitabelid, mis aktsepteerivad kasutaja-sisestatud võtmeid, võivad olla vastuvõtlikud räsirünnakutele (collision DOS), seetõttu kasutatakse mõnikord võtmete randomiseerimist või turvalisemaid räsimeetodeid.

Kokkuvõttes on räsitabel (hash-tabel) võimas ja sageli parim valik kiirete võtme-põhiste otsingute jaoks. Selle kasutamine nõuab teadlikkust räsifunktsiooni valikust, kokkupõrgete käitlemisest ja laadimisfaktorist, et hoida jõudlus kõrge ja käitumine ennustatav.

Väike telefoniraamat kui hash-tabel

Küsimused ja vastused

K: Mis on hash-tabel?

V: Räsitabel on teatud tüüpi andmestruktuur, mida kasutatakse teabe salvestamiseks. See kasutab hash-funktsiooni, et jälgida, kuhu andmed on paigutatud, ja saab kiiresti leida teavet, kui teil on selle nimi.

K: Millised on kaks hash-tabelis salvestatud andmete osa?

V: Räsitabelis salvestatud andmed koosnevad kahest osast - võtmest, mis on andmetega seotud nimi, ja väärtusest, mis on tegelik salvestatav andmestik.

K: Kuidas hash-tabel töötab?

V: Räsitabel töötab, kasutades räsifunktsiooni, et välja selgitada, millist numbrit selle nimest tuleks kasutada andmete salvestamiseks paljudest kastidest või ämbritest koosnevas massiivisarnases struktuuris. See võimaldab teabe kiiret leidmist sõltumata sellest, kui palju andmeid sinna on pandud.

K: Millised on mõned levinumad kasutusalad, mida kasutatakse hash-tabelite puhul?

V: Hash Tables'i kasutatakse tavaliselt assotsiatiivsete massiivide, andmebaaside, vahemälude ja kogumite puhul, kuna need võimaldavad kiiresti leida teavet, olenemata sellest, kui palju andmeid sinna on pandud.

K: Miks on Hash-tabelid kiiremad kui teised vahendid, näiteks otsingupuud või muud otsingustruktuurid?

V: Hash-tabelid on teistest vahenditest kiiremad, sest nad leiavad teavet alati sama kiiresti, olenemata sellest, kui palju andmeid on neisse pandud, samas kui muud vahendid võivad võtta kauem aega sõltuvalt sellest, kui palju andmeid on. Lisaks võimaldavad nad kasutajatel lisada ja eemaldada võtme/väärtuse paare samuti võrdse kiirusega.

K: Millised arvutitarkvarad kasutavad Hash-tabeleid?

V: Paljud liiki arvutitarkvarad kasutavad kihttabelid nende kiire väljavõtteaja ja tõhusate salvestusvõimaluste tõttu.