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.