Hašų lentelė – kas tai yra ir kaip veikia
Hašų lentelė yra duomenų struktūra, skirta greitam raktais pažymėtų reikšmių (angl. key-value) saugojimui ir paieškai. Kompiuterių moksle tokios saugojimo priemonės vadinamos duomenų struktūromis. Hašų lentelė naudoja specialią hašinę funkciją, kuri pagal rakto (pavyzdžiui, asmens vardo) turinį apskaičiuoja skaičių — vietos indeksą masyve. Kiekvienam raktui priskiriama reikšmė (vertė), pavyzdžiui, telefono numeris.
Kaip tai veikia
Hašų lentelė paprastai remiasi paprastu vizualiu vaizdu — turime masyvą (tarsi eilę langelių arba kibirų), kiekviename langelyje gali būti saugomi vienas arba keli įrašai. Hašinė funkcija nuskaito raktą (pvz., tekstinį vardą) ir grąžina didelį sveiką skaičių. Norint gauti galiojantį masyvo indeksą, šis skaičius dažniausiai pavertimas modulo masyvo dydžio: index = hash(key) % size. Taip žinome, į kurį langelį dėti ar iš kurio skaityti duomenis.
Susidūrimai (collisions) ir jų sprendimai
Skirtingi raktai kartais duoda tą patį indeksą — tai vadinama susidūrimu. Tai natūrali problema, todėl hašų lentelės naudoja įvairius metodus ją valdyti:
- Grandinės metodas (chaining) — kiekviename masyvo langelyje laikomas sąrašas (pvz., susietų sąrašas arba dinaminis vektorius). Visi įrašai, kurie pateko į tą patį indeksą, dedami į tą sąrašą.
- Atviras adresavimas (open addressing) — kai susiduria įrašai, ieškoma kito laisvo langelio pagal tam tikrą tvarką. Pavyzdžiai: linijinis tyrimas (linear probing), kvadratinis tyrimas (quadratic probing), dvigubas hašavimas (double hashing).
Kiekvienas metodas turi privalumų ir trūkumų: grandinės paprastai patikimesnės esant dideliam užpildymo lygiui, o atviras adresavimas gali būti efektyvesnis atminties prasme, bet jautresnis klasterizacijai.
Laiko sudėtingumas ir įkrovos faktorius
Gerai parinkta hašų lentelė vidutiniškai užtikrina O(1) laiką paieškai, įterpimui ir ištrynimui. Tačiau blogiausiu atveju (pvz., visi raktai nuteka į vieną kibirą, arba hašavimo funkcija labai prasta) operacija gali tapti O(n). Siekiant išlaikyti greitį, dažnai stebimas įkrovos faktorius (load factor) — įrašų skaičius padalytas iš masyvo dydžio. Kai įkrovos faktorius viršija tam tikrą ribą, lentelė paprastai perskirstoma (resize) — sukuriamas didesnis masyvas ir visi įrašai perhašuojami.
Hašinės funkcijos savybės
Hašinė funkcija, skirta įprastinei hašų lentelei, turėtų būti greita apskaičiuoti, tolygiai paskirstyti raktais ir deterministinė (vienodas raktas visada duoda tą patį rezultatą). Svarbu pabrėžti, kad tai skiriasi nuo kriptografinės hašinės funkcijos: kriptografinės funkcijos yra sukurtos saugumui užtikrinti, o lentelėse dažnai užtenka paprastesnių, bet efektyvių funkcijų.
Praktinės pastabos
- Hašų lentelės netinka, jei reikia išlaikyti elementus surikiuotus pagal raktą — tam geriau tinka medžiai (pvz., balansuoti paieškos medžiai).
- Rinktiniuose (sets), asociatyviniuose masyvuose (maps/dictionaries), talpyklose (caches) ir duomenų bazių indeksuose hašų lentelės labai populiarios dėl greitumo.
- Multithreading aplinkose būtina užtikrinti sinchronizaciją arba naudoti bendradarbiavimo saugius (concurrent) hašų lentelių įgyvendinimus.
- Raktų tipai nebūtinai turi būti tekstai — tai gali būti skaičiai, objekto identifikatoriai ar sudėtiniai rakto tipai (tuomet reikalinga atitinkama hašinė funkcija ir lyginimas).
Panaudojimas
Dėl greitos prieigos ir paprastos koncepcijos hašų lentelės plačiai naudojamos:
- asociatyviniams masyvams (žemėlapiams) ir duomenų bazėms;
- talpykloms (caches) ir spartiesiems žemėlapiams;
- rinkinių (sets), simbolių lentelėms kompiliatoriuose ir kt.
Apibendrinant: hašų lentelė — tai efektyvus būdas saugoti ir greitai rasti raktu pažymėtus duomenis. Tinkamai parinkus hašinę funkciją, tvarkymo metodą ir dydžio keitimo strategiją, ji užtikrina vidutinį O(1) greičio lygį daugeliui praktinių uždavinių.
Nedidelė telefonų knyga kaip hash lentelė
Klausimai ir atsakymai
K: Kas yra hash lentelė?
A: Hašinė lentelė yra duomenų struktūros, naudojamos informacijai saugoti, tipas. Joje naudojama hash funkcija, kad būtų galima sekti, kur yra įdėti duomenys, ir greitai surasti informaciją, jei žinote jos pavadinimą.
K: Kokios yra dvi hešinės lentelės saugomų duomenų dalys?
A: Hešinėje lentelėje saugomus duomenis sudaro dvi dalys - raktas, kuris yra su duomenimis susijęs pavadinimas, ir reikšmė, kuri yra faktinė saugoma duomenų dalis.
K: Kaip veikia hešinė lentelė?
A.: Hašinė lentelė veikia naudojant hašavimo funkciją, kad būtų nustatyta, kuris skaičius iš pavadinimo turėtų būti naudojamas duomenims saugoti į masyvą panašioje struktūroje, sudarytoje iš daugybės langelių arba kaušų. Tai leidžia greitai gauti informaciją, nepriklausomai nuo to, kiek duomenų į ją buvo sudėta.
K: Kokie yra kai kurie įprasti hešinių lentelių naudojimo būdai?
A: "Hash" lentelės dažniausiai naudojamos asociatyviniams masyvams, duomenų bazėms, talpykloms ir rinkiniams dėl jų gebėjimo greitai surasti informaciją, nesvarbu, kiek duomenų į jas įdėta.
K: Kodėl "Hash" lentelės yra greitesnės už kitas priemones, pavyzdžiui, paieškos medžius ar kitas paieškos struktūras?
A: "Hash" lentelės yra greitesnės už kitus įrankius, nes jos visada gali rasti informaciją tuo pačiu greičiu, nepriklausomai nuo to, kiek duomenų į jas įdėta, o kiti įrankiai gali užtrukti ilgiau, priklausomai nuo duomenų kiekio. Be to, jos leidžia naudotojams vienodai greitai pridėti ir pašalinti raktų ir verčių poras.
K: Kokioje kompiuterių programinėje įrangoje naudojamos gretinamosios lentelės?
A: Daugelyje kompiuterių programinės įrangos rūšių naudojamos "Hash Tables" dėl greito duomenų gavimo laiko ir efektyvaus saugojimo galimybių.
