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 - het verbinden van de bedrijfsnaam 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 set gegevens zijn afhankelijk van de efficiëntie van de hash -functie. Een goede hash -functie typischAlly voorziet in een uniforme lookup van sleutels 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 clustervan waarden is al toegewezen, het zou meestal veel langer duren om te zoeken naar een niet -toegewezen waarde voor een nieuwe sleutel.
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 de informatica hebben ernaar gestreefd de perfecte hash -functie te produceren - een functie die geen botsingen of clusters produceert, gegeven een toenemende belastingsfactor. In theorie is de sleutel tot het produceren van een perfecte hashtable pro voorDuce een perfecte hash -functie. Over het algemeen geloven onderzoekers dat een perfecte hash -functie constante prestaties zou moeten hebben - het aantal botsingen en clusters - met een toenemende belastingsfactor. In het slechtste geval zou een perfecte hash -functie nog steeds constant hashing mogelijk maken zonder een drempel te bereiken.