hashstructuren

Hashstructuren is een verzameling gegevensstructuren die een sleutel koppelen aan een waarde via een hashfunctie. Het doel is snelle toegang tot elementen, meestal in O(1) verwachte tijd voor zoeken, invoeren en verwijderen. Hashstructuren worden breed toegepast als symbolentabellen, caches en sets.

Een hashstructuur bestaat doorgaans uit een array van zakken (buckets) waarin items worden geplaatst op basis van de uitkomst van een hashfunctie. Omdat meerdere sleutels dezelfde bucket kunnen opleveren (collisions), zijn er verschillende collision resolution strategieën.

De twee hoofdbenaderingen zijn aparte chaining en open addressing. Bij aparte chaining worden in elke bucket een lijst of boom opgeslagen van alle items die naar die bucket verwijzen. Bij open addressing wordt bij een conflict een alternatieve bucket gezocht volgens een vast algoritme, bijvoorbeeld lineair, kwadratisch of met dubbele hashing.

Prestaties hangen af van de kwaliteit van de hashfunctie en van de load factor, oftewel het verhouding aantal opgeslagen elementen tot het aantal buckets. In de meeste toepassingen blijft de gemiddelde tijd per bewerking constant (O(1)) bij voldoende ruimte, terwijl de slechtste gevallen lineaire tijd kunnen bedragen. Om de prestaties te bewaren, worden hashstructuren periodiek gerehashed of uitgebreid.

Veelgebruikte voorbeelden zijn hashmaps en hashsets in programmeertalen zoals Java, Python en C++. Naast standaard tabellen bestaan er varianten zoals dynamische hashtabellen, extendible hashing en cuckoo hashing, die verschillende strategieën voor resizing of collision handling gebruiken.

Hashstructuren bieden snelle en flexibele opslag van sleutel-waardeparen, maar vereisen aandacht voor geheugenverbruik, caching en, bij multi-threaded toepassingen, synchronisatie. Ze vormen een fundamenteel bouwblok in informatietechnologie en softwareontwikkeling.