Jaucējtabula (heštabula) — definīcija, darbības princips un pielietojums
Jaucējtabula (heštabula) ir viena no efektīvākajām datu struktūrām informācijas glabāšanai un ātrai piekļuvei. Datorzinātnē to bieži izmanto, lai sasaistītu katrai informācijas vienībai unikālu nosaukumu — atslēgu — ar tai atbilstošo vērtību. Piemēram, atslēga var būt personas vārds, bet vērtību, kas tam piesaistīta, var būt tālruņa numurs. Heštabula ļauj pēc atslēgas ļoti ātri noteikt, kur glabājas atbilstošā vērtība.
Darbības princips
Heštabulas pamatā ir masīvs, kas darbojas kā daudzu "lodziņu" (buckets) kopa. Katram lodziņam ir numurs, parasti sākot no 0 un skaitot uz augšu. Lai uzzinātu, kurā lodziņā saglabāt vai no kura nolasīt datus, tiek izmantota heša funkcija, kas ievadā atslēgu (piem., vārdu) un izvada indeksa numuru.
Labai heštabulai heša funkcijai jābūt deterministiskai (vienam un tam pašam ievadam jāatbilst vienam un tam pašam izvadam), ātrai un jāsadala atslēgas pēc iespējas vienmērīgāk pa pieejamajiem lodziņiem. Heša funkcija var atgriezt skaitli, kuru pēc tam normē (piem., atlikums dalījumā ar masīva izmēru), lai iegūtu derīgu indeksu.
Sadursmes (collisions) un to risinājumi
Tā kā heša funkcija attēlo no lielas atslēgu telpas uz ierobežotu lodziņu skaitu, dažkārt vairākas atslēgas var tikt attēlotas uz vienu un to paša indeksa — rodas sadursme. Biežāk lietotās stratēģijas sadursmju risināšanai:
- Ķēdīšana (chaining) — katrā lodziņā tur vai nu saistītu elementu saraksts vai cita dinamiska struktūra; visi elementi ar vienu indeksu tiek glabāti šajā sarakstā.
- Atvērtā adresēšana (open addressing) —, ja vieta ir aizņemta, tiek meklēta nākamā brīva vieta pēc kāda noteikta shēmas (lineārā meklēšana, kvadrātiskā meklēšana, double hashing u.c.).
- Rehashing — izmantojot otru heša funkciju vai pārrēķinot indeksus, lai samazinātu sadursmju ietekmi (bieži izmanto, mainot masīva izmēru, kad slodzes faktors pārsniedz robežu).
Veiktspēja un slodzes faktors
Vidēji heštabulas nodrošina O(1) laiku meklēšanai, ievietošanai un dzēšanai, ja sadursmju skaits ir zems un heša funkcija labi izlīdzina atslēgas. Tomēr sliktākajā gadījumā (piem., visām atslēgām tiek dots viens indekss vai slikta heša funkcija) darbības laiks var degradēt līdz O(n).
Slodzes faktors (load factor, alfa) tiek definēts kā attiecība starp saglabāto elementu skaitu un masīva lielumu. Lai saglabātu veiktspēju, daudzas implementācijas palielina masīvu (rehash) kad slodzes faktors pārsniedz noteiktu slieksni (piem., 0.7).
Hešfunkciju veidi un prasības
Atkarībā no pielietojuma var izmantot dažādas hešfunkcijas:
- Vienkāršas, ātras nekriptogrāfiskas hešfunkcijas — piemērotas datu strukturām, kur prioritāte ir ātrums (piem., MurmurHash, xxHash).
- Kryptogrāfiskas hešfunkcijas — nodrošina spēcīgāku sadursmju izturību pret ļaunprātīgu manipulāciju, taču ir lēnākas (piem., SHA ģimene); izmantojamas, ja nepieciešama drošība.
Hešfunkcijai jābūt deterministiskai, ātrai un ar labu izlīdzināšanu. Jāņem vērā arī atslēgu tipa īpašības (kā tiek kodēts vārds, lielie/mazie burtu jautājumi, Unicode utt.).
Pielietojums
Heštabulas izmantošanas piemēri:
- Asociatīvie masīvi un vārdnīcas programmēšanas valodās (key-value map).
- Datu bāzes indeksēšana un kešatmiņas mehānismi.
- Kešatmiņas (cache) realizācija, lai ātri atrastu saglabātos datus.
- Kopu (set) implementācijas elementu pārbaudei un duplikātu noņemšanai.
- Simbolu tabulas kompilatoros, URL īsināšanas servisi, datu deduplikācija un citi ātras piekļuves lietojumi.
Ierobežojumi un darbības īpašības
- Heštabulas nesaglabā elementu secību — tās nav piemērotas, ja nepieciešami sakārtoti vaicājumi vai diapazona pieprasījumi.
- Atkarībā no izvēlētās sadursmju stratēģijas un slodzes faktora var mainīties atmiņas patēriņš un veiktspēja.
- Ja atslēgas var mainīties pēc ievietošanas (mutablās struktūras), tās jāizskata uzmanīgi, jo tas ietekmē heša rezultātu.
Praktisks piemērs (vienkāršs)
Iedomājieties telefonu grāmatu, kur atslēga ir vārds un vērtība, — tālruņa numurs. Hešfunkcija ņem vārdu "Anna" un pārveido to par skaitli, ko pēc tam konvertē uz indeksa numuru, piemēram, 42. Tad telefona numurs tiek saglabāts masīva pozīcijā 42. Ja vēl kāds vārds arī dod indeksu 42, tad tiek izmantota ķēdīšana vai cita sadursmju risināšana, lai abus ierakstus saglabātu un vēlāk atrastu.
Kopsavilkumā, jaucējtabula (heštabula) ir spēcīgs un bieži lietots rīks ātrai atslēgas–vērtības sasaistīšanai. Pareiza hešfunkcijas izvēle, sadursmju pārvaldība un atbilstoša slodzes faktora kontrole nodrošina lielisku veiktspēju plašam praktisku uzdevumu lokam.
Neliela tālruņu grāmata kā hash tabula
Jautājumi un atbildes
J: Kas ir hash tabula?
A: Hešgrāfa tabula ir datu struktūras veids, ko izmanto informācijas glabāšanai. Tā izmanto hash funkciju, lai sekotu līdzi tam, kur dati ir ievietoti, un var ātri atrast informāciju, ja ir zināms tās nosaukums.
J: Kādas ir divas datu daļas, kas tiek glabātas heša tabulā?
A: Heš tabulā glabātie dati sastāv no divām daļām - atslēgas, kas ir ar datiem saistītais nosaukums, un vērtības, kas ir faktiskais saglabājamais datu gabals.
J: Kā darbojas hash tabula?
A.: Heša tabula darbojas, izmantojot heša funkciju, lai noskaidrotu, kurš skaitlis no tās nosaukuma ir jāizmanto datu glabāšanai masīvam līdzīgā struktūrā, kas sastāv no daudziem laukiem vai kausiem. Tas ļauj ātri iegūt informāciju neatkarīgi no tā, cik daudz datu tajā ir ievietots.
J: Kādi ir daži izplatītākie heša tabulu lietojumi?
A: Hash tabulas parasti izmanto asociatīvajiem masīviem, datu bāzēm, kešatmiņām un kopām, jo tās ļauj ātri atrast informāciju neatkarīgi no tā, cik daudz datu tajās ir ievietots.
J: Kāpēc Hash tabulas ir ātrākas nekā citi rīki, piemēram, meklēšanas koki vai citas meklēšanas struktūras?
A: Hash tabulas ir ātrākas par citiem rīkiem, jo tās vienmēr spēj atrast informāciju ar tādu pašu ātrumu neatkarīgi no tajās ievietoto datu apjoma, savukārt citiem rīkiem tas var aizņemt vairāk laika atkarībā no datu apjoma. Turklāt tie ļauj lietotājiem pievienot un noņemt atslēgu/vērtību pārus ar vienādu ātrumu.
J: Kāda veida datoru programmatūrā izmanto Hash tabulas?
A: Daudzas datoru programmatūras izmanto Hash tabulas, jo tās nodrošina ātru atgūšanas laiku un efektīvu glabāšanas iespēju.
