Kāda ir hash tabulas darbības principi?

Hesētaba (vai saistītais masīvs) glabā "atslēga-vērtība" pārus. Tā darbības princips ir balstīts uz hašfunkcijas izmantošanu, kas pārveido atslēgu skaitliskā indeksā (hašā), kas norāda uz vērtības glabāšanas vietu masīvā (groziņā).

Soļi:

1. Hašfunkcijas aprēķināšana: Dotajai atslēgai tiek aprēķināts hašs:

   <?php
   $key = "example";
   $hash = crc32($key); // Vienkāršas hašfunkcijas piemērs
   

2. Indeksa noteikšana: Hašs tiek pārveidots par masīva indeksu, parasti izmantojot moduļa operāciju ar masīva lielumu:

   <?php
   $arraySize = 10;
   $index = $hash % $arraySize;
   

3. Piekļuve groziņam: Aprēķinātais indekss ļauj piekļūt attiecīgajam masīva groziņam:
4. Kolīziju risināšana: Tā kā dažādi atslēgas var būt ar vienādu hašu (kolīzija), groziņš var saturēt vairākus "atslēga-vērtība" pārus. Kolīziju risināšanas dažādi veidi:
   • Atsevišķu ķēžu metode (Separate Chaining): Katram groziņam ir saistīts saraksts (piemēram, saistīts saraksts) ar "atslēga-vērtība" pāriem, kuru haši ir vienādi.
   • Atvērtās adresācijas metode (Open Addressing): Ja notiek kolīzija, meklē brīvu vietu masīvā pēc noteikta noteikuma (līnija, kvadrātiska, dubultā hašēšana).

Operācijas:

• Ievietošana: Aprēķina atslēgas hašu, nosaka indeksu, un "atslēga-vērtība" pāris tiek ievietots attiecīgajā groziņā. Ja ir kolīzija, tas tiek pievienots sarakstam (ķēdē) vai meklēta brīva vieta (atvērtā adrese).
• Meklēšana: Aprēķina atslēgas hašu, nosaka indeksu. Attiecīgajā groziņā meklē vērtību pēc atslēgas. Atsevišķu ķēžu gadījumā pārbauda saraksta elementus; atvērtās adresešanas gadījumā veic secīgu meklēšanu.
• Dzēšana: Aprēķina atslēgas hašu, nosaka indeksu. Attiecīgajā groziņā atrod un dzēš pāri pēc atslēgas.

Priekšrocības:

• Ātra piekļuve elementiem (vidēji O(1)).
• Efektīva atmiņas izmantošana.

Trūkumi:

• Kolīziju daudzums var pasliktināt veiktspēju.
• Tabulas izmērs var prasīt regulēšanu (rehashing), lai saglabātu efektivitāti.