Kaj je Hash Table?

Zgoščevalna tabela je definirana kot podatkovna struktura, ki se uporablja za hitro vstavljanje, iskanje in odstranjevanje parov ključ-vrednost. Deluje na koncept zgoščevanja , kjer je vsak ključ preveden s funkcijo zgoščevanja v poseben indeks v matriki. Indeks deluje kot lokacija za shranjevanje ujemajoče se vrednosti. Preprosto povedano, preslika ključe z vrednostjo.

Kaj je faktor obremenitve?

Faktor obremenitve zgoščene tabele je določen s tem, koliko elementov je tam shranjenih glede na to, kako velika je tabela. Tabela je lahko natrpana in ima daljše čase iskanja in trkov, če je faktor obremenitve visok. Idealen faktor obremenitve je mogoče vzdrževati z uporabo dobre zgoščevalne funkcije in ustreznega spreminjanja velikosti tabele.

Kaj je funkcija Hash?

Funkcija, ki prevaja ključe v matrične indekse, je znana kot zgoščevalna funkcija. Ključi morajo biti enakomerno porazdeljeni po matriki prek spodobne funkcije zgoščevanja, da se zmanjšajo kolizije in zagotovi hitra hitrost iskanja.

1 do 100 rimska št

• Predpostavka o celem vesolju: Predpostavlja se, da so ključi cela števila znotraj določenega obsega v skladu s predpostavko o celem vesolju. To omogoča uporabo osnovnih operacij zgoščevanja, kot je zgoščevanje deljenja ali množenja.
• Zgoščevanje z delitvijo: Ta preprosta tehnika zgoščevanja uporablja preostalo vrednost ključa, potem ko jo deli z velikostjo matrike kot indeks. Ko je velikost niza praštevilo in so ključi enakomerno razporejeni, deluje dobro.
• Zgoščevanje z množenjem: Ta preprosta operacija zgoščevanja pomnoži ključ s konstanto med 0 in 1, preden vzame delni del izida. Po tem se indeks določi z množenjem delne komponente z velikostjo matrike. Prav tako deluje učinkovito, ko so tipke enakomerno razpršene.

Izbira zgoščevalne funkcije :

Izbira primerne zgoščevalne funkcije temelji na lastnostih ključev in predvideni funkcionalnosti zgoščevalne tabele. Uporaba funkcije, ki enakomerno porazdeli tipke in zmanjša kolizije, je ključnega pomena.

Kriteriji, na podlagi katerih je izbrana zgoščevalna funkcija:

• Da bi zagotovili čim manjše število kolizij, mora dobra zgoščevalna funkcija enakomerno porazdeliti ključe po zgoščevalni tabeli. To pomeni, da mora biti za vse pare ključev verjetnost, da se dva ključa zgostita na istem mestu v tabeli, precej konstantna.
• Da bi omogočili hitro zgoščevanje in iskanje ključev, mora biti funkcija zgoščevanja računsko učinkovita.
• Izvesti ključ iz njegove zgoščene vrednosti bi moralo biti izziv. Posledično je manj verjetno, da bodo poskusi uganjanja ključa z zgoščeno vrednostjo uspešni.
• Zgoščevalna funkcija mora biti dovolj prilagodljiva, da se lahko prilagaja, ko se spreminjajo zgoščeni podatki. Na primer, funkcija zgoščevanja mora še naprej pravilno delovati, če se ključi, ki se zgoščajo, spremenijo v velikosti ali obliki.

Tehnike reševanja trkov :

Do trkov pride, ko dva ali več ključev kažeta na isti indeks polja. Veriženje, odprto naslavljanje in dvojno zgoščevanje je nekaj tehnik za reševanje kolizij.

• Odprto naslavljanje : trki se obravnavajo z iskanjem naslednjega praznega prostora v tabeli. Če je prva reža že zasedena, se zgoščevalna funkcija uporabi za naslednje reže, dokler ena ne ostane prazna. Obstaja več načinov za uporabo tega pristopa, vključno z dvojnim zgoščevanjem, linearnim in kvadratnim tipanjem.
• Ločeno veriženje : V ločenem veriženju je prisoten povezan seznam objektov, ki zgoščajo vsako režo v zgoščevalni tabeli. Dva ključa sta vključena v povezani seznam, če se razpršita v isto režo. Ta metoda je precej preprosta za uporabo in lahko obvlada več kolizij.
• Robin Hood zgoščevanje: Za zmanjšanje dolžine verige se trki pri zgoščevanju Robin Hooda odpravijo z izklopom tipk. Algoritem primerja razdaljo med režo in zasedeno režo obeh ključev, če nov ključ razprši že zasedeno režo. Obstoječi ključ se zamenja z novim, če je bližje svoji idealni reži. S tem se obstoječi ključ približa njegovi idealni reži. Ta metoda ima tendenco zmanjšanja kolizij in povprečne dolžine verige.

Dinamično spreminjanje velikosti:

Ta funkcija omogoča, da se zgoščevalna tabela razširi ali skrči kot odgovor na spremembe v številu elementov v tabeli. To spodbuja faktor obremenitve, ki je idealen in hiter čas iskanja.

razvrščanje na seznamu v Javi

Izvedbe zgoščene tabele

Python, Java, C++ in Ruby je le nekaj programskih jezikov, ki podpirajo zgoščene tabele. Uporabljajo se lahko kot prilagojena podatkovna struktura poleg tega, da so pogosto vključeni v standardno knjižnico.

Primer – štetje znakov v nizu geeksforgeeks.

V tem primeru uporabljamo tehniko zgoščevanja za shranjevanje števila nizov.

kaj je uri

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

Izhod:

The count of e is 4>

Analiza kompleksnosti zgoščene tabele:

Za operacije iskanja, vstavljanja in brisanja imajo zgoščene tabele povprečno časovno kompleksnost O(1). Vendar lahko te operacije v najslabšem primeru zahtevajo O(n) časa, kjer je n število elementov v tabeli.

Uporaba zgoščene tabele:

• Zgoščevalne tabele se pogosto uporabljajo za indeksiranje in iskanje velikih količin podatkov. Iskalnik lahko uporabi razpršilno tabelo za shranjevanje spletnih strani, ki jih je indeksiral.
• Podatki so običajno predpomnjeni v pomnilniku prek zgoščenih tabel, kar omogoča hiter dostop do pogosto uporabljenih informacij.
• Zgoščevalne funkcije se v kriptografiji pogosto uporabljajo za ustvarjanje digitalnih podpisov, preverjanje veljavnosti podatkov in zagotavljanje celovitosti podatkov.
• Zgoščevalne tabele se lahko uporabljajo za implementacijo indeksov baze podatkov, kar omogoča hiter dostop do podatkov na podlagi ključnih vrednosti.