Dėstymo lentelė

Maišos lentelė (angl. hash table) – duomenų struktūra, kurioje pagal sutartą trumpą nuorodą (raktą) galima greitai rasti su tuo raktu susietą įrašą, kuriame yra daugiau duomenų.

Nedidelei telefonų knygai skirta maišos lentelė. Šiuo atveju visoms galimoms pavardėms apskaičiuojama tik 15 skirtingų maišos kodų, paieška pagal kuriuos ilgai netrunka. Vėliau lyginamos tik tą patį maišos kodą turinčios pavardės.

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.

Maišos lentelėje kiekvienam įrašo raktui apskaičiuojamas pagalbinis maišos kodas (angl. 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.

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 angl. 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 jo skaitmenų suma, kad ir atitinkanti 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“ (angl. 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š norimo kibirų skaičiaus ir galutiniu maišos kodu panaudojant gaunamą liekaną.

Gerai parašytoje maišos 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.

Tokioje lentelėje nėra jokio „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).

Šaltiniai

1. Lecture 17 Introduction to Hashing www.cs.cmu.edu