Hva er Hash Table?

En Hash-tabell er definert som en datastruktur som brukes til å sette inn, slå opp og fjerne nøkkelverdi-par raskt. Den opererer på hashing-konsept , hvor hver tast er oversatt av en hash-funksjon til en distinkt indeks i en matrise. Indeksen fungerer som et lagringssted for den samsvarende verdien. Med enkle ord, kartlegger den nøklene med verdien.

Hva er belastningsfaktor?

En hash-tabells belastningsfaktor bestemmes av hvor mange elementer som holdes der i forhold til hvor stor tabellen er. Bordet kan være rotete og ha lengre søketider og kollisjoner hvis belastningsfaktoren er høy. En ideell belastningsfaktor kan opprettholdes ved bruk av en god hash-funksjon og riktig tabellstørrelse.

Hva er en Hash-funksjon?

En funksjon som oversetter nøkler til array-indekser er kjent som en hash-funksjon. Nøklene skal være jevnt fordelt over arrayet via en anstendig hash-funksjon for å redusere kollisjoner og sikre raske oppslagshastigheter.

• Heltallsuniversantagelse: Nøklene antas å være heltall innenfor et visst område i henhold til heltallsuniverset. Dette muliggjør bruk av grunnleggende hashing-operasjoner som divisjons- eller multiplikasjonshashing.
• Hashing etter divisjon: Denne enkle hashing-teknikken bruker nøkkelens gjenværende verdi etter å ha delt den med matrisens størrelse som indeks. Når en matrisestørrelse er et primtall og tastene er jevnt fordelt, gir den gode resultater.
• Hashing ved multiplikasjon: Denne enkle hashing-operasjonen multipliserer nøkkelen med en konstant mellom 0 og 1 før du tar brøkdelen av resultatet. Etter det bestemmes indeksen ved å multiplisere brøkkomponenten med matrisens størrelse. Den fungerer også effektivt når tastene er spredt likt.

Velge en hash-funksjon :

Å velge en anstendig hash-funksjon er basert på egenskapene til tastene og den tiltenkte funksjonaliteten til hash-tabellen. Å bruke en funksjon som jevnt fordeler tastene og reduserer kollisjoner er avgjørende.

Kriterier basert på hvilke hash-funksjoner er valgt:

• For å sikre at antall kollisjoner holdes på et minimum, bør en god hash-funksjon fordele nøklene gjennom hashtabellen på en jevn måte. Dette innebærer at for alle sammenkoblinger av nøkler, bør sannsynligheten for at to nøkler hash til samme posisjon i tabellen være ganske konstant.
• For å muliggjøre rask hashing og nøkkelhenting, bør hash-funksjonen være beregningseffektiv.
• Det burde være utfordrende å utlede nøkkelen fra hashverdien. Som et resultat er det mindre sannsynlig at forsøk på å gjette nøkkelen ved hjelp av hash-verdien vil lykkes.
• En hash-funksjon bør være fleksibel nok til å justere etter hvert som dataene som hash endres. For eksempel må hash-funksjonen fortsette å fungere riktig hvis nøklene som hash endres i størrelse eller format.

Teknikker for kollisjonsoppløsning :

Kollisjoner skjer når to eller flere nøkler peker til samme matriseindeks. Kjetting, åpen adressering og dobbel hashing er noen få teknikker for å løse kollisjoner.

• Åpen adressering : kollisjoner håndteres ved å se etter følgende tomme plass i tabellen. Hvis det første sporet allerede er tatt, blir hash-funksjonen brukt på de påfølgende sporene inntil en er tom. Det er forskjellige måter å bruke denne tilnærmingen på, inkludert dobbel hashing, lineær sondering og kvadratisk sondering.
• Separat kjetting : I separat kjeding er en koblet liste over objekter som hash til hvert spor i hash-tabellen til stede. To nøkler er inkludert i den koblede listen hvis de hash til samme spor. Denne metoden er ganske enkel å bruke og kan håndtere flere kollisjoner.
• Robin Hood hashing: For å redusere lengden på kjeden adresseres kollisjoner i Robin Hood-hashing ved å slå av nøkler. Algoritmen sammenligner avstanden mellom sporet og det okkuperte sporet for de to nøklene hvis en ny nøkkel hashes til en allerede opptatt spor. Den eksisterende nøkkelen blir byttet ut med den nye hvis den er nærmere sin ideelle spor. Dette bringer den eksisterende nøkkelen nærmere det ideelle sporet. Denne metoden har en tendens til å redusere kollisjoner og gjennomsnittlig kjedelengde.

Dynamisk endring av størrelse:

Denne funksjonen gjør det mulig for hash-tabellen å utvide eller trekke seg sammen som svar på endringer i antall elementer i tabellen. Dette fremmer en belastningsfaktor som er ideell og raske oppslagstider.

Implementeringer av Hash Table

Python, Java, C++ og Ruby er bare noen få av programmeringsspråkene som støtter hash-tabeller. De kan brukes som en tilpasset datastruktur i tillegg til at de ofte er inkludert i standardbiblioteket.

Eksempel – Tell tegn i String-geeksforgeeks.

I dette eksemplet bruker vi en hashing-teknikk for å lagre antallet av strengen.

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

Produksjon:

The count of e is 4>

Kompleksitetsanalyse av en hash-tabell:

For oppslags-, innsettings- og slettingsoperasjoner har hashtabeller en gjennomsnittlig sakstidskompleksitet på O(1). Likevel kan disse operasjonene i verste fall kreve O(n) tid, der n er antall elementer i tabellen.

Anvendelser av Hash Table:

• Hash-tabeller brukes ofte til å indeksere og søke i enorme mengder data. En søkemotor kan bruke en hash-tabell for å lagre nettsidene den har indeksert.
• Data bufres vanligvis i minnet via hash-tabeller, noe som gir rask tilgang til ofte brukt informasjon.
• Hash-funksjoner brukes ofte i kryptografi for å lage digitale signaturer, validere data og garantere dataintegritet.
• Hash-tabeller kan brukes til å implementere databaseindekser, noe som gir rask tilgang til data basert på nøkkelverdier.