TechCodeview

Introduzione all'hashing nella struttura dei dati:

L'hashing è una tecnica popolare in informatica che prevede la mappatura di grandi set di dati su valori a lunghezza fissa. È un processo di conversione di un set di dati di dimensione variabile in un set di dati di dimensione fissa. La capacità di eseguire operazioni di ricerca efficienti rende l'hashing un concetto essenziale nelle strutture dati.

Cos'è l'hashing?

Un algoritmo di hashing viene utilizzato per convertire un input (come una stringa o un numero intero) in un output di dimensione fissa (denominato codice hash o valore hash). I dati vengono quindi archiviati e recuperati utilizzando questo valore hash come indice in un array o tabella hash. La funzione hash deve essere deterministica, il che garantisce che produrrà sempre lo stesso risultato per un dato input.

L'hashing viene comunemente utilizzato per creare un identificatore univoco per un dato, che può essere utilizzato per cercare rapidamente tali dati in un set di dati di grandi dimensioni. Ad esempio, un browser Web può utilizzare l'hashing per archiviare in modo sicuro le password dei siti Web. Quando un utente inserisce la propria password, il browser la converte in un valore hash e lo confronta con il valore hash memorizzato per autenticare l'utente.

Cos'è una chiave hash?

Nel contesto dell'hashing, una chiave hash (nota anche come valore hash o codice hash) è una rappresentazione numerica o alfanumerica di dimensione fissa generata da un algoritmo di hashing. Viene derivato dai dati di input, come una stringa di testo o un file, attraverso un processo noto come hashing.

L'hashing prevede l'applicazione di una funzione matematica specifica ai dati di input, che produce una chiave hash univoca che in genere è di lunghezza fissa, indipendentemente dalla dimensione dell'input. La chiave hash risultante è essenzialmente un'impronta digitale dei dati originali.

La chiave hash ha diversi scopi. Viene comunemente utilizzato per i controlli di integrità dei dati, poiché anche una piccola modifica nei dati di input produrrà una chiave hash significativamente diversa. Le chiavi hash vengono utilizzate anche per il recupero e l'archiviazione efficiente dei dati in tabelle hash o strutture dati, poiché consentono operazioni di ricerca e confronto rapide.

Come funziona l'hashing?

Il processo di hashing può essere suddiviso in tre fasi:

• Input: i dati da sottoporre ad hashing vengono immessi nell'algoritmo di hashing.
• Funzione hash: l'algoritmo di hashing prende i dati di input e applica una funzione matematica per generare un valore hash di dimensione fissa. La funzione hash dovrebbe essere progettata in modo tale che diversi valori di input producano diversi valori di hash e piccoli cambiamenti nell'input producano grandi cambiamenti nell'output.
• Output: viene restituito il valore hash, che viene utilizzato come indice per archiviare o recuperare dati in una struttura dati.

Algoritmi di hashing:

Esistono numerosi algoritmi di hashing, ciascuno con vantaggi e svantaggi distinti. Gli algoritmi più popolari includono quanto segue:

• MD5: un algoritmo di hashing ampiamente utilizzato che produce un valore hash a 128 bit.
• SHA-1: un popolare algoritmo di hashing che produce un valore hash a 160 bit.
• SHA-256: un algoritmo di hashing più sicuro che produce un valore hash a 256 bit.

Funzione hash:

Funzione hash: una funzione hash è un tipo di operazione matematica che accetta un input (o una chiave) e restituisce un risultato di dimensione fissa noto come codice hash o valore hash. La funzione hash deve sempre produrre lo stesso codice hash per lo stesso input per essere deterministica. Inoltre, la funzione hash dovrebbe produrre un codice hash univoco per ciascun input, noto come proprietà hash.

Esistono diversi tipi di funzioni hash, tra cui:

modelli di programmazione java

Metodo di divisione:

Questo metodo prevede la divisione della chiave per la dimensione della tabella e l'utilizzo del resto come valore hash. Ad esempio, se la dimensione della tabella è 10 e la chiave è 23, il valore hash sarà 3 (23% 10 = 3).

Metodo di moltiplicazione:

Questo metodo prevede di moltiplicare la chiave per una costante e prendere la parte frazionaria del prodotto come valore hash. Ad esempio, se la chiave è 23 e la costante è 0,618, il valore hash sarebbe 2 (floor(10*(0,61823 - floor(0,61823))) = floor(2,236) = 2).

Hashing universale:

Questo metodo prevede l'utilizzo di una funzione hash casuale da una famiglia di funzioni hash. Ciò garantisce che la funzione hash non sia influenzata da alcun input particolare e sia resistente agli attacchi.

Risoluzione delle collisioni

Una delle principali sfide nell'hashing è la gestione delle collisioni, che si verificano quando due o più valori di input producono lo stesso valore hash. Esistono varie tecniche utilizzate per risolvere le collisioni, tra cui:

• Concatenamento: in questa tecnica, ogni slot della tabella hash contiene un elenco collegato di tutti i valori che hanno lo stesso valore hash. Questa tecnica è semplice e facile da implementare, ma può portare a scarse prestazioni quando gli elenchi collegati diventano troppo lunghi.
• Indirizzamento aperto: in questa tecnica, quando si verifica una collisione, l'algoritmo cerca uno slot vuoto nella tabella hash esaminando gli slot successivi finché non viene trovato uno slot vuoto. Questa tecnica può essere più efficiente del concatenamento quando il fattore di carico è basso, ma può portare al clustering e a prestazioni scadenti quando il fattore di carico è elevato.
• Doppio hashing: si tratta di una variante dell'indirizzamento aperto che utilizza una seconda funzione hash per determinare lo slot successivo da sondare quando si verifica una collisione. Questa tecnica può aiutare a ridurre il clustering e migliorare le prestazioni.

Esempio di risoluzione delle collisioni

Continuiamo con il nostro esempio di una tabella hash con dimensione 5. Vogliamo memorizzare le coppie chiave-valore 'John: 123456' e 'Mary: 987654' nella tabella hash. Entrambe le chiavi producono lo stesso codice hash 4, quindi si verifica una collisione.

Possiamo usare il concatenamento per risolvere la collisione. Creiamo un elenco collegato all'indice 4 e aggiungiamo le coppie chiave-valore all'elenco. La tabella hash ora appare così:

0:

1:

2:

3:

4: Giovanni: 123456 -> Maria: 987654

5:

Tabella hash:

Una tabella hash è una struttura dati che memorizza i dati in un array. In genere, viene selezionata una dimensione per l'array maggiore del numero di elementi che possono essere contenuti nella tabella hash. Una chiave viene mappata a un indice nell'array utilizzando la funzione hash.

La funzione hash viene utilizzata per individuare l'indice in cui un elemento deve essere inserito nella tabella hash per aggiungere un nuovo elemento. L'elemento viene aggiunto a quell'indice se non c'è una collisione. Se c'è una collisione, viene utilizzato il metodo di risoluzione delle collisioni per trovare il successivo slot disponibile nell'array.

La funzione hash viene utilizzata per individuare l'indice in cui è memorizzato l'elemento per recuperarlo dalla tabella hash. Se l'elemento non viene trovato in quell'indice, il metodo di risoluzione delle collisioni viene utilizzato per cercare l'elemento nell'elenco collegato (se viene utilizzato il concatenamento) o nel successivo slot disponibile (se viene utilizzato l'indirizzamento aperto).

Operazioni sulle tabelle hash

Esistono diverse operazioni che possono essere eseguite su una tabella hash, tra cui:

• Inserimento: inserimento di una nuova coppia chiave-valore nella tabella hash.
• Eliminazione: rimozione di una coppia chiave-valore dalla tabella hash.
• Cerca: ricerca di una coppia chiave-valore nella tabella hash.

Creazione di una tabella hash:

L'hashing viene spesso utilizzato per creare tabelle hash, ovvero strutture di dati che consentono l'inserimento, l'eliminazione e il recupero rapidi dei dati. Una o più coppie chiave-valore possono essere archiviate in ciascuno degli array di bucket che compongono una tabella hash.

Per creare una tabella hash, dobbiamo prima definire una funzione hash che associa ciascuna chiave a un indice univoco nell'array. Una semplice funzione hash potrebbe essere quella di prendere la somma dei valori ASCII dei caratteri nella chiave e utilizzare il resto diviso per la dimensione dell'array. Tuttavia, questa funzione hash è inefficiente e può portare a collisioni (due chiavi mappate allo stesso indice).

Per evitare collisioni, possiamo utilizzare funzioni hash più avanzate che producono una distribuzione più uniforme dei valori hash nell'array. Un algoritmo popolare è la funzione hash djb2, che utilizza operazioni bit per bit per generare un valore hash:

 unsigned long hash(char* str) { unsigned long hash = 5381; int c; while (c = *str++) { hash = ((hash << 5) + hash) + c; } return hash; } 

Questa funzione hash accetta una stringa come input e restituisce un valore hash intero lungo senza segno. La funzione inizializza un valore hash pari a 5381 e quindi esegue un'iterazione su ogni carattere nella stringa, utilizzando operazioni bit a bit per generare un nuovo valore hash. Viene restituito il valore hash finale.

Tabelle hash in C++

In C++, la libreria standard fornisce una classe contenitore di tabelle hash chiamata unordered_map. Il contenitore unordered_map viene implementato utilizzando una tabella hash e fornisce un accesso rapido alle coppie chiave-valore. Il contenitore unordered_map utilizza una funzione hash per calcolare il codice hash delle chiavi e quindi utilizza l'indirizzamento aperto per risolvere le collisioni.

Per utilizzare il contenitore unordered_map in C++, è necessario includere il file di intestazione. Ecco un esempio di come creare un contenitore unordered_map in C++:

 #include #include int main() { // create an unordered_map container std::unordered_map my_map; // insert some key-value pairs into the map my_map['apple'] = 10; my_map['banana'] = 20; my_map['orange'] = 30; // print the value associated with the 'banana' key std::cout << my_map['banana'] << std::endl; return 0; } 

Spiegazione:

esempi di alberi binari

• Questo programma dimostra l'uso del contenitore unordered_map in C++, che viene implementato utilizzando una tabella hash e fornisce un accesso rapido alle coppie chiave-valore.
• Innanzitutto, il programma include i file di intestazione necessari: e.
• Quindi, il programma crea un contenitore vuoto unordered_map chiamato my_map, che ha chiavi stringa e valori interi. Questo viene fatto utilizzando la sintassi std::unordered_map my_map;
• Successivamente, il programma inserisce tre coppie chiave-valore nel contenitore my_map utilizzando l'operatore []: 'mela' con un valore pari a 10, 'banana' con un valore pari a 20 e 'arancione' con un valore pari a 30.
• Questo viene fatto utilizzando la sintassi my_map['apple'] = 10;, my_map['banana'] = 20; e my_map['orange'] = 30; rispettivamente.
• Infine, il programma stampa il valore associato alla chiave 'banana' utilizzando l'operatore [] e l'oggetto std::cout.

Uscita del programma:

Inserimento di dati in una tabella hash

Per inserire una coppia chiave-valore in una tabella hash, dobbiamo prima inserire un indice nell'array per memorizzare la coppia chiave-valore. Se un'altra chiave è associata allo stesso indice, si verifica una collisione e dobbiamo gestirla in modo appropriato. Un metodo comune consiste nell'utilizzare il concatenamento, in cui ciascun bucket nell'array contiene un elenco collegato di coppie chiave-valore che hanno lo stesso valore hash.

Ecco un esempio di come inserire una coppia chiave-valore in una tabella hash utilizzando il concatenamento:

 typedef struct node { char* key; int value; struct node* next; } node; node* hash_table[100]; void insert(char* key, int value) { unsigned long hash_value = hash(key) % 100; node* new_node = (node*) malloc(sizeof(node)); new_node->key = key; new_node->value = value; new_node->next = NULL; if (hash_table[hash_value] == NULL) { hash_table[hash_value] = new_node; } else { node* curr_node = hash_table[hash_value]; while (curr_node->next != NULL) { curr_node = curr_node->next; } curr_node->next = new_node; } } 

Spiegazione:

• Per prima cosa viene definita una struttura chiamata node, che rappresenta un singolo nodo nella tabella hash.
• Ogni nodo ha tre membri: una chiave char* per memorizzare la chiave, un valore int per memorizzare il valore associato e un puntatore a un altro nodo chiamato next per gestire le collisioni nella tabella hash utilizzando un elenco collegato.
• Viene dichiarato un array di puntatori al nodo chiamato hash_table con una dimensione di 100. Questo array verrà utilizzato per memorizzare gli elementi della tabella hash.
• La funzione di inserimento accetta una chiave char* e un valore int come parametri.
• Si inizia calcolando il valore hash per la chiave specificata utilizzando la funzione hash, che si presuppone sia definita altrove nel programma.
• Il valore hash viene quindi ridotto per rientrare nelle dimensioni dell'array hash_table utilizzando l'operatore modulo % 100.
• Un nuovo nodo viene creato utilizzando l'allocazione dinamica della memoria (malloc(sizeof(node))) e ai suoi membri (chiave, valore e successivo) vengono assegnati rispettivamente la chiave, il valore e NULL forniti.
• Se lo slot corrispondente nell'array hash_table è vuoto (NULL), indicando che non si è verificata alcuna collisione, il nuovo nodo viene assegnato direttamente a quello slot (hash_table[hash_value] = new_node).

Tuttavia, se è già presente un nodo su quell'indice nell'array hash_table, la funzione deve gestire la collisione. Attraversa la lista collegata partendo dal nodo corrente (hash_table[hash_value]) e si sposta al nodo successivo fino a raggiungere la fine (curr_node->next != NULL). Una volta raggiunta la fine dell'elenco, il nuovo nodo viene aggiunto come nodo successivo (curr_node->next = new_node).

Implementazione dell'hashing in C++:

Vediamo un'implementazione dell'hashing in C++ utilizzando l'indirizzamento aperto e il sondaggio lineare per la risoluzione delle collisioni. Implementeremo una tabella hash che memorizza i numeri interi.

 #include using namespace std; const int SIZE = 10; class HashTable { private: int arr[SIZE]; public: HashTable() { for (int i = 0; i <size; i++) { arr[i]="-1;" } int hashfunction(int key) return key % size; void insert(int index="hashFunction(key);" i="0;" while (arr[(index + i) size] !="-1" && arr[(index i++; if cout << 'element already exists in the hash table' endl; else remove(int deleted from return; not found display() for (int < (arr[i]="=" -1 || -2) continue; 'index ' ': }; main() hashtable ht; ht.insert(5); ht.insert(15); ht.insert(25); ht.insert(35); ht.insert(45); ht.display(); ht.remove(15); ht.remove(10); ht.insert(55); 0; pre> <p> <strong>Explanation:</strong> </p> <ul> <li>This program implements a hash table data structure using linear probing to handle collisions.</li> <li>A hash table is a data structure that stores data in key-value pairs, where the keys are hashed using a hash function to generate an index in an array. This allows for constant-time average-case complexity for inserting, searching, and deleting elements from the hash table.</li> <li>The HashTable class has a private integer array arr of size SIZE, which is initialized to -1 in the constructor. The hash function method takes an integer key and returns the hash value of the key, which is simply the remainder of the key when divided by SIZE.</li> <li>The insert method takes an integer key and uses the hash function to get the index where the key should be inserted.</li> <li>If the index is already occupied by another key, linear probing is used to find the next available index in the array. Linear probing checks the next index in the array until it finds an empty slot or the key itself.</li> <li>If the key is already in the hash table, the method displays a message saying that the element already exists. Otherwise, it inserts the key at the calculated index.</li> <li>The remove method takes an integer key and uses the hash function to get the index where the key is located.</li> <li>If the key is not in the calculated index, linear probing is used to search for the key in the next indices in the array. Once the key is found, it is deleted by setting its value to -2.</li> <li>If the key is not found in the hash table, the method displays a message saying that the element is not found.</li> <li>The display method simply iterates through the array and prints out all non-empty key-value pairs.</li> <li>In the main function, an instance of the HashTable class is created, and several integers are inserted into the hash table using the insert method.</li> <li>Then, the display method is called to show the contents of the hash table. The remove method is called twice, first to remove an element that exists in the hash table and then to remove an element that does not exist.</li> <li>The display method is called after each remove method call to show the updated contents of the hash table.</li> <li>Finally, another integer is inserted into the hash table, and the display method is called again to show the final contents of the hash table.</li> </ul> <p> <strong>Program Output:</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/65/hashing-data-structure-3.webp" alt="Hashing in Data Structure"> <h2>Applications of Hashing</h2> <p>Hashing has many applications in computer science, including:</p> <ul> <li>Databases: Hashing is used to index and search large databases efficiently.</li> <li>Cryptography: Hash functions are used to generate message digests, which are used to verify the integrity of data and protect against tampering.</li> <li>Caching: Hash tables are used in caching systems to store frequently accessed data and improve performance.</li> <li>Spell checking: Hashing is used in spell checkers to quickly search for words in a dictionary.</li> <li>Network routing: Hashing is used in load balancing and routing algorithms to distribute network traffic across multiple servers.</li> </ul> <h2>Advantages of Hashing:</h2> <ul> <li>Fast Access: Hashing provides constant time access to data, making it faster than other data structures like linked lists and arrays.</li> <li>Efficient Search: Hashing allows for quick search operations, making it an ideal data structure for applications that require frequent search operations.</li> <li>Space-Efficient: Hashing can be more space-efficient than other data structures, as it only requires a fixed amount of memory to store the hash table.</li> </ul> <h2>Limitations of Hashing:</h2> <ul> <li>Hash Collisions: Hashing can produce the same hash value for different keys, leading to hash collisions. To handle collisions, we need to use collision resolution techniques like chaining or open addressing.</li> <li>Hash Function Quality: The quality of the hash function determines the efficiency of the hashing algorithm. A poor-quality hash function can lead to more collisions, reducing the performance of the hashing algorithm.</li> </ul> <h2>Conclusion:</h2> <p>In conclusion, hashing is a widely used technique in a data structure that provides efficient access to data. It involves mapping a large amount of data to a smaller hash table using a hash function, which reduces the amount of time needed to search for specific data elements. The hash function ensures that data is stored in a unique location within the hash table and allows for easy retrieval of data when needed.</p> <p>Hashing has several advantages over other data structure techniques, such as faster retrieval times, efficient use of memory, and reduced collisions due to the use of a good hash function. However, it also has some limitations, including the possibility of hash collisions and the need for a good hash function that can distribute data evenly across the hash table.</p> <p>Overall, hashing is a powerful technique that is used in many applications, including database indexing, spell-checking, and password storage. By using a good hash function and implementing appropriate collision resolution techniques, developers can optimize the performance of their applications and provide users with a seamless experience.</p> <hr></size;>