Dėstymo lentelė

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigaciją, paiešką

Dėstymo lentelė (hash table) – tai duomenų struktūra, kuriuoje duomenys yra saugomi, priskiriant jiems unikalų raktą. Raktus generuoja įvairios maišos (hash) funkcijos. Dėstymo lentelės naudingiausios, kai dažniausia (ar jautriausia) su duomenimis atliekama operacija yra paieška: maišos funkcija pagal duomenis identifikuojančią informaciją generuoja maišos kodą (raktą), kuris dėstymo lentelėje naudojamas įrašų rikiavimui ir aptikimui.

Lentelė realizuoja sąsają „vienas į vienas“. Jei reikia sąsajos „vienas į daug“ arba „daug į daug“, naudojama keleto lentelių sistema, susieta asociatyviniais vienetais.

Kolizijos[taisyti | redaguoti kodą]

Jei du įrašai dėstymo lentelėje turi vienodus raktus, įvyksta kolizija. Yra sugalvota įvairių būdų kolizijoms pašalinti, tačiau čia išnagrinėsime du: atviras adresavimas (open addressing) ir eiliavimas (chaining).

Atviras adresavimas[taisyti | redaguoti kodą]

Įvykus kolizijai ieškoma kitos tuščios (atviros) vietos tam elementui padėti.

Tiesinis dėstymas (linear probing
Vieta naujam elementui randama tikrinant lentelę kas pastovų skaičių elementų nuo kolizijos (dažniausiai tai 1)
Antros eilės dėstymas (quadratic probing
Ieškoma didinant periodą tiesiškai (tada eilutės numeris kinta antros eilės greičiu)
Dvigubas dėstymas (double hashing
Tikrinimo periodas apskaičiuojamas kita maišos funkcija priklausomai nuo elemento rakto.

Naudojant atviro adresavimo metodą, labai svarbus yra apkrovos faktorius. Kuo pilnesnė lentelė, tuo didesnė galimybė, kad įvyks kolizija – įdėjimo operacijos laikas didėja. Tuo pačiu ilgesnė tampa ir paieškos operacija. Dažniausiai lentelės užpildymas apribojamas iki 80 %.

Skaičiuojant efektyvumą, tariama, kad blogiausiu atveju yra užpildyta visa lentelė ir laiko atžvilgiu efektyvumas yra O (N *M), kur M lentelės dydis, o N norimų įterpti įrašu skaičius

Naudojant tiesinį dėstymą algoritmo efektyvumą mažina netolygiai po lentelę išsidėstę įrašai.

Dažniausiai dvigubam dėstymui reikia mažiau palyginimų nei tiesiniam dėstymui.

Atviro adresavimo pagrindinis privalumas yra mažesnis reikalingas atminties kiekis.

Eiliavimas[taisyti | redaguoti kodą]

Eiliavimas angl. – separate chaining arba chaining.

Kiekvienoje dėstymo lentelės „eilutėje“ yra duomenų struktūra, kurioje saugomi visi įrašai, turintys tą patį maišos kodą (dažniausiai tiesinis sąrašas). Kai į lentelę įterpiamas naujas elementas, jis įterpiamas į maišos kodo nurodytos eilutės duomenų struktūrą.

Sekiant efektyviausio panaudojimo reikia užtikrinti, kad maksimalaus įrašų skaičiaus ir lentelės eilučių skaičiaus proporcija būtų kaip įmanoma mažesnė.

Tokio metodo privalumai: rečiau arba net visai nereikalingas lentelės išplėtimas. Pildantis lentelei, efektyvumo degradavimas yra O(n). Be to, šis metodas yra lengvai realizuojamas.

Eiliavimo panaudojimo blogosios pusės kyla iš tiesinio sąrašo duomenų struktūros panaudojimo: dirbant su mažais (atminties prasme) įrašais, duomenų struktūra palyginus su duomenimis užima daug atminties. Taip pat tiesinių sąrašų apėjimas (tvarsing) yra sunkiai (nelabai efektyviai) kešuojamas.

Egzistuoja alternatyvūs eiliavimo dėstymo lentelėje organizavimo būdai. Juose eilutės realizuojamos ne tiesiniais sąrašais, o sudėtingesnėmis, bet greitesnėmis duomenų struktūromis. Pavyzdžiui, panaudojant Raudonai-Juodą medį galime pasiekti O(log n) efektyvumo degradavimą.

Realizavimas[taisyti | redaguoti kodą]

Nagrinėjama dėstymo lentelės realizacija turi du parametrus, kurie turi įtakos jos efektyvumui: lentelės dydį bei apkrovimo koeficientą. Apkrovimo koeficientas gali būti tarp 0,0 ir 1,0. Kai įrašų skaičius dėstymo lentelėje viršyja apkrovimo koeficientą tuometinei lentelės talpai, dėstymo lentelės talpa yra padidinama. Lentelė su didesniu apkrovimo koeficientu efektyviau naudoja atmintį, bet informacijos paieška gali trukti ilgiau. Jei tikėtina, kad į dėstymo lentelę bus įterpta daug įrašų, pakankamai didelės pradinės talpos lentelės sukūrimas leis įterpti įrašus daug efektyviau negu tuo atveju, kai įterpiant įrašus reikės didinti lentelę.

Abstraktaus duomenų tipo sąsaja[taisyti | redaguoti kodą]

create ([int initialCapacity, float loadFactor]) 
Sukuria naują (tuščią) dėstymo lentelę. Nebūtini parametrai: pradinė talpa bei duotas apkrovimo koeficientas.
put (key, object) 
Įdeda naują elementą į lentelę. Key – raktas, pagal kurį skaičiuojama hash reikšmė. Object – duomenų rinkinys.
get (key) 
Grąžina reikšmę, kuri atitinka raktą dėstymo lentelėje, arba Null reikšmę, jei nerasta ieškomo rakto.
remove(key) 
Pašalina raktą atitinkančią reikšmę iš dėstymo lentelės. Šis metodas nieko nedaro, jei rakto dėstymo lentelėje nėra.
search (key) 
Patikrina, ar duotas raktas yra dėstymo lentelėje.
rehash () 
Perkelia dėstymo lentelės turinį į didesnės talpos dėstymo lentelę. Šis metodas yra iškviečiamas automatiškai, kai raktų skaičius dėstymo lentelėje viršija tos lentelės apkrovimo koeficientą einamajai lentelės talpai.
clear () 
Išvalo dėstymo lentelę.