Dėstymo lentelės

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.

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 keletos lentelių sistema, susieta asociatyviniais vienetais.

Turinys

[taisyti] Kolizijos

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).

[taisyti] Atviras adresavimas

Į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 konstantinį skaičų 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 atvėju yra užpildyta visa lentelė ir laiko atžvilgiu efektyvumas O (N *M), kur M lentelės dydis, o N norimu į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.

[taisyti] Eiliavimas

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žtinkrinti, kad maksimalaus įrašų skaičiaus ir lentelės eilučių skaičiaus proporcija būtų kaip įmanoma mažesnė.

Tokio metodo privalumai yra tai, jog 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š tiesinis 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šu apėjimas (tvarsing) yra sunkiai (ne labai efektyviai) kešuojamas.

Egzistuoja alternatyvus 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ą..

[taisyti] Realizavimas

Nagrinėjama dėstymo lentelės realizacija turi du parametrus, kurie įtakoja jos efektyvumą: 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 atveju, kai įterpiant įrašus reikės didinti lentelę.

[taisyti] Abstraktaus duomenų tipo sąsaja

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) 
Gražina reikšmę, kuri atitinka raktą dėstymo lentelėje, arba Null reikšmę, jei nerasta ieškomo rakto.
remove(key) 
Išmeta raktą atitinkančią reikšmę iš dėstymo lentelės. Šis metodas nieko nedaro, jie rakto nėra dėstymo lentelėje.
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ę.