Hvad er Hash Table?

En Hash-tabel er defineret som en datastruktur, der bruges til hurtigt at indsætte, slå op og fjerne nøgleværdi-par. Den opererer på hashing koncept , hvor hver tast er oversat af en hash-funktion til et særskilt indeks i en matrix. Indekset fungerer som et lagersted for den matchende værdi. Med enkle ord kortlægger det nøglerne med værdien.

Hvad er belastningsfaktor?

En hash-tabels belastningsfaktor bestemmes af, hvor mange elementer der opbevares der i forhold til, hvor stor bordet er. Bordet kan være rodet og have længere søgetider og kollisioner, hvis belastningsfaktoren er høj. En ideel belastningsfaktor kan opretholdes ved brug af en god hash-funktion og korrekt tabelstørrelse.

Hvad er en Hash-funktion?

En funktion, der oversætter nøgler til array-indekser, er kendt som en hash-funktion. Tasterne skal være jævnt fordelt over arrayet via en anstændig hash-funktion for at reducere kollisioner og sikre hurtige opslagshastigheder.

• Heltalsuniversantagelse: Nøglerne antages at være heltal inden for et bestemt område i henhold til antagelsen om heltalsuniverset. Dette muliggør brugen af ​​grundlæggende hashing-operationer som division eller multiplikation hashing.
• Hashing efter division: Denne ligetil hashing-teknik bruger nøglens resterende værdi efter at have divideret den med arrayets størrelse som indeks. Når en matrixstørrelse er et primtal, og tasterne er jævnt fordelt, fungerer den godt.
• Hashing ved multiplikation: Denne ligetil hashing-operation multiplicerer nøglen med en konstant mellem 0 og 1, før den tager brøkdelen af ​​resultatet. Derefter bestemmes indekset ved at gange brøkkomponenten med arrayets størrelse. Den fungerer også effektivt, når tasterne er lige spredt.

Valg af hash-funktion :

Valg af en anstændig hash-funktion er baseret på egenskaberne for tasterne og den tilsigtede funktionalitet af hash-tabellen. Det er afgørende at bruge en funktion, der fordeler tasterne jævnt og reducerer kollisioner.

Kriterier baseret på hvilke en hash-funktion er valgt:

• For at sikre at antallet af kollisioner holdes på et minimum, bør en god hash-funktion fordele nøglerne i hele hashtabellen på en ensartet måde. Dette indebærer, at for alle parringer af nøgler, bør sandsynligheden for, at to nøgler hash til den samme position i tabellen være ret konstant.
• For at muliggøre hurtig hash og nøglehentning, bør hash-funktionen være beregningseffektiv.
• Det burde være udfordrende at udlede nøglen fra dens hashværdi. Som følge heraf er det mindre sandsynligt, at forsøg på at gætte nøglen ved hjælp af hashværdien vil lykkes.
• En hash-funktion skal være fleksibel nok til at justere, efterhånden som de data, der hashes, ændres. For eksempel skal hash-funktionen fortsætte med at fungere korrekt, hvis de nøgler, der hash ændres i størrelse eller format.

Teknikker til løsning af kollisioner :

Kollisioner sker, når to eller flere nøgler peger på det samme array-indeks. Kædning, åben adressering og dobbelt hashing er nogle få teknikker til at løse kollisioner.

• Åben adressering : kollisioner håndteres ved at lede efter følgende tomme plads i tabellen. Hvis den første plads allerede er taget, anvendes hash-funktionen på de efterfølgende slots, indtil en efterlades tom. Der er forskellige måder at bruge denne tilgang på, herunder dobbelt hashing, lineær sondering og kvadratisk sondering.
• Separat kæde : I separat kæde er der en sammenkædet liste over objekter, der hash til hver plads i hash-tabellen. To nøgler er inkluderet i den sammenkædede liste, hvis de hash til samme slot. Denne metode er ret enkel at bruge og kan håndtere flere kollisioner.
• Robin Hood hashing: For at reducere længden af ​​kæden løses kollisioner i Robin Hood hashing ved at slukke for nøgler. Algoritmen sammenligner afstanden mellem spalten og den besatte plads for de to nøgler, hvis en ny nøgle hashes til en allerede optaget plads. Den eksisterende nøgle bliver skiftet ud med den nye, hvis den er tættere på dens ideelle slot. Dette bringer den eksisterende nøgle tættere på dens ideelle slot. Denne metode har en tendens til at skære ned på kollisioner og den gennemsnitlige kædelængde.

Dynamisk ændring af størrelse:

Denne funktion gør det muligt for hashtabellen at udvide eller trække sig sammen som svar på ændringer i antallet af elementer i tabellen. Dette fremmer en belastningsfaktor, der er ideel og hurtige opslagstider.

Implementeringer af Hash Table

Python, Java, C++ og Ruby er blot nogle få af de programmeringssprog, der understøtter hash-tabeller. De kan bruges som en tilpasset datastruktur ud over at de ofte er inkluderet i standardbiblioteket.

Eksempel – Tæl tegn i String-nørderne.

I dette eksempel bruger vi en hashing-teknik til lagring af strengens antal.

#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>

Kompleksitetsanalyse af en Hash-tabel:

Til opslags-, indsættelses- og sletningsoperationer har hashtabeller en gennemsnitlig sagstidskompleksitet på O(1). Alligevel kan disse operationer i værste fald kræve O(n) tid, hvor n er antallet af elementer i tabellen.

Anvendelser af Hash Table:

• Hash-tabeller bruges ofte til at indeksere og søge i enorme mængder af data. En søgemaskine kan bruge en hash-tabel til at gemme de websider, den har indekseret.
• Data cachelagres normalt i hukommelsen via hash-tabeller, hvilket muliggør hurtig adgang til ofte brugt information.
• Hash-funktioner bruges ofte i kryptografi til at skabe digitale signaturer, validere data og garantere dataintegritet.
• Hash-tabeller kan bruges til at implementere databaseindekser, hvilket muliggør hurtig adgang til data baseret på nøgleværdier.