Wat is Hashtabel (hash table)?
Datastructuur die met een hashfunctie uit een sleutel een opslagpositie berekent, waardoor zoeken, invoegen en verwijderen gemiddeld O(1) kosten. Botsingen, waarbij verschillende sleutels op dezelfde positie uitkomen, worden afgehandeld met chaining of open adressering.
Japanse benaming: ハッシュテーブル
“Hashtabel (hash table)” komt voor in 7 oefenvragen uit 4 onderwerpen, bijv. Datastructuren en algoritmen, Kansrekening, statistiek en wachtrijen, Geheugenhiërarchie en prestaties.
Vakgebied: Datastructuren en algoritmen
Werking en afhandeling van botsingen
Een hashtabel zet een sleutel met een hashfunctie om in een geheel getal en gebruikt bijvoorbeeld de rest bij deling door de tabelgrootte als opslagpositie. Er zijn veel meer mogelijke sleutels dan posities, dus botsingen, waarbij verschillende sleutels op dezelfde positie uitkomen, zijn onvermijdelijk. Chaining koppelt de elementen op dezelfde positie aan elkaar, bijvoorbeeld in een gelinkte lijst. Open adressering zoekt een andere vrije positie in de tabel, met methoden zoals lineair proberen, dat de naburige posities één voor één onderzoekt, of dubbele hashing, dat met een tweede hashfunctie de stapgrootte kiest.
Bezettingsgraad en rehashing
Het aantal opgeslagen elementen gedeeld door de tabelgrootte heet de bezettingsgraad (load factor). Bij chaining is de gemiddelde lijstlengte evenredig met de bezettingsgraad; bij open adressering neemt het aantal pogingen om een vrije plaats te vinden sterk toe als de bezettingsgraad 1 nadert. Overschrijdt de bezettingsgraad een gekozen grens, dan wordt de tabel daarom vergroot, meestal tot ongeveer het dubbele, en worden alle elementen opnieuw ingevoegd (rehashing). Eén rehash kost O(n), maar omdat de tussenpozen tussen vergrotingen steeds verdubbelen, blijven de kosten per invoeging geamortiseerd O(1).
Prestaties en aandachtspunten
Het gemiddelde van O(1) veronderstelt dat de hashfunctie de sleutels gelijkmatig over de tabel spreidt. Een slechte hashfunctie, of invoer die opzettelijk botsingen veroorzaakt (een hash-floodingaanval), kan de tabel in het slechtste geval vertragen tot O(n); daarom gebruiken webservers en vergelijkbare software hashfuncties die met een willekeurige seed worden gemengd. Een hashtabel houdt haar elementen bovendien niet op volgorde, dus binaire zoekbomen of B-bomen zijn beter geschikt voor bereikzoekopdrachten en geordende opsommingen. De werkelijke snelheid hangt ook af van het cachegedrag: methoden die naburige posities onderzoeken, zoals lineair proberen, zijn vaak sneller dan chaining, dat pointers volgt.
Veelgestelde vragen
Hoe hangen hashtabellen samen met hashfuncties?
Een hashfunctie berekent uit een sleutel een waarde in een vast bereik, en een hashtabel is een datastructuur die haar gebruikt om opslagposities te berekenen. Hashfuncties voor hashtabellen leggen de nadruk op snelheid en een gelijkmatige spreiding en hoeven meestal niet eenrichtings te zijn zoals cryptografische hashfuncties.
Waar worden hashtabellen gebruikt?
Overal waar waarden snel op sleutel moeten worden opgezocht, zoals dictionary's (associatieve arrays) en sets in programmeertalen, symbooltabellen in compilers, hash joins en hashindexen in databases, en cachebeheer.