Wat is een associatieve array?

Een associatieve array, ook wel een hashtabel of hashmap genoemd, is vergelijkbaar met een standaardarray, behalve dat de index van de array een string kan zijn in plaats van een geheel getal. In veel databasetoepassingen en in andere programma's die met grote hoeveelheden gegevens omgaan, is een associatieve array een essentieel element om informatie op een efficiënte manier te sorteren en te openen. De kern van een associatieve array is een standaardarray die wordt geïndexeerd met gehele getallen, zoals normaal het geval zou zijn. Een speciaal algoritme dat een hash-functie wordt genoemd, converteert de tekenreeksindex naar een geheel getal om de waarde te vinden. Dit is een consistente conversie, dus de werkelijke gehele getalindex hoeft nooit te worden opgeslagen, maar wordt in plaats daarvan elke keer berekend op basis van de tekenreeks.

De gebruikte terminologie bij het verwijzen naar een associatieve array kan enigszins verschillen van wat wordt gebruikt bij het praten over een normale array. Wat normaal een index wordt genoemd - de numerieke locatie van een element in een array - wordt de sleutel genoemd. De gegevens die aan de sleutel zijn gekoppeld, worden de waarde genoemd. Dit betekent dat binnen een associatieve array een sleutel wordt geassocieerd met een waarde, die correleert met een index die verwijst naar een element in een standaardarray in de gegevensstructuur.

De kern van elke associatieve array is de hash-functie. Dit is een algoritme dat wordt gebruikt om de numerieke index van een waarde op basis van de sleutel te bepalen. Er zijn verschillende soorten hash-functies, sommige ontworpen om te werken op toetsen die gehele getallen zijn en sommige ontworpen om te werken op toetsen die tekenreeksen zijn. In het geval van een integersleutel is een populaire methode om de sleutelwaarde te delen door de grootte van de array en de rest van de deling te gebruiken om, hopelijk, een unieke indexwaarde te krijgen.

De hash-functie kan veel complexer zijn voor toetsen die tekenreeksen zijn. Sommige methoden omvatten het toevoegen van de numerieke waarde van elk teken in de tekenreeks en deze vervolgens delen door een cijfer, of alleen de eerste paar tekens van de tekenreeks gebruiken om een ​​uniek nummer te krijgen. Er zijn veel manieren om een ​​getal af te leiden uit een reeks tekens.

Bij het omgaan met een groot aantal sleutel / waarde-paren in een associatieve array, is een probleem dat kan ontstaan ​​botsing. Botsing vindt plaats wanneer de integer-index afgeleid van een sleutel identiek is aan de integer-index van een andere sleutel. Deze twee sleutels wijzen dan effectief naar dezelfde index in de waardematrix. Er zijn verschillende oplossingen voor botsingen, vooral omdat het in de meeste praktische toepassingen zeer waarschijnlijk is.

Een oplossing voor botsing is om elke waarde-index daadwerkelijk een gekoppelde lijst te laten zijn, zodat, wanneer meer dan één sleutel naar die indexlocatie oplost, de locatie meer dan één waarde kan bevatten. Dit wordt chaining genoemd en is een eenvoudige manier om een ​​botsing af te handelen, hoewel het ook de tijd kan vertragen die nodig is om de informatie op te halen. Een andere methode om met een botsing om te gaan, wordt lineaire sondering genoemd. Wanneer een botsing optreedt, werkt lineair sonderen door de waardematrix te bewegen totdat een ongebruikte index wordt gevonden. Deze oplossing kan helpen om de gegevens gelijkmatig verdeeld te houden in de associatieve array, maar het kan ook de hoeveelheid tijd verhogen die nodig is om een ​​waarde op te zoeken.