Waaruit bestaat een hash-tabel?

Een hash-tabel bestaat uit een vaste grootte array (emmer of slot) en een hashfunctie.

• Array (Emmers/Slots): Vertegenwoordigt een reeks cellen waarin "sleutel-waarde" paren worden opgeslagen. De grootte van de array bepaalt het aantal mogelijke plaatsen voor het opslaan van elementen.

• Hashfunctie: Zet de sleutel om in een gehele waarde (hash-code), die wordt gebruikt om de index van de cel in de array (emmer) te bepalen, waar de bijbehorende waarde wordt opgeslagen of opgehaald.

Daarnaast kan er zijn:

• Strategie voor het oplossen van botsingen: Mechanisme om situaties te behandelen waarin verschillende sleutels dezelfde hash-code genereren en naar dezelfde cel in de array wijzen. Veelgebruikte strategieën:
  • Separate chaining (Gescheiden ketting): Elke cel in de array slaat een pointer op naar een gekoppelde lijst (of een andere datastructuur), die alle "sleutel-waarde" paren bevat waarvan de hash-codes naar die cel wijzen.
  • Open addressing (Open adressering): Bij botsingen wordt gezocht naar een vrije cel in de array volgens een bepaalde regel (bijvoorbeeld lineair of kwadratisch zoeken).