|
[[Vaizdas:HashTable lt.svg|thumb|Nedidelei telefonų knygai skirta maišos lentelė. Šiuo atveju visoms galimoms pavardėspavardėms apskaičiuojama tik 15 skirtingų maišos kodų, paieška pagal kuriuos ilgai netrunka. Vėliau lyginamaslyginamos tik tą patį maišos kodą turinčios pavardės.]]
'''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>
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.
DėstymoMaišos 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.
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 josjo skaitmenų suma, kad ir atitinkantį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“ ({{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š norimo kibirų skaičiaus ir galutiniu maišos kodu panaudojant gaunamą liekaną.
Gerai parašytoje dėstymomaiš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 jokiosjokio „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 ==
| 