Mis on hash-tabeli tööpõhimõte?

Häš-tabel (või assotsiatiivne massiiv) salvestab "võti-väärtus" paare. Selle tööpõhimõte põhineb häšifunktsiooni kasutamisel, mis muudab võtme arvuliseks indeksiks (häšiks), mis näitab väärtuse salvestamise kohta massiivis (korpuses).

Sammud:

1. Häši arvutamine: Antud võtme jaoks arvutatakse häš:

   <?php
   $key = "example";
   $hash = crc32($key); // Näide lihtsast häšifunktsioonist
   

2. Indeksi määramine: Häš muudetakse massiivi indeksiks, tavaliselt kasutades modulaatori operatsiooni massiivi suurusega:

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

3. Juurdepääs korpusele: Arvutatud indeks võimaldab pääseda vastavale massiivi korpusele:
4. Kolizioonide lahendamine: Kuna erinevad võtmed võivad omada sama häši (kolleksioon), võib korpuses olla mitu "võti-väärtus" paari. Kolisioonide lahendamiseks kasutatakse erinevaid meetodeid:
   • Kettide meetod (Separate Chaining): Igas korpuses hoitakse nimekiri (nt seotud nimekiri) "võti-väärtus" paare, mille häšid on samad.
   • Avaadressmeetod (Open Addressing): Kui toimub kolisioon, otsitakse vaba koht massiivis kindla reegli järgi (jooneline, kvadratiivne, topelthäšimine).

Operatsioonid:

• Lisamine: Arvutatakse võtme häš, määratakse indeks ja "võti-väärtus" paar asetatakse vastavasse korpusesse. Kui toimub kolisioon, lisatakse see nimekirja (ketti) või otsitakse vaba koht (avatud aadress).
• Otsing: Arvutatakse võtme häš, määratakse indeks. Vastavas korpuses otsitakse väärtust võtme järgi. Kettide meetodis läbitakse nimekiri; avatud aadressi meetodis tehakse järjestikune otsing.
• Kustutamine: Arvutatakse võtme häš, määratakse indeks. Vastavas korpuses leitakse ja kustutatakse paar võtme järgi.

Eelised:

• Kiire juurdepääs elementidele (keskmiselt O(1)).
• Efektiivne mälu kasutus.

Miinused:

• Kolisioonide arv võib halvendada jõudlust.
• Tabeli suurus võib nõuda reguleerimist (rehashing), et säilitada efektiivsus.