Wat is een hash-tabel?

Een hash-tabel is een gegevensstructuur die een associatieve array (woordenboek) implementeert. Het slaat paren "sleutel-waarde" op, waarbij de sleutels uniek zijn.

Basisprincipes:

• Hashfunctie: Zet de sleutel om in een getal (hash-code of index). Deze index wijst naar de opslagplaats van de waarde in de array (mandje).
• Array (manden): Werkelijke opslag van de "sleutel-waarde" paren.
• Botsingen: Situatie waarin verschillende sleutels dezelfde hash-code genereren.

Oplossing voor botsingen:

• Kettingmethode (Separate chaining): In elk mandje bevindt zich een lijst (of een andere datastructuur) van elementen met dezelfde hash-code.
• Open adressering (Open addressing): Bij een botsing wordt gezocht naar een vrij mandje met behulp van verschillende strategieën (lineair sondage, kwadratisch sondage, dubbele hashing).

Kenmerken:

• Snelle toegang: In het ideale geval O(1) voor invoeg-, zoek- en verwijderbewerkingen.
• Afhankelijkheid van de hashfunctie: De kwaliteit van de hashfunctie en de strategie voor het oplossen van botsingen beïnvloeden de prestaties sterk.
• Geheugengebruik: Vereist extra geheugen voor de array van manden.

Gebruik in QA:

• Opslag van testgegevens (sleutel - parameternaam, waarde - verwachte of feitelijke waarde).
• Controle op de uniciteit van elementen (bijvoorbeeld gebruikers-ID's).
• Implementatie van caches.