Ce este Hash Table?

Un tabel Hash este definit ca o structură de date folosită pentru a insera, căuta și elimina rapid perechile cheie-valoare. Acesta operează pe conceptul de hashing , unde fiecare cheie este tradusă printr-o funcție hash într-un index distinct într-o matrice. Indexul funcționează ca o locație de stocare pentru valoarea de potrivire. Cu cuvinte simple, mapează cheile cu valoarea.

inurl:.git/head

Ce este factorul de încărcare?

Factorul de încărcare al unui tabel hash este determinat de câte elemente sunt păstrate acolo în raport cu cât de mare este tabelul. Tabelul poate fi aglomerat și poate avea timpi de căutare și coliziuni mai lungi dacă factorul de încărcare este mare. Un factor de încărcare ideal poate fi menținut prin utilizarea unei bune funcții hash și a unei redimensionări adecvate a tabelului.

Ce este o funcție Hash?

O funcție care traduce cheile în indici de matrice este cunoscută ca o funcție hash. Cheile ar trebui să fie distribuite uniform în cadrul matricei printr-o funcție hash decentă pentru a reduce coliziunile și pentru a asigura viteze rapide de căutare.

• Ipoteza universului întreg: Se presupune că cheile sunt numere întregi într-un anumit interval, conform ipotezei universului întreg. Acest lucru permite utilizarea operațiunilor de hashing de bază, cum ar fi hashingul de împărțire sau multiplicare.
• Hashing după diviziune: Această tehnică simplă de hashing folosește valoarea rămasă a cheii după ce o împarte la dimensiunea matricei ca index. Când dimensiunea unei matrice este un număr prim și cheile sunt distanțate uniform, funcționează bine.
• Hashing prin înmulțire: Această operație de hashing simplă înmulțește cheia cu o constantă între 0 și 1 înainte de a lua porțiunea fracțională a rezultatului. După aceea, indicele este determinat prin înmulțirea componentei fracționale cu dimensiunea matricei. De asemenea, funcționează eficient atunci când tastele sunt împrăștiate în mod egal.

Alegerea unei funcții hash :

Selectarea unei funcții hash decente se bazează pe proprietățile tastelor și pe funcționalitatea dorită a tabelului hash. Utilizarea unei funcții care distribuie uniform cheile și reduce coliziunile este crucială.

Criterii pe baza cărora este aleasă o funcție hash:

• Pentru a vă asigura că numărul de coliziuni este menținut la un nivel minim, o funcție de hash bună ar trebui să distribuie cheile în tabelul de hash într-o manieră uniformă. Acest lucru implică faptul că, pentru toate perechile de chei, probabilitatea ca două chei să atingă aceeași poziție în tabel ar trebui să fie destul de constantă.
• Pentru a permite hashingul rapid și recuperarea cheilor, funcția hash ar trebui să fie eficientă din punct de vedere computațional.
• Ar trebui să fie dificil să deducem cheia din valoarea hash. Ca rezultat, încercările de a ghici cheia folosind valoarea hash sunt mai puțin probabil să reușească.
• O funcție hash ar trebui să fie suficient de flexibilă pentru a fi ajustată pe măsură ce se modifică datele hash. De exemplu, funcția hash trebuie să continue să funcționeze corect dacă cheile care sunt hash își schimbă dimensiunea sau formatul.

Tehnici de rezolvare a coliziunilor :

Coliziunile au loc atunci când două sau mai multe chei indică același index de matrice. Înlănțuirea, adresarea deschisă și hashingul dublu sunt câteva tehnici de rezolvare a coliziunilor.

• Adresare deschisă : coliziunile sunt tratate prin căutarea următorului spațiu gol în tabel. Dacă primul slot este deja ocupat, funcția hash este aplicată sloturilor ulterioare până când unul rămâne gol. Există diferite moduri de a folosi această abordare, inclusiv hashing dublu, sondare liniară și sondare pătratică.
• Înlănțuire separată : În înlănțuire separată, este prezentă o listă legată de obiecte care se hash la fiecare slot din tabelul hash. Două chei sunt incluse în lista legată dacă au acces la același slot. Această metodă este destul de simplă de utilizat și poate gestiona mai multe coliziuni.
• Hashing Robin Hood: Pentru a reduce lungimea lanțului, coliziunile în hashing Robin Hood sunt abordate prin dezactivarea tastelor. Algoritmul compară distanța dintre slot și slotul ocupat al celor două chei în cazul în care o nouă cheie se lovește la un slot deja ocupat. Cheia existentă este schimbată cu cea nouă dacă este mai aproape de slotul ideal. Acest lucru aduce cheia existentă mai aproape de slotul ideal. Această metodă are tendința de a reduce coliziunile și lungimea medie a lanțului.

Redimensionare dinamică:

Această caracteristică permite tabelului hash să se extindă sau să se contracte ca răspuns la modificările numărului de elemente conținute în tabel. Acest lucru promovează un factor de încărcare care este ideal și timpi de căutare rapide.

Implementări Hash Table

Python, Java, C++ și Ruby sunt doar câteva dintre limbajele de programare care acceptă tabele hash. Ele pot fi folosite ca o structură de date personalizată, pe lângă faptul că sunt incluse frecvent în biblioteca standard.

Exemplu – Numărați caracterele din String geeksforgeeks.

În acest exemplu, folosim o tehnică de hashing pentru stocarea numărului șirului.

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

Ieșire:

The count of e is 4>

Analiza complexității unui tabel Hash:

Pentru operațiunile de căutare, inserare și ștergere, tabelele hash au o complexitate medie de timp de O(1). Totuși, aceste operații pot necesita, în cel mai rău caz, timp O(n), unde n este numărul de elemente din tabel.

Aplicații ale tabelului Hash:

• Tabelele hash sunt frecvent utilizate pentru indexarea și căutarea unor volume masive de date. Un motor de căutare poate folosi un tabel hash pentru a stoca paginile web pe care le-a indexat.
• Datele sunt de obicei stocate în cache în memorie prin tabele hash, permițând accesul rapid la informațiile utilizate frecvent.
• Funcțiile hash sunt frecvent utilizate în criptografie pentru a crea semnături digitale, a valida datele și a garanta integritatea datelor.
• Tabelele hash pot fi utilizate pentru implementarea indexurilor bazelor de date, permițând accesul rapid la date pe baza valorilor cheie.