Koks yra hash lentelės veikimo principas?

Žemės-atsitiktinė lentelė (arba asocijuotas masyvas) saugo "raktas-reikšmė" poras. Jos veikimo principas pagrįstas žemės-atsitiktinės funkcijos naudojimu, kuri paverčia raktą skaitmeniniu indeksu (žemės-atsitiktiniu), nurodančiu saugojimo vietą masyve (krepšelyje).

Žingsniai:

Žemės-atsitiktinės funkcijos apskaičiavimas: duotam raktui apskaičiuojamas žemės-atsitiktinis:

<?php
$key = "example";
$hash = crc32($key); // Paprastos žemės-atsitiktinės funkcijos pavyzdys

Indekso nustatymas: Žemės-atsitiktinis paverčiamas masyvo indeksu, dažniausiai naudojant modulių operaciją su masyvo dydžiu:
```
<?php
$arraySize = 10;
$index = $hash % $arraySize;
```
Prieiga prie krepšelio: Apskaičiuotas indeksas leidžia pasiekti atitinkamą masyvo krepšelį:
Kolizijų sprendimas: Kadangi skirtingi raktai gali turėti tą patį žemės-atsitiktinį (kolizija), krepšelis gali turėti kelis "raktas-reikšmė" poras. Kolizijų sprendimo būdai:
- Atskirų grandinių metodas (Separate Chaining): Kiekviename krepšelyje saugoma sąrašas (pvz., susietas sąrašas) "raktas-reikšmė" porų, kurių žemės-atsitiktiniai sutampa.
- Atvirosios adresacijos metodas (Open Addressing): Jei įvyksta kolizija, ieškoma laisvos vietos masyve pagal tam tikrą taisyklę (linijinis, kvadratinis, dvigubas žemės-atsitiktinis).

Operacijos:

Įterpimas: Apskaičiuojamas raktas žemės-atsitiktinis, nustatomas indeksas, ir "raktas-reikšmė" pora įdedama į atitinkamą krepšelį. Jei įvyksta kolizija, ji pridedama prie sąrašo (grandinės) arba ieškoma laisva vieta (atvira adresacija).
Paieška: Apskaičiuojamas raktas žemės-atsitiktinis, nustatomas indeksas. Atitinkamame krepšelyje ieškoma reikšmė pagal raktą. Atkelių grandinių atveju pereinama per sąrašo elementus; atviro adresavimo atveju atliekama sekli paieška.
Šalinimas: Apskaičiuojamas raktas žemės-atsitiktinis, nustatomas indeksas. Atitinkamame krepšelyje randama ir ištrinama pora pagal raktą.

Privalumai:

Greita prieiga prie elementų (vidutiniškai O(1)).
Efektyvus atminties naudojimas.

Trūkumai:

Kolizijų daugėjimas gali bloginti našumą.
Lentelės dydis gali reikėti koreguoti (perdirbti - rehashing), siekiant išlaikyti efektyvumą.