Vad är Hash Table?

En Hash-tabell definieras som en datastruktur som används för att snabbt infoga, slå upp och ta bort nyckel-värdepar. Den verkar på hashing koncept , där varje tangent översätts av en hashfunktion till ett distinkt index i en array. Indexet fungerar som en lagringsplats för det matchande värdet. Med enkla ord mappar den nycklarna med värdet.

Vad är belastningsfaktor?

En hashtabells belastningsfaktor bestäms av hur många element som finns där i förhållande till hur stor tabellen är. Bordet kan vara rörigt och ha längre söktider och kollisioner om belastningsfaktorn är hög. En idealisk belastningsfaktor kan upprätthållas med hjälp av en bra hashfunktion och korrekt tabellstorlek.

Vad är en Hash-funktion?

En funktion som översätter nycklar till arrayindex är känd som en hashfunktion. Nycklarna bör vara jämnt fördelade över arrayen via en anständig hashfunktion för att minska kollisioner och säkerställa snabba uppslagshastigheter.

• Heltalsuniversumsantagande: Nycklarna antas vara heltal inom ett visst intervall enligt heltalsuniversumsantagandet. Detta möjliggör användningen av grundläggande hashoperationer som division eller multiplikationshashning.
• Hashing efter division: Denna enkla hashteknik använder nyckelns återstående värde efter att ha dividerat det med arrayens storlek som index. När en matrisstorlek är ett primtal och nycklarna är jämnt fördelade, fungerar den bra.
• Hashing genom multiplikation: Denna enkla hash-operation multiplicerar nyckeln med en konstant mellan 0 och 1 innan den tar del av resultatet. Därefter bestäms indexet genom att multiplicera bråkkomponenten med arrayens storlek. Den fungerar också effektivt när tangenterna är lika utspridda.

Att välja en hashfunktion :

Att välja en anständig hashfunktion baseras på egenskaperna hos nycklarna och den avsedda funktionaliteten hos hashtabellen. Att använda en funktion som jämnt fördelar nycklarna och minskar kollisioner är avgörande.

Kriterier baserade på vilka en hashfunktion väljs:

• För att säkerställa att antalet kollisioner hålls till ett minimum bör en bra hashfunktion fördela nycklarna över hela hashtabellen på ett enhetligt sätt. Detta innebär att sannolikheten för att två nycklar hash till samma position i tabellen bör vara ganska konstant för alla parningar av nycklar.
• För att möjliggöra snabb hashning och nyckelhämtning bör hashfunktionen vara beräkningseffektiv.
• Det borde vara utmanande att härleda nyckeln från dess hashvärde. Som ett resultat är det mindre sannolikt att försök att gissa nyckeln med hjälp av hashvärdet lyckas.
• En hashfunktion bör vara tillräckligt flexibel för att justera allt eftersom data som hashas ändras. Till exempel måste hashfunktionen fortsätta att fungera korrekt om nycklarna som hashas ändras i storlek eller format.

Kollisionsupplösningstekniker :

Kollisioner inträffar när två eller flera nycklar pekar på samma arrayindex. Kedjekoppling, öppen adressering och dubbelhashning är några tekniker för att lösa kollisioner.

• Öppna adressering : kollisioner hanteras genom att leta efter följande tomma utrymme i tabellen. Om den första luckan redan har tagits, tillämpas hashfunktionen på de efterföljande luckorna tills en lämnas tom. Det finns olika sätt att använda detta tillvägagångssätt, inklusive dubbelhashning, linjär sondering och kvadratisk sondering.
• Separat kedja : I separat kedja finns en länkad lista med objekt som hash till varje plats i hashtabellen. Två nycklar ingår i den länkade listan om de hash till samma plats. Denna metod är ganska enkel att använda och kan hantera flera kollisioner.
• Robin Hood hashing: För att minska kedjans längd åtgärdas kollisioner i Robin Hood-hashing genom att stänga av nycklar. Algoritmen jämför avståndet mellan luckan och den upptagna luckan för de två nycklarna om en ny nyckel hash till en redan upptagen lucka. Den befintliga nyckeln byts ut med den nya om den är närmare sin ideala plats. Detta för den befintliga nyckeln närmare sin ideala plats. Denna metod har en tendens att minska kollisioner och genomsnittlig kedjelängd.

Dynamisk storleksändring:

Den här funktionen gör det möjligt för hashtabellen att expandera eller krympa som svar på ändringar i antalet element i tabellen. Detta främjar en belastningsfaktor som är idealisk och snabba uppslagstider.

Implementeringar av Hash Table

Python, Java, C++ och Ruby är bara några av de programmeringsspråk som stöder hashtabeller. De kan användas som en anpassad datastruktur förutom att de ofta ingår i standardbiblioteket.

Exempel – Räkna tecken i String-geeksforgeeks.

I det här exemplet använder vi en hashteknik för att lagra antalet av strängen.

#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

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']);  } }>

# 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')])>

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']);  } }>

// 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)]}`);>

Produktion:

The count of e is 4>

Komplexitetsanalys av en hashtabell:

För uppslags-, infognings- och borttagningsoperationer har hashtabeller en tidskomplexitet för genomsnittliga fall på O(1). Ändå kan dessa operationer i värsta fall kräva O(n) tid, där n är antalet element i tabellen.

Tillämpningar av Hash Table:

• Hash-tabeller används ofta för att indexera och söka i stora mängder data. En sökmotor kan använda en hashtabell för att lagra webbsidorna som den har indexerat.
• Data cachelagras vanligtvis i minnet via hashtabeller, vilket möjliggör snabb åtkomst till ofta använd information.
• Hash-funktioner används ofta i kryptografi för att skapa digitala signaturer, validera data och garantera dataintegritet.
• Hash-tabeller kan användas för att implementera databasindex, vilket möjliggör snabb åtkomst till data baserat på nyckelvärden.