Wat is het principe van werking van een hash-tabel?

Een hashtabel (of associatief array) slaat paren "sleutel-waarde" op. Het werkingsprincipe is gebaseerd op het gebruik van een hashfunctie, die de sleutel omzet in een numerieke index (hash), die de opslagplaats van de waarde in de array (mand) aangeeft.

Stappen:

1. Hashberekening: Voor een gegeven sleutel wordt de hash berekend.

   <?php
   $key = "example";
   $hash = crc32($key); // Voorbeeld van een eenvoudige hashfunctie
   

2. Bepaling van de index: De hash wordt omgezet in een array-index, meestal door de modulo-operatie van de grootte van de array.

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

3. Toegang tot de mand: Toegang tot de bijbehorende mand in de array met behulp van de berekende index.
4. Oplossen van botsingen: Aangezien verschillende sleutels dezelfde hash kunnen hebben (botsing), kan de mand meerdere "sleutel-waarde" paren bevatten. Voor het oplossen van botsingen worden verschillende methoden gebruikt:
   • Chaining (koppeling): Elke mand slaat een lijst (bijvoorbeeld een gekoppelde lijst) op van "sleutel-waarde" paren waarvan de hashes overeenkomen.
   • Open adressering: Bij botsing wordt herhaaldelijk gezocht naar een vrije cel in de array volgens een bepaalde regel (lineair, kwadratisch, dubbele hashing).

Operaties:

• Invoegen: De hash van de sleutel wordt berekend, de index wordt bepaald, en het "sleutel-waarde" paar wordt in de bijbehorende mand geplaatst. Bij botsing wordt het toegevoegd aan de lijst (koppeling) of wordt een vrije plek gezocht (open adressering).
• Zoeken: De hash van de sleutel wordt berekend, de index wordt bepaald. In de bijbehorende mand wordt de waarde gezocht op basis van de sleutel. Bij chaining worden de lijstitems doorlopen; bij open adressering wordt een sequentiële zoekactie uitgevoerd.
• Verwijderen: De hash van de sleutel wordt berekend, de index wordt bepaald. In de bijbehorende mand wordt het paar gevonden en verwijderd op basis van de sleutel.

Voordelen:

• Snelle toegang tot elementen (gemiddeld O(1)).
• Efficiënt gebruik van geheugen.

Nadelen:

• De prestaties kunnen verslechteren bij veel botsingen.
• De grootte van de tabel kan aanpassing vereisen (rehashing) om de efficiëntie te behouden.