Hashing nei DBMS: tecniche di hashing statico e dinamico
Fiona Marrone
⚡ Riepilogo intelligente
Nei DBMS, l'hashing è una tecnica che calcola la posizione su disco di un record direttamente dalla sua chiave, senza attraversare un indice. Una funzione hash associa le chiavi di ricerca ai bucket di dati e l'hashing, statico o dinamico, gestisce la crescita di tali bucket.
Cos'è l'hashing nel DBMS?
Nei DBMS, l'hashing è una tecnica per cercare direttamente la posizione dei dati desiderati sul disco senza utilizzare una struttura di indice. Il metodo di hashing viene utilizzato per indicizzare e recuperare elementi in un database, poiché è più veloce cercare un elemento specifico utilizzando la chiave hash più corta invece del suo valore originale. I dati vengono memorizzati sotto forma di blocchi di dati il cui indirizzo viene generato applicando una funzione hash; la posizione di memoria in cui vengono memorizzati questi record è nota come blocco dati o bucket di dati.
Perché abbiamo bisogno dell'hashing?
Ecco le situazioni in un DBMS in cui è necessario applicare il metodo di hashing:
- Nel caso di una struttura di database di grandi dimensioni, è difficile cercare tutti i valori dell'indice attraverso tutti i loro livelli e quindi raggiungere il blocco di dati di destinazione per ottenere i dati desiderati.
- L'hashing viene utilizzato per indicizzare e recuperare elementi in un database, perché è più veloce cercare un elemento specifico utilizzando la chiave hash più breve rispetto al valore originale.
- L'hashing è un metodo ideale per calcolare la posizione diretta di un record di dati sul disco senza utilizzare una struttura di indice.
- È anche una tecnica utile per implementare i dizionari.
Terminologie importanti nell'hashing
Ecco alcuni termini importanti utilizzati nell'hashing:
- Contenitore di dati: I bucket di dati sono posizioni di memoria in cui vengono archiviati i record. Sono anche noti come unità di archiviazione.
- Chiave: a Chiave DBMS è un attributo o un insieme di attributi che ti aiuta a identificare una riga (tupla) in una relazione (tabella).
- Funzione hash: una cartinaping funzione che associa l'intero set di chiavi di ricerca all'indirizzo in cui sono effettivamente memorizzati i record.
- Sondaggio lineare: un intervallo fisso tra le sonde. In questo metodo, il blocco di dati successivo disponibile viene utilizzato per inserire il nuovo record, anziché sovrascrivere il record precedente.
- Sondaggio quadratico: Aiuta a determinare il nuovo indirizzo del bucket aggiungendo l'output consecutivo di un polinomio quadratico al valore iniziale fornito dal calcolo originale.
- Indice hash: l'indirizzo del blocco di dati. Una funzione hash può essere una semplice funzione matematica o una complessa.
- Double Hashing: Un metodo utilizzato nelle tabelle hash per risolvere le collisioni applicando una seconda funzione hash.
- Trabocco del secchio: La condizione di overflow del bucket è chiamata collisione. Questa è una fase fatale per qualsiasi funzione hash statica.
Tipi di tecniche di hashing
Nei DBMS esistono principalmente due tipi di tecniche di hashing:
- Hashing statico
- Hashing dinamico
La differenza principale tra i due risiede nel fatto che il numero di bucket è fisso o meno, come spiegato nelle due sezioni successive.
Hashing statico
Nell'hashing statico, l'indirizzo del bucket di dati risultante rimarrà sempre lo stesso.
Pertanto, se generi un indirizzo per, ad esempio, ID_studente = 10 utilizzando la funzione di hashing mod(3), l'indirizzo del bucket risultante sarà sempre 1Pertanto, non vedrai alcun cambiamento nell'indirizzo del bucket.
Pertanto, nel metodo di hashing statico, il numero di bucket di dati in memoria rimane sempre costante.
Funzioni hash statiche
- Inserimento di un record: Quando è necessario inserire un nuovo record nella tabella, si genera un indirizzo per esso utilizzando la sua chiave hash. Una volta generato l'indirizzo, il record viene memorizzato in quella posizione.
- Ricerca: Quando è necessario recuperare il record, la stessa funzione hash viene utilizzata per recuperare l'indirizzo del bucket in cui sono archiviati i dati.
- Eliminare un record: Utilizzando la funzione hash, si recupera prima il record che si desidera eliminare, quindi si rimuove il record da quell'indirizzo di memoria.
L'hashing statico è ulteriormente suddiviso in:
- Hashing aperto
- Hashing chiuso
Apri Hashing
Nel metodo di hashing aperto, anziché sovrascrivere il record precedente, si utilizza il blocco di dati successivo disponibile per inserire il nuovo record. Questo metodo è anche noto come probing lineare.
Ad esempio, A2 è un nuovo record che si desidera inserire. La funzione hash genera l'indirizzo 222, ma questo è già occupato da un altro valore. Per questo motivo, il sistema cerca il successivo bucket di dati, il 501, e vi assegna A2.
Hashing chiuso
Nel metodo di hashing chiuso, quando i bucket sono pieni, viene assegnato un nuovo bucket per lo stesso hash e il risultato viene collegato al precedente.
Hashing dinamico
L'hashing dinamico offre un meccanismo in cui i bucket di dati vengono aggiunti e rimossi dinamicamente e su richiesta. In questo metodo di hashing, la funzione hash consente di creare un gran numero di valori e la struttura si espande o si riduce in base ai dati. Ciò lo rende particolarmente adatto per tabelle le cui dimensioni non possono essere previste in anticipo, dove l'hashing statico causerebbe uno spreco di spazio o un overflow.
Differenza tra indicizzazione ordinata e hashing
Di seguito sono riportate le principali differenze tra indicizzazione e hashing:
| Scheda Sintetica | Indicizzazione ordinata | hashing |
|---|---|---|
| Memorizzazione dell'indirizzo | Gli indirizzi in memoria sono ordinati in base a un valore chiave chiamato chiave primaria. | Gli indirizzi vengono sempre generati utilizzando una funzione hash sul valore della chiave. |
| Cookie di prestazione | Può diminuire all'aumentare dei dati, perché i dati vengono memorizzati ordinati e ogni inserimento, cancellazione o aggiornamento li riordina. | Le prestazioni sono ottimali con l'aggiunta e la cancellazione costante di dati. Per un database di grandi dimensioni, la manutenzione del file hash diventa più onerosa. |
| Utilizzare per | Preferito per il recupero di intervalli, dove i dati vengono recuperati per un intervallo specifico. | Ideale per recuperare un record specifico in base alla chiave di ricerca, e funziona bene solo quando la funzione hash è associata alla chiave di ricerca. |
| Gestione della memoria | Molti blocchi di dati inutilizzati derivano da operazioni di eliminazione e aggiornamento e non possono essere rilasciati per il riutilizzo, pertanto è necessaria una manutenzione regolare. | Nell'hashing statico e dinamico, la memoria viene sempre gestita e l'overflow del bucket viene gestito per estendere l'hashing statico. |
In breve, scegli ordinato indicizzazione per query di intervallo e hashing per ricerche di corrispondenza esatta sulla chiave.
Cos'è la collisione?
Una collisione di hash è uno stato in cui gli hash risultanti da due o più elementi nel set di dati vengono mappati erroneamente nello stesso punto nel tabella hash.
Come gestire una collisione di hashing
Esistono due tecniche che puoi utilizzare per evitare una collisione di hash:
- Rielaborare: Questo metodo invoca una funzione hash secondaria, che viene applicata continuamente finché non viene trovato uno spazio vuoto in cui inserire un record.
- Concatenamento: Il metodo di concatenamento crea una lista concatenata di elementi le cui chiavi hanno lo stesso valore hash. Questo metodo richiede un campo di collegamento aggiuntivo in ogni posizione della tabella.
