Een hash table is een datastructuur die elke waarde onder een unieke sleutel opslaat, zodat je die waarde bijna meteen terugvindt. Het werkt door de sleutel door een wiskundige functie te halen die een locatie oplevert, en de waarde daar neer te zetten. Vraag je later om dezelfde sleutel, dan wijst diezelfde functie regelrecht terug naar de juiste plek.
Denk aan de garderobe van een theater. Je geeft je jas af en krijgt een genummerd bonnetje. Om de jas terug te krijgen, loopt de medewerker direct naar vak 47 in plaats van elke hanger af te zoeken. Een hash table doet hetzelfde met data: de sleutel is je bonnetje en de wiskunde geeft het vak, en daarom blijven zoekopdrachten snel, zelfs met miljoenen regels. Vergelijk dat met een array item voor item doorlopen, wat trager wordt naarmate hij groeit, een verschil dat Big O-notatie precies beschrijft.
Veel talen leveren hun eigen versie onder een andere naam, zoals de HashMap in Java. Het drijft dictionaries, caches en de indexen die databases snel maken.
De ene kanttekening die je moet kennen, zijn botsingen. Soms leveren twee verschillende sleutels hetzelfde vak op, alsof twee jassen aan hanger 47 worden toegewezen, en de structuur moet dat netjes opvangen door allebei te bewaren en ze bij het opzoeken uit elkaar te halen. Een goed gebouwde hash table houdt botsingen zeldzaam, maar raakt hij zo vol dat de meeste vakken botsen, dan verdwijnt het snelheidsvoordeel en gaan zoekopdrachten kruipen. Daarom telt zowel de keuze van de hashfunctie als de tabel niet te vol laten lopen in de praktijk.
Bij TopDevs leunen we op hash tables zodra het systeem van een klant directe lookups op ID of e-mail nodig heeft, want ze houden de responstijd vlak terwijl de data groeit.
