Associatieve array

Een associatieve array is, in een programmeertaal, een datacontainer waarmee door middel van een sleutelobject een ander object gezocht wordt.

Een array is gewoonlijk een lijst van waarden waar je via een index in de vorm van een getal een waarde kan uit aanspreken. Bij een associatieve array hoeft de index niet per se een getal te zijn, maar het kan ook bijvoorbeeld een string zijn.

Een associatieve array gaat ook door het leven als een map of een dictionary. Het woord map wordt gebruikt omdat deze datastructuur een mapping implementeert, hetgeen een soort vertaling is. Hier komt ook de term dictionary vandaan, je stopt er een woord in en er komt een ander woord uit. Een associatieve array vertoont veel gelijkenis met een tabel uit een relationele database.

Uitleg

Stel dat in een fictieve programmeertaal de syntaxis voor het opvragen van een waarde uit een array er zo uitziet:

arraynaam[index]

Bijvoorbeeld adressen[1] geeft het adres dat op positie 1 in de array staat. Dit is niet altijd praktisch, want vaak wil je het adres hebben van iemand met bijvoorbeeld een bepaalde naam. De datastructuur 'array' is in dit geval minder geschikt omdat er dan een lus geschreven moet worden die de array doorloopt en steeds test op de naam. Dit levert onnodig veel broncode op en is bovendien niet efficiënt in termen van rekentijd.

Het is veel leesbaarder indien dit genoteerd kan worden als

arraynaam[zoeksleutel]

zodat het opvragen van het gewenste array-element eruitziet als adressen["jan"]. Dit is precies wat een associatieve array is. De zoeksleutel hoeft geen string te zijn zoals in dit voorbeeld, maar kan elk type object zijn.

Een associatieve array kan zo gemaakt worden dat deze zoekt op meerdere sleutels zoals bij een multidimensionele array. Bijvoorbeeld: adressen["jan", "smit"]. Het is echter gebruikelijker eerst een object te maken dat de volledige zoeksleutel bevat en deze als argument mee te geven. Dit komt er dan, in een fictieve programmeertaal, zo uit te zien:

arraynaam[sleutelklasse(sleutel1, sleutel2)]

Gebruik

Associatieve arrays worden gebruikt in vele programmeertalen. Enkele 'scriptachtige' talen zoals AWK of JavaScript kennen uitsluitend associatieve arrays als container. In andere talen is het een van de mogelijke datastructuren die gebruikt kan worden. In Java wordt standaard een klasse meegeleverd die deze functionaliteit biedt. In C++ wordt deze voorziening geleverd door de Standard Template Library (STL), maar ook Microsoft heeft dit in zijn MFC zitten.

Implementatie

Een associatieve array kan op verschillende manieren geïmplementeerd worden. Hoofdzaak in de implementatie is dat het opzoeken van elementen snel is (idealiter O(1)), waarvoor betaald wordt door het toevoegen of verwijderen van elementen duurder te maken en/of meer geheugen te gebruiken.

Een veel gebruikte implementatie is de hashtabel. De associatieve array wordt in Perl hash genoemd.

Een alternatief is een boomstructuur, zoals een gebalanceerde binaire boom of een Bayer-boom. Dit is het geval in de STL.