Hashing si riferisce al processo di generazione di un output di dimensione fissa da un input di dimensione variabile utilizzando le formule matematiche note come funzioni hash. Questa tecnica determina un indice o una posizione per l'archiviazione di un elemento in una struttura dati.

lo scorrimento del mouse non funziona

Necessità della struttura dei dati Hash

La quantità di dati su Internet cresce esponenzialmente ogni giorno, rendendo difficile archiviarli tutti in modo efficace. Nella programmazione quotidiana, questa quantità di dati potrebbe non essere così grande, ma è comunque necessario archiviarla, accedervi ed elaborarla in modo semplice ed efficiente. Una struttura dati molto comune utilizzata per tale scopo è la struttura dati Array.

Ora sorge la domanda: se Array esisteva già, che bisogno c'era di una nuova struttura dati! La risposta a questa domanda è nella parola efficienza. Anche se l'archiviazione in Array richiede O(1) tempo, cercarci ci vuole almeno O(log n) tempo. Questo tempo sembra essere piccolo, ma per un set di dati di grandi dimensioni può causare molti problemi e questo, a sua volta, rende inefficiente la struttura dei dati dell'array.

Quindi ora stiamo cercando una struttura dati in grado di memorizzare i dati e cercarli in tempo costante, cioè in O(1) tempo. È così che è entrata in gioco la struttura dei dati Hashing. Con l'introduzione della struttura dati Hash, è ora possibile archiviare facilmente i dati in tempo costante e recuperarli anche in tempo costante.

Componenti dell'hashing

Esistono principalmente tre componenti dell'hashing:

1. Chiave: UN Chiave può essere qualsiasi stringa o numero intero fornito come input nella funzione hash, la tecnica che determina un indice o una posizione per l'archiviazione di un elemento in una struttura dati.
2. Funzione hash: IL funzione hash riceve la chiave di input e restituisce l'indice di un elemento in un array chiamato tabella hash. L'indice è noto come indice hash .
3. Tabella hash: La tabella hash è una struttura dati che mappa le chiavi sui valori utilizzando una funzione speciale chiamata funzione hash. L'hash memorizza i dati in modo associativo in un array in cui ciascun valore dei dati ha il proprio indice univoco.

Componenti dell'hashing

Cos'è la collisione?

Il processo di hashing genera un numero piccolo per una chiave grande, quindi esiste la possibilità che due chiavi possano produrre lo stesso valore. La situazione in cui la chiave appena inserita corrisponde a una chiave già occupata e deve essere gestita utilizzando una tecnologia di gestione delle collisioni.

Collisione nell'hashing

scheda SIM inserita ma nessun servizio Android

Vantaggi dell'hashing nelle strutture dati

• Supporto valori-chiave: L'hashing è ideale per implementare strutture di dati chiave-valore.
• Recupero veloce dei dati: L'hashing consente un rapido accesso agli elementi con complessità a tempo costante.
• Efficienza: Le operazioni di inserimento, cancellazione e ricerca sono altamente efficienti.
• Riduzione dell'utilizzo della memoria: L'hashing richiede meno memoria poiché alloca uno spazio fisso per la memorizzazione degli elementi.
• Scalabilità: L'hashing funziona bene con set di dati di grandi dimensioni, mantenendo un tempo di accesso costante.
• Sicurezza e crittografia: L'hashing è essenziale per l'archiviazione sicura dei dati e la verifica dell'integrità.

Per saperne di più sull'hashing fare riferimento al file Introduzione all'hashing: esercitazioni sulla struttura dei dati e sugli algoritmi