Wat is een hashtable?

In informatica is een hashtable een gegevensstructuur voor het opslaan van gegevens die bestaat uit een lijst met waarden, toetsen genoemd, die gepaard gaan met een overeenkomstige lijst met waarden, een array genoemd.Een bedrijfsnaam kan bijvoorbeeld worden gekoppeld aan het adres.Meestal heeft elke waarde in de array een positienummer dat een hash wordt genoemd.De hash -functie is over het algemeen een set instructies of een algoritme dat elke sleutelwaarde toewijst aan een hash mdash;De bedrijfsnaam verbinden met zijn adres, zijn telefoonnummer en zijn bedrijfscategorie bijvoorbeeld.Het doel van de hash -functie is om elke sleutel toe te wijzen aan een unieke overeenkomstige waarde in de array;Dit wordt gewoonlijk hashing genoemd.Hash -functies moeten correct zijn opgemaakt voor een hashtable om correct te functioneren.

De prestaties van een hashtable op een reeks gegevens zijn afhankelijk van de efficiëntie van de hash -functie.Een goede hash -functie voorziet meestal in een uniform opzoektoetsen en een gelijkmatige verdeling van toewijzingen in de overeenkomstige array.Een hash -botsing treedt op wanneer twee sleutels worden toegewezen aan dezelfde overeenkomstige waarde.Wanneer een hash -botsing optreedt, wordt de hash -functie meestal opnieuw uitgevoerd totdat een unieke overeenkomstige waarde wordt gevonden;Dit resulteert meestal in langere hashing -tijden.Hoewel het aantal sleutels in een hashtable meestal is opgelost, kunnen er soms dubbele toetsen zijn.Toch heeft een goed ontworpen hashtable effectieve hash-functies die elke sleutel in kaart brengen aan een unieke overeenkomstige waarde in de array.

Soms kunnen inefficiënte hash -functies in een hashtable ook een cluster van toewijzingen produceren.Als een hash -functie een cluster van toewijzingen voor bestaande toetsen maakt, kan dit de hoeveelheid tijd vergroten die nodig is om de overeenkomstige waarden op te zoeken.Dit kan de hashing voor toekomstige toetsen vertragen, omdat de meeste hash -functies over het algemeen zoeken naar de volgende beschikbare positie in de array.Als een groot cluster van waarden al is toegewezen, zou het meestal veel langer duren om een niet -toegewezen waarde voor een nieuwe sleutel te zoeken.

De laadfactor is een ander concept gerelateerd aan de efficiëntie van een hash -functie;De laadfactor is de hoeveelheid reeds bestaande hashings in relatie tot de totale grootte van de overeenkomstige array in een hashtable.Het wordt meestal gedefinieerd door het aantal reeds toegewezen sleutels te delen door de grootte van de overeenkomstige array.Naarmate de laadfactor toeneemt, zal een goede hash -functie normaal gesproken nog steeds een constant aantal botsingen en clusters tot een bepaald punt behouden.Vaak kan deze drempel worden gebruikt om te bepalen hoe efficiënt een hash -functie is met een bepaald aantal sleutels en wanneer een nieuwe hash -functie nodig kan zijn.

Veel onderzoekers van informatica hebben ernaar gestreefd om de perfecte hash -functie mdash te produceren;Een die geen botsingen of clusters produceert, die een toenemende belastingsfactor heeft gegeven.In theorie is de sleutel tot het produceren van een perfecte hashtable een perfecte hash -functie produceren.Over het algemeen geloven onderzoekers dat een perfecte hash -functie constante prestaties moet hebben mdash;Het aantal botsingen en clusters mdash;met een toenemende belastingsfactor.In het ergste geval zou een perfecte hash -functie nog steeds constante hashing mogelijk maken zonder een drempel te bereiken.