Hashing nella struttura dei dati: funzione, tecniche [con esempi]
Pubblicato: 2021-05-02Sommario
introduzione
L'hashing è un'importante struttura di dati progettata per risolvere il problema di trovare e archiviare in modo efficiente i dati in un array. Ad esempio, se hai un elenco di 20000 numeri e hai fornito un numero da cercare in quell'elenco, eseguirai la scansione di ogni numero nell'elenco fino a trovare una corrispondenza.
Richiede una notevole quantità di tempo per cercare nell'intero elenco e individuare quel numero specifico. Questo processo manuale di scansione non è solo dispendioso in termini di tempo, ma anche inefficiente. Con l'hashing nella struttura dei dati, puoi restringere la ricerca e trovare il numero in pochi secondi.
Questo blog ti fornirà una comprensione più approfondita del metodo hash, delle tabelle hash e del sondaggio lineare con esempi.
Che cos'è l'hashing nella struttura dei dati?
L'hashing nella struttura dei dati è una tecnica per mappare una grossa porzione di dati in piccole tabelle usando una funzione di hashing. È anche nota come funzione di digest del messaggio. È una tecnica che identifica in modo univoco un articolo specifico da una raccolta di articoli simili.
Utilizza tabelle hash per archiviare i dati in un formato array. A ogni valore nell'array è assegnato un numero di indice univoco. Le tabelle hash utilizzano una tecnica per generare questi numeri di indice univoci per ogni valore archiviato in un formato matrice. Questa tecnica è chiamata tecnica hash.
Hai solo bisogno di trovare l'indice dell'elemento desiderato, invece di trovare i dati. Con l'indicizzazione, puoi scansionare rapidamente l'intero elenco e recuperare l'elemento che desideri. L'indicizzazione aiuta anche nell'inserimento di operazioni quando è necessario inserire dati in una posizione specifica. Non importa quanto grande o piccola sia la tabella, puoi aggiornare e recuperare i dati in pochi secondi.
L'hashing in una struttura dati è un processo in due fasi.
- La funzione hash converte l'elemento in un piccolo intero o valore hash. Questo numero intero viene utilizzato come indice per memorizzare i dati originali.
- Memorizza i dati in una tabella hash. È possibile utilizzare una chiave hash per individuare rapidamente i dati.
Esempi di hashing nella struttura dei dati
I seguenti sono esempi reali di hashing nella struttura dei dati :
- Nelle scuole, l'insegnante assegna un numero di ruolo univoco a ogni studente. Successivamente, l'insegnante utilizza quel numero di registro per recuperare informazioni su quello studente.
- Una biblioteca ha un numero infinito di libri. Il bibliotecario assegna un numero univoco a ciascun libro. Questo numero univoco aiuta a identificare la posizione dei libri sullo scaffale.
Checkout: ordinamento nella struttura dei dati
Funzione hash
La funzione hash in una struttura dati associa dimensioni arbitrarie di dati a dati di dimensioni fisse. Restituisce i seguenti valori: un piccolo valore intero (noto anche come valore hash), codici hash e somme hash.
hash = hashfunc(chiave)
indice = hash % array_size
La funzione has deve soddisfare i seguenti requisiti:
- Una buona funzione hash è facile da calcolare.
- Una buona funzione hash non si blocca mai nel clustering e distribuisce le chiavi in modo uniforme nella tabella hash.
- Una buona funzione hash evita la collisione quando due elementi o elementi vengono assegnati allo stesso valore hash.
Tavolo Hash
L'hashing nella struttura dei dati utilizza le tabelle hash per archiviare le coppie chiave-valore. La tabella hash utilizza quindi la funzione hash per generare un indice. L'hashing utilizza questo indice univoco per eseguire operazioni di inserimento, aggiornamento e ricerca.
Come funziona l'hashing nella struttura dei dati?
Nell'hashing, la funzione di hashing associa stringhe o numeri a un valore intero piccolo. Le tabelle hash recuperano l'elemento dall'elenco utilizzando una funzione di hashing. L'obiettivo della tecnica di hashing è distribuire i dati in modo uniforme su un array. L'hashing assegna a tutti gli elementi una chiave univoca. La tabella hash utilizza questa chiave per accedere ai dati nell'elenco.
La tabella hash memorizza i dati in una coppia chiave-valore. Il tasto funge da input per la funzione di hashing. La funzione di hashing genera quindi un numero di indice univoco per ogni valore memorizzato. Il numero di indice mantiene il valore che corrisponde a quella chiave. La funzione hash restituisce un piccolo valore intero come output. L'output della funzione hash è chiamato valore hash.
Cerchiamo di capire l' hashing in una struttura di dati con un esempio. Immagina di dover archiviare alcuni elementi (disposti in una coppia chiave-valore) all'interno di una tabella hash con 30 celle.
I valori sono: (3,21) (1,72) (40,36) (5,30) (11,44) (15,33) (18,12) (16,80) (38,99)
La tabella hash sarà simile alla seguente:
| Numero di serie | Chiave | Hash | Indice di matrice |
| 1 | 3 | 3%30 = 3 | 3 |
| 2 | 1 | 1%30 = 1 | 1 |
| 3 | 40 | 40%30 = 10 | 10 |
| 4 | 5 | 5%30 = 5 | 5 |
| 5 | 11 | 11%30 = 11 | 11 |
| 6 | 15 | 15%30 = 15 | 15 |
| 7 | 18 | 18%30 = 18 | 18 |
| 8 | 16 | 16%30 = 16 | 16 |
| 9 | 38 | 38%30 = 8 | 8 |
Leggi anche: Tipi di strutture dati in Python
Tecniche di risoluzione delle collisioni
L'hashing nella struttura dei dati cade in una collisione se a due chiavi viene assegnato lo stesso numero di indice nella tabella hash. La collisione crea un problema perché ogni indice in una tabella hash dovrebbe memorizzare un solo valore. L'hashing nella struttura dei dati utilizza diverse tecniche di risoluzione delle collisioni per gestire le prestazioni di una tabella hash.
Sondaggio lineare
L'hashing nella struttura dei dati risulta in un indice di matrice che è già occupato per memorizzare un valore. In tal caso, l'hashing esegue un'operazione di ricerca e ricerca linearmente la cella vuota successiva.
Esempio di indagine lineare
Immagina che ti sia stato chiesto di archiviare alcuni articoli all'interno di una tabella hash di dimensione 30. Gli articoli sono già ordinati in un formato di coppia chiave-valore. I valori riportati sono: (3,21) (1,72) (63,36) (5,30) (11,44) (15,33) (18,12) (16,80) (46,99) .
L'hash(n) è l'indice calcolato utilizzando una funzione hash e T è la dimensione della tabella. Se lo slot index = ( hash(n) % T) è pieno, allora cerchiamo l'indice di slot successivo aggiungendo 1 ((hash(n) + 1) % T). Se anche (hash(n) + 1) % T è pieno, allora proviamo (hash(n) + 2) % T. Se anche (hash(n) + 2) % T è pieno, allora proviamo (hash( n) + 3) % T.
La tabella hash sarà simile alla seguente:
| Numero di serie | Chiave | Hash | Indice di matrice | Indice di matrice dopo il sondaggio lineare |
| 1 | 3 | 3%30 = 3 | 3 | 3 |
| 2 | 1 | 1%30 = 1 | 1 | 1 |
| 3 | 63 | 63%30 = 3 | 3 | 4 |
| 4 | 5 | 5%30 = 5 | 5 | 5 |
| 5 | 11 | 11%30 = 11 | 11 | 11 |
| 6 | 15 | 15%30 = 15 | 15 | 15 |
| 7 | 18 | 18%30 = 18 | 18 | 18 |
| 8 | 16 | 16%30 = 16 | 16 | 16 |
| 9 | 46 | 46%30 = 8 | 16 | 17 |
Doppio Hashing
La tecnica del double hashing utilizza due funzioni hash. La seconda funzione hash entra in uso quando la prima funzione provoca una collisione. Fornisce un indice di offset per memorizzare il valore.
La formula per la tecnica del double hashing è la seguente:
(firstHash(chiave) + i * secondHash(chiave)) % sizeOfTable
Dove i è il valore di offset. Questo valore di offset viene incrementato finché non trova uno slot vuoto.
Ad esempio, hai due funzioni hash: h1 e h2. È necessario eseguire i seguenti passaggi per trovare uno slot vuoto:
- Verifica se hash1(key) è vuoto. Se sì, memorizza il valore in questo slot.
- Se hash1(key) non è vuoto, trova un altro slot usando hash2(key).
- Verifica se hash1(key) + hash2(key) è vuoto. Se sì, memorizza il valore in questo slot.
- Continua ad incrementare il contatore e ripeti con hash1(key)+2hash2(key), hash1(key)+3hash2(key) e così via, finché non trova uno slot vuoto.
Esempio di doppio hashing
Immagina di dover memorizzare alcuni elementi all'interno di una tabella hash di dimensione 20. I valori indicati sono: (16, 8, 63, 9, 27, 37, 48, 5, 69, 34, 1).
h1(n)=n%20
h2(n)=n%13
nh(n, i) = (h1 (n) + ih2(n)) mod 20
| n | h(n,i) = (h'(n) + io 2 ) %20 |
| 16 | io = 0, h(n,0) = 16 |
| 8 | io = 0, h(n,0) = 8 |
| 63 | io = 0, h(n,0) = 3 |
| 9 | io = 0, h(n,0) = 9 |
| 27 | io = 0, h(n,0) = 7 |
| 37 | io = 0, h(n,0) = 17 |
| 48 | io = 0, h(n,0) = 8 io = 0, h(n,1) = 9 io = 0, h(n,2) = 12 |
| 5 | io = 0, h(n,0) = 5 |
| 69 | io = 0, h(n,0) = 9 io = 0, h(n,1) = 10 |
| 34 | io = 0, h(n,0) = 14 |
| 1 | io = 0, h(n,0) = 1 |
Conclusione
Il doppio hashing ha un costo di calcolo elevato, ma ricerca lo slot libero successivo più velocemente rispetto al metodo di probing lineare. Gli esempi forniti nell'articolo sono solo a scopo esplicativo. È possibile modificare le dichiarazioni sopra riportate in base alle proprie esigenze. In questo blog abbiamo appreso il concetto di hashing nella struttura dei dati .
Puoi provare l'esempio per rafforzare la tua conoscenza della struttura dei dati. Se sei curioso di saperne di più sulla struttura dei dati , dai un'occhiata al programma upGrad Executive PG nel corso Full Stack Development . Questo corso è progettato per professionisti che lavorano e offre una formazione rigorosa e l'inserimento lavorativo con le migliori aziende.
Cos'è una tabella hash?
Una tabella hash è un'implementazione di un array associativo, una struttura utilizzata nella programmazione di computer per implementare un tipo di dati astratto (ADT). In un tipo di dati astratto, il programmatore non ha bisogno di conoscere i dettagli di implementazione del tipo di dati (come il modo in cui i dati sono archiviati in memoria), ma solo le operazioni che possono essere eseguite sul tipo di dati. Una tabella hash utilizza una funzione hash per calcolare un indice in una matrice di bucket o slot, da cui è possibile trovare il valore desiderato. Le tabelle hash vengono utilizzate per implementare strutture di dati simili a mappe. Le tabelle hash sono molto utilizzate nei computer moderni per implementare cose come dizionari (come in python), array associativi (come in php), tabelle hash java, ecc. Le tabelle hash sono solitamente implementate nelle lingue come array di valori ordinati in base alle loro chiavi . Ciò rende le operazioni di ricerca e inserimento/cancellazione molto veloci, poiché i dati vengono archiviati sistematicamente in memoria.
Quali sono le applicazioni delle funzioni di hashing?
Le funzioni di hashing vengono utilizzate per diverse applicazioni nell'informatica, ad esempio crittografia e fingerprinting dei documenti. Lo scopo principale di una funzione di hashing è mappare grandi quantità di input su un output di lunghezza fissa. In crittografia, l'hashing viene utilizzato per garantire che un messaggio o un documento non sia stato manomesso. Se il documento o il messaggio viene alterato in qualsiasi modo (anche un solo carattere), viene alterato anche il valore hash. È quindi quasi impossibile creare un documento o un messaggio con un determinato valore hash.
Quali sono le tecniche di risoluzione delle collisioni nell'hashing?
Le tecniche di risoluzione delle collisioni nell'hashing vengono utilizzate per risolvere le collisioni nell'hashing. Le tecniche di risoluzione delle collisioni sono il concatenamento o l'indirizzamento aperto. Nel concatenamento, manteniamo il vecchio elemento in posizione e inseriamo il nuovo elemento nel successivo spazio disponibile. È un metodo semplice per la risoluzione delle collisioni, ma presenta lo svantaggio di scarse prestazioni. Nell'indirizzamento aperto, sostituiamo il vecchio elemento con il nuovo elemento e contrassegniamo il vecchio elemento come una collisione.