Wat is een associatieve array?
Een associatieve array, ook wel een hash -tabel of hash -kaart genoemd, is vergelijkbaar met een standaard array, 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 betrekking hebben op grote hoeveelheden gegevens, is een associatieve array een essentieel element bij het op een efficiënte manier om informatie te helpen sorteren en toegang te krijgen tot informatie. De kern van een associatieve array is een standaard array die wordt geïndexeerd met gehele getallen, zoals normaal gesproken het geval zou zijn. Een speciaal algoritme genaamd een hash -functie converteert de tekenreeksindex in een geheel getal index om de waarde te vinden. Dit is een consistente conversie, dus de werkelijke gehele index hoeft nooit te worden opgeslagen, maar wordt in plaats daarvan elke keer uit de tekenreeks berekend.
De terminologie die wordt gebruikt bij het verwijzen naar een associatieve array kan enigszins anders zijn dan wat wordt gebruikt bij het praten over een normale array. Wat normaal gesproken een index zou worden genoemd - de numerieke locatie van een element in een array - wordt desleutel. De gegevens die aan de sleutel zijn gekoppeld, worden de waarde genoemd. Dit betekent dat, binnen een associatieve array, een sleutel is gekoppeld aan 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 te bepalen op basis van de sleutel. Er zijn verschillende soorten hash -functies, sommige ontworpen om te werken op toetsen die gehele getallen zijn en sommige ontworpen om te werken aan sleutels die strings zijn. In het geval van een geheel getalsleutel is een populaire methode om de belangrijkste waarde te delen door de grootte van de array en de rest van de divisie te gebruiken om, hopelijk, een unieke indexwaarde te krijgen.
De hash -functie kan veel complexer zijn voor sleutels die strings zijn. Sommige methoden omvatten het toevoegen van de numerieke waarde van elk teken in de string en het vervolgens delen door een aantal getal,Of alleen de eerste paar tekens van de string gebruiken om een uniek nummer te krijgen. Er zijn veel manieren om een nummer af te leiden aan een reeks tekens.
Bij het omgaan met een grote hoeveelheid sleutelwaardeparen in een associatieve array wordt een probleem dat zich kan voordoen, botsing genoemd. Botsing gebeurt wanneer de gehele getalindex van een sleutel identiek is aan de gehele getalindex van een andere sleutel. Deze twee sleutels wijzen vervolgens effectief op dezelfde index in de waardereeks. Er zijn verschillende oplossingen voor botsing, vooral omdat het een grote kans heeft om in de meeste praktische toepassingen te gebeuren.
Eén oplossing voor botsing is om elke waarde -index een gekoppelde lijst te hebben, zodat, wanneer meer dan één sleutel oplost naar die indexlocatie, 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 lineair onderzoek genoemd.Wanneer een botsing optreedt, werkt lineaire sondering door door de waardereeks te gaan 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 vergroten die nodig is om een waarde op te zoeken.