Cos'è la tabella hash?

Una tabella Hash è definita come una struttura dati utilizzata per inserire, cercare e rimuovere rapidamente coppie chiave-valore. Opera su concetto di hashing , dove ciascuna chiave viene tradotta da una funzione hash in un indice distinto in un array. L'indice funziona come posizione di archiviazione per il valore corrispondente. In parole semplici, mappa le chiavi con il valore.

Cos'è il fattore di carico?

Il fattore di carico di una tabella hash è determinato da quanti elementi vengono conservati in relazione alla dimensione della tabella. La tabella potrebbe essere disordinata e avere tempi di ricerca più lunghi e collisioni se il fattore di carico è elevato. È possibile mantenere un fattore di carico ideale con l'uso di una buona funzione hash e di un adeguato ridimensionamento della tabella.

Cos'è una funzione Hash?

Una funzione che traduce le chiavi in ​​indici di array è nota come funzione hash. Le chiavi dovrebbero essere distribuite uniformemente nell'array tramite una funzione hash decente per ridurre le collisioni e garantire velocità di ricerca rapide.

• Presupposto dell'universo intero: Si presuppone che le chiavi siano numeri interi entro un certo intervallo secondo il presupposto dell'universo intero. Ciò consente l'uso di operazioni di hashing di base come l'hashing di divisione o moltiplicazione.
• Hashing per divisione: Questa semplice tecnica di hashing utilizza il valore rimanente della chiave dopo averlo diviso per la dimensione dell'array come indice. Quando la dimensione di un array è un numero primo e le chiavi sono equamente distanziate, funziona bene.
• Hashing per moltiplicazione: Questa semplice operazione di hashing moltiplica la chiave per una costante compresa tra 0 e 1 prima di prendere la parte frazionaria del risultato. Successivamente, l’indice viene determinato moltiplicando la componente frazionaria per la dimensione dell’array. Inoltre, funziona in modo efficace quando i tasti sono distribuiti equamente.

Scelta di una funzione hash :

La selezione di una funzione hash decente si basa sulle proprietà delle chiavi e sulla funzionalità prevista della tabella hash. È fondamentale utilizzare una funzione che distribuisca uniformemente i tasti e riduca le collisioni.

Criteri in base ai quali viene scelta una funzione hash:

• Per garantire che il numero di collisioni sia ridotto al minimo, una buona funzione hash dovrebbe distribuire le chiavi in ​​tutta la tabella hash in modo uniforme. Ciò implica che per tutte le coppie di chiavi, la probabilità che due chiavi abbiano la stessa posizione nella tabella dovrebbe essere piuttosto costante.
• Per consentire un hashing e un recupero delle chiavi rapidi, la funzione hash dovrebbe essere efficiente dal punto di vista computazionale.
• Dovrebbe essere difficile dedurre la chiave dal suo valore hash. Di conseguenza, i tentativi di indovinare la chiave utilizzando il valore hash hanno meno probabilità di successo.
• Una funzione hash dovrebbe essere sufficientemente flessibile da adattarsi alle modifiche dei dati sottoposti ad hashing. Ad esempio, la funzione hash deve continuare a funzionare correttamente se le chiavi sottoposte ad hashing cambiano in dimensione o formato.

Tecniche di risoluzione delle collisioni :

Le collisioni si verificano quando due o più chiavi puntano allo stesso indice di array. Il concatenamento, l'indirizzamento aperto e il doppio hashing sono alcune tecniche per risolvere le collisioni.

• Indirizzamento aperto : le collisioni vengono gestite cercando il seguente spazio vuoto nella tabella. Se il primo slot è già occupato, la funzione hash viene applicata agli slot successivi finché non ne viene lasciato uno vuoto. Esistono vari modi per utilizzare questo approccio, tra cui il doppio hashing, il sondaggio lineare e il sondaggio quadratico.
• Concatenamento separato : Nel concatenamento separato, è presente un elenco collegato di oggetti con hash su ciascuno slot nella tabella hash. Due chiavi sono incluse nell'elenco collegato se hanno lo stesso slot. Questo metodo è piuttosto semplice da usare e può gestire diverse collisioni.
• Hashing di Robin Hood: Per ridurre la lunghezza della catena, le collisioni nell'hashing di Robin Hood vengono risolte disattivando le chiavi. L'algoritmo confronta la distanza tra lo slot e lo slot occupato delle due chiavi se una nuova chiave ha un hash su uno slot già occupato. La chiave esistente viene sostituita con quella nuova se è più vicina allo slot ideale. Ciò avvicina la chiave esistente al suo slot ideale. Questo metodo tende a ridurre le collisioni e la lunghezza media della catena.

Ridimensionamento dinamico:

Questa funzionalità consente alla tabella hash di espandersi o contrarsi in risposta alle modifiche nel numero di elementi contenuti nella tabella. Ciò promuove un fattore di carico ideale e tempi di ricerca rapidi.

Implementazioni della tabella hash

Python, Java, C++ e Ruby sono solo alcuni dei linguaggi di programmazione che supportano le tabelle hash. Possono essere utilizzati come struttura dati personalizzata oltre ad essere spesso inclusi nella libreria standard.

Esempio: conta i caratteri in String geeksforgeeks.

In questo esempio utilizziamo una tecnica di hashing per archiviare il conteggio della stringa.

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

Produzione:

The count of e is 4>

Analisi della complessità di una tabella hash:

Per le operazioni di ricerca, inserimento ed eliminazione, le tabelle hash hanno una complessità temporale nel caso medio di O (1). Tuttavia, queste operazioni potrebbero, nel peggiore dei casi, richiedere un tempo O(n), dove n è il numero di elementi nella tabella.

Applicazioni della tabella hash:

• Le tabelle hash vengono spesso utilizzate per l'indicizzazione e la ricerca di enormi volumi di dati. Un motore di ricerca potrebbe utilizzare una tabella hash per archiviare le pagine web che ha indicizzato.
• I dati vengono solitamente memorizzati nella cache in memoria tramite tabelle hash, consentendo un rapido accesso alle informazioni utilizzate di frequente.
• Le funzioni hash vengono spesso utilizzate in crittografia per creare firme digitali, convalidare i dati e garantire l'integrità dei dati.
• Le tabelle hash possono essere utilizzate per implementare gli indici dei database, consentendo un accesso rapido ai dati in base ai valori chiave.