Introduzione alla funzione hash in C
Questo articolo contiene una breve nota sull'hash (tabella hash e funzione hash). Il concetto più importante è la "ricerca" che determina la complessità temporale. Per ridurre la complessità temporale rispetto a qualsiasi altra struttura di dati, viene introdotto il concetto di hashing che ha tempo O (1) nel caso medio e nel caso peggiore impiegherà O (n) tempo.
L'hashing è una tecnica con accesso più rapido agli elementi che mappa i dati dati con una chiave minore per i confronti. In generale, in questa tecnica, i tasti vengono tracciati utilizzando la funzione hash in una tabella nota come tabella hash.
Cos'è la funzione hash?
La funzione hash è una funzione che utilizza l'operazione a tempo costante per archiviare e recuperare il valore dalla tabella hash, che viene applicato sulle chiavi come numeri interi e utilizzato come indirizzo per i valori nella tabella hash.
Tipi di una funzione hash
I tipi di funzioni hash sono spiegati di seguito:
1. Metodo di divisione
In questo metodo, la funzione hash dipende dal resto di una divisione.
Esempio: gli elementi da inserire in una tabella hash sono 42, 78, 89, 64 e prendiamo la dimensione della tabella come 10.
Hash (chiave) = dimensione tabella% elementi;
2 = 42% 10;
8 = 78% 10;
9 = 89% 10;
4 = 64% 10;
La rappresentazione della tabella può essere vista come di seguito:
2. Metodo del quadrato centrale
In questo metodo, la parte centrale dell'elemento quadrato viene considerata come indice.
Gli elementi da posizionare nella tabella hash sono 210, 350, 99, 890 e le dimensioni della tabella sono 100.
210 * 210 = 44100, indice = 1 come parte centrale del risultato (44100) è 1.
350 * 350 = 122500, indice = 25 come parte centrale del risultato (122500) è 25.
99 * 99 = 9801, indice = 80 come la parte centrale del risultato (9801) è 80.
890 * 890 = 792100, indice = 21 come la parte centrale del risultato (792100) è 21.
3. Metodo di piegatura delle cifre
In questo metodo l'elemento da posizionare nella tabella è sing hash key, che si ottiene dividendo gli elementi in varie parti e quindi combinando le parti eseguendo alcune semplici operazioni matematiche.
Gli elementi da posizionare sono 23576623, 34687734.
- hash (chiave) = 235 + 766 + 23 = 1024
- tasto cancelletto) = 34 + 68 + 77 + 34 = 213
In questi tipi di hash supponiamo di avere numeri da 1 a 100 e dimensioni della tabella hash = 10. Elementi = 23, 12, 32
Hash (chiave) = 23% 10 = 3;
Hash (chiave) = 12% 10 = 2;
Hash (chiave) = 32% 10 = 2;
Dall'esempio precedente si noti che entrambi gli elementi 12 e 32 indicano il 2 ° posto nella tabella, dove non è possibile scrivere entrambi nello stesso punto, tale problema è noto come una collisione. Per evitare questo tipo di problemi ci sono alcune tecniche di funzioni hash che possono essere utilizzate.
Tipi di tecniche di risoluzione delle collisioni
Discutiamo i tipi di tecniche di risoluzione delle collisioni:
1. Concatenamento
In questo metodo, come suggerisce il nome, fornisce una catena di caselle per il record nella tabella con due voci di elementi. Pertanto, ogni volta che si verificano tali collisioni, le caselle fungono da elenco collegato.
Esempio: 23, 12, 32 con dimensioni della tabella 10.
Hash (chiave) = 23% 10 = 3;
Hash (chiave) = 12% 10 = 2;
Hash (chiave) = 32% 10 = 2;
2. Apri Indirizzamento
- Analisi lineare
Questo è un altro metodo per risolvere i problemi di collisione. Come dice il nome ogni volta che si verifica una collisione, due elementi devono essere posizionati sulla stessa voce nella tabella, ma con questo metodo, possiamo cercare il prossimo spazio vuoto o voce nella tabella e posizionare il secondo elemento. Questo può di nuovo portare a un altro problema; se non troviamo alcuna voce vuota nella tabella, ciò porta al clustering. Quindi questo è noto come un problema di clustering, che può essere risolto con il seguente metodo.
Esempio: 23, 12, 32 con dimensioni della tabella 10
Hash (chiave) = 23% 10 = 3;
Hash (chiave) = 12% 10 = 2;
Hash (chiave) = 32% 10 = 2;
In questo diagramma 12 e 32 possono essere inseriti nella stessa voce con l'indice 2 ma con questo metodo vengono posizionati in modo lineare.
- Sondaggio quadratico
Questo metodo è una risoluzione per il problema del clustering durante il sondaggio lineare. In questo metodo la funzione hash con chiave hash viene calcolata come hash (chiave) = (hash (chiave) + x * x)% della dimensione della tabella (dove x = 0, 1, 2 …).
Esempio: 23, 12, 32 con dimensioni della tabella 10
Hash (chiave) = 23% 10 = 3;
Hash (chiave) = 12% 10 = 2;
Hash (chiave) = 32% 10 = 2;
In questo, possiamo vedere che 23 e 12 possono essere posizionati facilmente ma 32 non possono ancora 12 e 32 condividere la stessa voce con lo stesso indice nella tabella, come per questo metodo hash (chiave) = (32 + 1 * 1) % 10 = 3. Ma in questo caso la voce di tabella con l'indice 3 viene posizionata con 23, quindi dobbiamo incrementare il valore x di 1. Hash (chiave) = (32 + 2 * 2)% 10 = 6. Quindi ora possiamo posizionare 32 nella voce con indice 6 nella tabella.
- Doppio hashing
Questo metodo dobbiamo calcolare 2 funzioni hash per risolvere il problema di collisione. Il primo viene calcolato utilizzando un metodo di divisione semplice. Il secondo deve soddisfare due regole; non deve essere uguale a 0 e le voci devono essere sondate.
- 1 (chiave) = chiave% dimensione della tabella.
- 2 (chiave) = p - (chiave mod p), dove p è numeri primi <dimensione della tabella.
Esempio: 23, 12, 32 con dimensioni della tabella 10
Hash (chiave) = 23% 10 = 3;
Hash (chiave) = 12% 10 = 2;
Hash (chiave) = 32% 10 = 2;
Anche in questo caso l'elemento 32 può essere posizionato usando hash2 (chiave) = 5 - (32% 5) = 3. Quindi 32 possono essere posizionati all'indice 5 nella tabella che è vuota in quanto dobbiamo saltare 3 voci per posizionarlo.
Conclusione-Hashing in C
L'hashing è una delle tecniche più importanti in termini di ricerca di dati forniti con metodi molto efficienti e rapidi usando la funzione hash e le tabelle hash. Ogni elemento può essere cercato e posizionato utilizzando diversi metodi di hashing. Questa tecnica è molto più veloce di qualsiasi altra struttura di dati in termini di coefficiente di tempo.
Articoli consigliati
Questa è una guida alla funzione Hashing in C. Qui discutiamo dell'introduzione della funzione Hashing in C, Cos'è la funzione Hash, Tipi di una funzione hash, ecc. Puoi anche consultare i nostri altri articoli suggeriti per saperne di più–
- Hashing nel DBMS
- Processo di crittografia
- Come installare CakePHP?
- Come funziona Blockchain
- Funzione hash in Java
- Funzione di hashing in PHP | Come lavorare?