|
[[Vaizdas:HashTable lt.svg|thumb|Nedideliai telefonų knygai skirta maišos lentelė. Šiuo atveju visoms galimoms pavardės apskaičiuojama tik 15 skirtingų maišos kodų, paieška pagal kuriuos ilgai netrunka. Vėliau lyginamas tik tą patį maišos kodą turinčios pavardės.]]
{{Šaltiniai|neturi_nuo=2005 m. gegužės|nuo=2020 m. rugpjūčio}}
'''Maišos lentelė''' ({{en|hash table}}) yra [[duomenų struktūra]] kurioje pagal sutartą trumpą nuorodą (raktą) galima greitai rasti su tuo raktu susietą įrašą, kuriame yra daugiau duomenų. <ref>Lecture 17 Introduction to Hashing [https://www.cs.cmu.edu/~guna/15-123S11/Lectures/Lecture17.pdf www.cs.cmu.edu]</ref>
{{stilius}}
'''Dėstymo lentelė''' ([[Anglų kalba|angl.]] ''hash table'') – tai [[duomenų struktūra]], kuriuoje duomenys yra saugomi, priskiriant jiems unikalų raktą. Raktus generuoja įvairios maišos ([[Anglų kalba|angl.]] ''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.
Raktas, pagal kurį reikia rasti susijusią duomenų struktūrą, gali būti žodis (tekstas), daug galimų reikšmių turintis skaičius ar sudėtingesnė duomenų struktūra (pavyzdžiui, geografinės koordinatės). Naiviai parašytas kodas lygintų pateikiamą raktą su visų duomenų struktūroje saugomų įrašų raktais. Jei struktūra iš tiesų didelė, tai užtrunka pernelyg ilgai.
Lentelė realizuoja sąsają „vienas į vienas“. Jei reikia sąsajos „vienas į daug“ arba „daug į daug“, naudojama keleto lentelių sistema, susieta [[asociatyvinis vienetas|asociatyviniais vienetais]].
Dėstymo lentelėje kiekvienam įrašo raktui apskaičiuojamas pagalbinis maišos kodas ({{en|hashcode}}). Jis trumpas, nesunkiai apskaičiuojamas bet keletui galimų raktų yra (ir turi būti) toks pats. Ieškant pirmiausia randamas paieškos rakto maišos kodas. Pagal jį greitai randami keli galimi kandidatai, tarp kurių jau ieškoma lyginant raktus, kurie kiekvienam lentelės įrašui turi skirtis.
== 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'').
Maišos kodai yra nedideli skaičiai, su kuriais susijusius lentelės raktų sąrašus galima rasti labai greitai. Jie neturi daug ryšio su logišku rakto turiniu (iš čia {{en|hashing}} — daržovių ar mėsos kapojimas mažais gabalėliais, juos paskui išmaišant. Pavyzdžiui, telefono numerio maišos kodas gali būti jos skaitmenų suma, kad ir atitinkantį anaiptol ne vieną numerį. Svarbu kad tokių maišos kodų daug mažiau nei galimų telefonų numerių, ir tarp jų ieškoti daug greičiau. Kiekvienam skirtingam maišos kodui priskiriamas „kibiras“ ({{en|bucket}}), kuriame saugomi visi tą maišos kodą turintys įrašai. Jei galimų maišos kodo reikšmių daugiau nei norima turėti kibirų, intervalą nesunku susiaurinti dalijant iš kibirų skaičiaus ir galutiniu maišos kodu panaudojant gaunamą liekaną.
=== Atviras adresavimas ===
Įvykus kolizijai ieškoma kitos tuščios (atviros) vietos tam elementui padėti.
Gerai parašytoje dėstymo lentelėje įrašas randamas per trumpą laiką, beveik nepriklausantį nuo lentelės dydžio. Naiviai parašytoje lentelėje paieškos laikas proporcingas lentelėje saugomų įrašų skaičiui.
; 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.
Tokioje lentelėje nėra jokios „natūralaus“ rūšiavimo – įrašų seka nepriklauso nei nuo raktų turinio (kaip žodyne), nei nuo to kokia tvarka tie įrašai buvo pridėti. Lentelė taip pat blogai tinka ieškoti pagal raktus, kurie atitinka tik apytikriai (pavyzdžiui pagal žodžius su galimomis rašybos klaidomis).
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 %.
== Šaltiniai ==
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
{{išn}}
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 ===
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š [[Tiesinis sąrašas|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šavimas|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-Juodas medis|Raudonai-Juodą medį]] galime pasiekti O(log n) efektyvumo degradavimą.
== Realizavimas ==
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šija 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 ===
<!-- vietoje key reikėtų kito termino, kad nebūtų painiojamas su maišos raktu. Priešingu atveju nėra galimybės nurodyti, kurį iš vienodą maišos raktą turinčių elementų reikia gauti arba išmesti. Be to, maišos raktas priklauso nuo lentelės dydžio, taigi neprotinga šio rakto skaičiavimą iškelti į abstrakčios duomenų sąsajos išorę [[User:Monas|Monas]] 08:02, 23 Bir 2005 (EEST) -->
; 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ę.
[[Kategorija:Duomenų struktūros]]
| 