Azərbaycan
Deutschland
Lietuva
Malta
ශ්රී ලංකාව
Türkmenistan
Türkiyə
Украина
Maišos lentelė angl hash table duomenų struktūra kurioje pagal sutartą trumpą nuorodą raktą galima greitai rasti su tuo
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ų.
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
- Lecture 17 Introduction to Hashing www.cs.cmu.edu
Autorius: www.NiNa.Az
Išleidimo data:
vikipedija, wiki, lietuvos, knyga, knygos, biblioteka, straipsnis, skaityti, atsisiųsti, nemokamai atsisiųsti, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, pictu, mobilusis, porn, telefonas, android, iOS, apple, mobile telefl, samsung, iPhone, xiomi, xiaomi, redmi, pornografija, honor, oppo, Nokia, Sonya, mi, pc, web, kompiuteris, Informacija apie Dėstymo lentelė, Kas yra Dėstymo lentelė? Ką reiškia Dėstymo lentelė?
Maisos lentele angl hash table duomenu struktura kurioje pagal sutarta trumpa nuoroda rakta galima greitai rasti su tuo raktu susieta įrasa kuriame yra daugiau duomenu Nedidelei telefonu knygai skirta maisos lentele Siuo atveju visoms galimoms pavardems apskaiciuojama tik 15 skirtingu maisos kodu paieska pagal kuriuos ilgai netrunka Veliau lyginamos tik ta patį maisos koda turincios pavardes Raktas pagal kurį reikia rasti susijusia duomenu struktura gali buti zodis tekstas daug galimu reiksmiu turintis skaicius ar sudetingesne duomenu struktura pavyzdziui geografines koordinates Naiviai parasytas kodas lygintu pateikiama rakta su visu duomenu strukturoje saugomu įrasu raktais Jei struktura is tiesu didele tai uztrunka pernelyg ilgai Maisos lenteleje kiekvienam įraso raktui apskaiciuojamas pagalbinis maisos kodas angl hashcode Jis trumpas nesunkiai apskaiciuojamas bet keletui galimu raktu yra ir turi buti toks pats Ieskant pirmiausia randamas paieskos rakto maisos kodas Pagal jį greitai randami keli galimi kandidatai tarp kuriu jau ieskoma lyginant raktus kurie kiekvienam lenteles įrasui turi skirtis Maisos kodai yra nedideli skaiciai su kuriais susijusius lenteles raktu sarasus galima rasti labai greitai Jie neturi daug rysio su logisku rakto turiniu is cia angl hashing darzoviu ar mesos kapojimas mazais gabaleliais juos paskui ismaisant Pavyzdziui telefono numerio maisos kodas gali buti jo skaitmenu suma kad ir atitinkanti anaiptol ne viena numerį Svarbu kad tokiu maisos kodu daug maziau nei galimu telefonu numeriu ir tarp ju ieskoti daug greiciau Kiekvienam skirtingam maisos kodui priskiriamas kibiras angl bucket kuriame saugomi visi ta maisos koda turintys įrasai Jei galimu maisos kodo reiksmiu daugiau nei norima tureti kibiru intervala nesunku susiaurinti dalijant is norimo kibiru skaiciaus ir galutiniu maisos kodu panaudojant gaunama liekana Gerai parasytoje maisos lenteleje įrasas randamas per trumpa laika beveik nepriklausantį nuo lenteles dydzio Naiviai parasytoje lenteleje paieskos laikas proporcingas lenteleje saugomu įrasu skaiciui Tokioje lenteleje nera jokio naturalaus rusiavimo įrasu seka nepriklauso nei nuo raktu turinio kaip zodyne nei nuo to kokia tvarka tie įrasai buvo prideti Lentele taip pat blogai tinka ieskoti pagal raktus kurie atitinka tik apytikriai pavyzdziui pagal zodzius su galimomis rasybos klaidomis SaltiniaiLecture 17 Introduction to Hashing www cs cmu edu