Wat is hashtabel?
Een hashtabel wordt gedefinieerd als een gegevensstructuur die wordt gebruikt om sleutel-waardeparen snel in te voegen, op te zoeken en te verwijderen. Het werkt op de hash-concept , waarbij elke sleutel door een hashfunctie wordt vertaald naar een afzonderlijke index in een array. De index fungeert als opslaglocatie voor de overeenkomende waarde. In eenvoudige woorden: het wijst de sleutels met de waarde toe.
Wat is de belastingsfactor?
De bezettingsgraad van een hashtabel wordt bepaald door het aantal elementen dat daarin wordt bewaard in verhouding tot hoe groot de tafel is. De tabel kan rommelig zijn en langere zoektijden en botsingen hebben als de bezettingsgraad hoog is. Een ideale bezettingsgraad kan worden gehandhaafd met behulp van een goede hashfunctie en de juiste tabelgrootte.
Wat is een hashfunctie?
Een functie die sleutels vertaalt naar array-indices staat bekend als een hash-functie. De sleutels moeten gelijkmatig over de array worden verdeeld via een fatsoenlijke hash-functie om botsingen te verminderen en snelle opzoeksnelheden te garanderen.
- Aanname van het gehele universum: Er wordt aangenomen dat de sleutels gehele getallen zijn binnen een bepaald bereik, volgens de aanname van het geheeltallige universum. Dit maakt het gebruik van elementaire hash-bewerkingen mogelijk, zoals hashing van delen of vermenigvuldigen.
- Hashing per deling: Deze eenvoudige hashtechniek gebruikt de resterende waarde van de sleutel nadat deze als index is gedeeld door de grootte van de array. Wanneer een arraygrootte een priemgetal is en de sleutels gelijkmatig verdeeld zijn, presteert deze goed.
- Hashing door vermenigvuldiging: Deze eenvoudige hash-bewerking vermenigvuldigt de sleutel met een constante tussen 0 en 1 voordat het fractionele deel van de uitkomst wordt genomen. Daarna wordt de index bepaald door de fractionele component te vermenigvuldigen met de grootte van de array. Het functioneert ook effectief als de toetsen gelijkmatig verspreid zijn.
Een hashfunctie kiezen :
Het selecteren van een goede hashfunctie is gebaseerd op de eigenschappen van de sleutels en de beoogde functionaliteit van de hashtabel. Het is cruciaal om een functie te gebruiken die de toetsen gelijkmatig verdeelt en botsingen vermindert.
Criteria op basis waarvan een hashfunctie wordt gekozen:
- Om ervoor te zorgen dat het aantal botsingen tot een minimum wordt beperkt, moet een goede hashfunctie de sleutels op een uniforme manier door de hashtabel verdelen. Dit houdt in dat voor alle sleutelparen de kans dat twee sleutels naar dezelfde positie in de tabel hashen redelijk constant moet zijn.
- Om snelle hashing en het ophalen van sleutels mogelijk te maken, moet de hash-functie rekenkundig efficiënt zijn.
- Het zou een uitdaging moeten zijn om de sleutel af te leiden uit de hashwaarde. Als gevolg hiervan is de kans kleiner dat pogingen om de sleutel te raden met behulp van de hashwaarde slagen.
- Een hashfunctie moet flexibel genoeg zijn om zich aan te passen als de gegevens die worden gehasht, veranderen. De hashfunctie moet bijvoorbeeld goed blijven functioneren als de sleutels die worden gehasht van grootte of formaat veranderen.
Technieken voor het oplossen van botsingen :
Botsingen treden op wanneer twee of meer sleutels naar dezelfde array-index verwijzen. Chaining, open adressering en dubbele hashing zijn enkele technieken voor het oplossen van botsingen.
- Open adressering : botsingen worden afgehandeld door te zoeken naar de volgende lege ruimte in de tabel. Als het eerste slot al bezet is, wordt de hashfunctie toegepast op de volgende slots totdat er één leeg blijft. Er zijn verschillende manieren om deze aanpak te gebruiken, waaronder dubbele hashing, lineaire sondering en kwadratische sondering.
- Aparte keten : Bij afzonderlijke koppelingen is er een gekoppelde lijst met objecten aanwezig die naar elk slot in de hashtabel hashen. Er worden twee sleutels opgenomen in de gekoppelde lijst als ze naar hetzelfde slot hashen. Deze methode is vrij eenvoudig te gebruiken en kan meerdere botsingen beheren.
- Robin Hood hasht: Om de lengte van de keten te verkleinen, worden botsingen bij Robin Hood-hashing aangepakt door sleutels uit te schakelen. Het algoritme vergelijkt de afstand tussen het slot en het bezette slot van de twee sleutels als een nieuwe sleutel hasht naar een reeds bezet slot. De bestaande sleutel wordt vervangen door de nieuwe als deze dichter bij het ideale slot komt. Dit brengt de bestaande sleutel dichter bij zijn ideale slot. Deze methode heeft de neiging om het aantal botsingen en de gemiddelde kettinglengte te verminderen.
Dynamisch formaat wijzigen:
Met deze functie kan de hashtabel uitzetten of inkrimpen als reactie op veranderingen in het aantal elementen in de tabel. Dit bevordert een ideale laadfactor en snelle opzoektijden.
Implementaties van hashtabel
Python, Java, C++ en Ruby zijn slechts enkele van de programmeertalen die hashtabellen ondersteunen. Ze kunnen worden gebruikt als een aangepaste datastructuur en worden vaak opgenomen in de standaardbibliotheek.
Voorbeeld – Tel tekens in de String geeksforgeeks.
In dit voorbeeld gebruiken we een hashtechniek voor het opslaan van het aantal strings.
C++ #include using namespace std; int main() { //initialize a string string s='geeksforgeeks'; // Using an array to store the count of each alphabet // by mapping the character to an index value int arr[26]={0}; //Storing the count for(int i=0;i Java public class CharacterCount { public static void main(String[] args) { // Initialize a string String s = 'geeksforgeeks'; // Using an array to store the count of each alphabet // by mapping the character to an index value int[] arr = new int[26]; // Storing the count for (int i = 0; i < s.length(); i++) { arr[s.charAt(i) - 'a']++; } // Search the count of the character char ch = 'e'; // Get count System.out.println('The count of ' + ch + ' is ' + arr[ch - 'a']); } }> Python # Initialize a string s = 'geeksforgeeks' # Using a list to store the count of each alphabet # by mapping the character to an index value arr = [0] * 26 # Storing the count for i in range(len(s)): arr[ord(s[i]) - ord('a')] += 1 # Search the count of the character ch = 'e' # Get count print('The count of ', ch, ' is ', arr[ord(ch) - ord('a')])> C# using System; class Program { static void Main(string[] args) { //initialize a string string s = 'geeksforgeeks'; // Using an array to store the count of each alphabet // by mapping the character to an index value int[] arr = new int[26]; //Storing the count for (int i = 0; i < s.Length; i++) { arr[s[i] - 'a']++; } //Search the count of the character char ch = 'e'; // get count Console.WriteLine('The count of ' + ch + ' is ' + arr[ch - 'a']); } }> Javascript // Initialize a string const s = 'geeksforgeeks'; // Using an array to store the count of each alphabet // by mapping the character to an index value const arr = Array(26).fill(0); // Storing the count for (let i = 0; i < s.length; i++) { arr[s.charCodeAt(i) - 'a'.charCodeAt(0)]++; } // Search the count of the character const ch = 'e'; // Get count console.log(`The count of ${ch} is ${arr[ch.charCodeAt(0) - 'a'.charCodeAt(0)]}`);>
Uitgang:
The count of e is 4>
Complexiteitsanalyse van een hashtabel:
Voor opzoek-, invoeg- en verwijderbewerkingen hebben hashtabellen een gemiddelde tijdscomplexiteit van O(1). Toch kunnen deze bewerkingen in het ergste geval O(n) tijd vergen, waarbij n het aantal elementen in de tabel is.
Toepassingen van hashtabel:
- Hashtabellen worden vaak gebruikt voor het indexeren en doorzoeken van enorme hoeveelheden gegevens. Een zoekmachine kan een hashtabel gebruiken om de webpagina's op te slaan die hij heeft geïndexeerd.
- Gegevens worden doorgaans via hashtabellen in het geheugen opgeslagen, waardoor snelle toegang tot veelgebruikte informatie mogelijk is.
- Hash-functies worden vaak gebruikt in cryptografie om digitale handtekeningen te creëren, gegevens te valideren en de gegevensintegriteit te garanderen.
- Hashtabellen kunnen worden gebruikt voor het implementeren van database-indexen, waardoor snelle toegang tot gegevens op basis van sleutelwaarden mogelijk wordt.