TechCodeview

Introducció al hashing a l'estructura de dades:

El hashing és una tècnica popular en informàtica que consisteix a mapar grans conjunts de dades amb valors de longitud fixa. És un procés de conversió d'un conjunt de dades de mida variable en un conjunt de dades de mida fixa. La capacitat de realitzar operacions de cerca eficients fa que el hashing sigui un concepte essencial en les estructures de dades.

Què és Hashing?

Un algorisme hash s'utilitza per convertir una entrada (com una cadena o un nombre enter) en una sortida de mida fixa (anomenada codi hash o valor hash). Les dades s'emmagatzemen i es recuperen utilitzant aquest valor hash com a índex en una matriu o taula hash. La funció hash ha de ser determinista, la qual cosa garanteix que sempre donarà el mateix resultat per a una entrada determinada.

El hashing s'utilitza habitualment per crear un identificador únic per a una peça de dades, que es pot utilitzar per cercar ràpidament aquestes dades en un conjunt de dades gran. Per exemple, un navegador web pot utilitzar hashing per emmagatzemar les contrasenyes dels llocs web de manera segura. Quan un usuari introdueix la seva contrasenya, el navegador la converteix en un valor hash i el compara amb el valor hash emmagatzemat per autenticar l'usuari.

Què és una clau hash?

En el context del hash, una clau hash (també coneguda com a valor hash o codi hash) és una representació numèrica o alfanumèrica de mida fixa generada per un algorisme hash. Es deriva de les dades d'entrada, com ara una cadena de text o un fitxer, mitjançant un procés conegut com hashing.

llistat de java

Hash implica aplicar una funció matemàtica específica a les dades d'entrada, que produeix una clau hash única que normalment té una longitud fixa, independentment de la mida de l'entrada. La clau hash resultant és essencialment una empremta digital de les dades originals.

La clau hash té diversos propòsits. S'utilitza habitualment per a comprovacions d'integritat de dades, ja que fins i tot un petit canvi en les dades d'entrada produirà una clau hash significativament diferent. Les claus hash també s'utilitzen per a la recuperació i l'emmagatzematge de dades eficients en taules hash o estructures de dades, ja que permeten operacions de cerca i comparació ràpides.

Com funciona l'hashing?

El procés de hash es pot dividir en tres passos:

• Entrada: les dades que s'han de calcular s'introdueixen a l'algoritme de resum.
• Funció hash: l'algoritme hash pren les dades d'entrada i aplica una funció matemàtica per generar un valor hash de mida fixa. La funció hash s'ha de dissenyar de manera que diferents valors d'entrada produeixin diferents valors hash, i petits canvis en l'entrada produeixin grans canvis en la sortida.
• Sortida: es retorna el valor hash, que s'utilitza com a índex per emmagatzemar o recuperar dades en una estructura de dades.

Algoritmes hashing:

Hi ha nombrosos algorismes de hash, cadascun amb diferents avantatges i desavantatges. Els algorismes més populars inclouen els següents:

• MD5: un algorisme hash àmpliament utilitzat que produeix un valor hash de 128 bits.
• SHA-1: un algorisme de hash popular que produeix un valor hash de 160 bits.
• SHA-256: un algorisme hash més segur que produeix un valor hash de 256 bits.

Funció hash:

Funció hash: una funció hash és un tipus d'operació matemàtica que pren una entrada (o clau) i produeix un resultat de mida fixa conegut com a codi hash o valor hash. La funció hash sempre ha de produir el mateix codi hash per a la mateixa entrada per tal de ser determinista. A més, la funció hash hauria de produir un codi hash únic per a cada entrada, que es coneix com a propietat hash.

Hi ha diferents tipus de funcions hash, com ara:

rdbms

Mètode de divisió:

Aquest mètode consisteix a dividir la clau per la mida de la taula i prendre la resta com a valor hash. Per exemple, si la mida de la taula és 10 i la clau és 23, el valor hash seria 3 (23 % 10 = 3).

Mètode de multiplicació:

Aquest mètode consisteix a multiplicar la clau per una constant i prendre la part fraccionària del producte com a valor hash. Per exemple, si la clau és 23 i la constant és 0,618, el valor hash seria 2 (floor(10*(0,61823 - floor(0,61823))) = floor(2,236) = 2).

Hashing universal:

Aquest mètode implica utilitzar una funció hash aleatòria d'una família de funcions hash. Això garanteix que la funció hash no estigui esbiaixada cap a cap entrada en particular i sigui resistent als atacs.

Resolució de col·lisions

Un dels principals reptes del hash és gestionar les col·lisions, que es produeixen quan dos o més valors d'entrada produeixen el mateix valor hash. Hi ha diverses tècniques utilitzades per resoldre col·lisions, com ara:

• Encadenament: en aquesta tècnica, cada ranura de taula hash conté una llista enllaçada de tots els valors que tenen el mateix valor hash. Aquesta tècnica és senzilla i fàcil d'implementar, però pot provocar un rendiment baix quan les llistes enllaçades es fan massa llargues.
• Adreçament obert: en aquesta tècnica, quan es produeix una col·lisió, l'algoritme cerca una ranura buida a la taula hash sondejant ranures successives fins que es troba una ranura buida. Aquesta tècnica pot ser més eficient que l'encadenament quan el factor de càrrega és baix, però pot provocar agrupacions i un rendiment baix quan el factor de càrrega és alt.
• Doble hash: aquesta és una variació de l'adreçament obert que utilitza una segona funció hash per determinar la següent ranura a sondar quan es produeix una col·lisió. Aquesta tècnica pot ajudar a reduir la agrupació i millorar el rendiment.

Exemple de resolució de col·lisions

Continuem amb el nostre exemple de taula hash amb una mida de 5. Volem emmagatzemar els parells clau-valor 'John: 123456' i 'Mary: 987654' a la taula hash. Les dues claus produeixen el mateix codi hash de 4, de manera que es produeix una col·lisió.

Podem utilitzar l'encadenament per resoldre la col·lisió. Creem una llista enllaçada a l'índex 4 i afegim els parells clau-valor a la llista. La taula hash ara té aquest aspecte:

0:

1:

numpy meshgrid

2:

3:

4: Joan: 123456 -> Maria: 987654

5:

Taula hash:

Una taula hash és una estructura de dades que emmagatzema dades en una matriu. Normalment, se selecciona una mida per a la matriu que és superior al nombre d'elements que poden cabre a la taula hash. Una clau s'assigna a un índex de la matriu mitjançant la funció hash.

La funció hash s'utilitza per localitzar l'índex on cal inserir un element a la taula hash per afegir un nou element. L'element s'afegeix a aquest índex si no hi ha cap col·lisió. Si hi ha una col·lisió, s'utilitza el mètode de resolució de col·lisions per trobar el següent espai disponible a la matriu.

iterant un mapa en java

La funció hash s'utilitza per localitzar l'índex que s'emmagatzema l'element per tal de recuperar-lo de la taula hash. Si l'element no es troba en aquest índex, s'utilitza el mètode de resolució de col·lisions per cercar l'element a la llista enllaçada (si s'utilitza l'encadenament) o a la següent ranura disponible (si s'utilitza l'adreçament obert).

Operacions de taula hash

Hi ha diverses operacions que es poden realitzar en una taula hash, com ara:

• Inserció: inserció d'un parell clau-valor nou a la taula hash.
• Supressió: eliminació d'un parell clau-valor de la taula hash.
• Cerca: cerca d'un parell clau-valor a la taula hash.

Creació d'una taula hash:

El hash s'utilitza sovint per crear taules hash, que són estructures de dades que permeten la inserció, la supressió i la recuperació ràpides de dades. Es poden emmagatzemar un o més parells clau-valor a cadascuna de les matrius de dipòsits que formen una taula hash.

Per crear una taula hash, primer hem de definir una funció hash que assigni cada clau a un índex únic de la matriu. Una funció hash senzilla podria ser prendre la suma dels valors ASCII dels caràcters de la clau i utilitzar la resta quan es divideix per la mida de la matriu. Tanmateix, aquesta funció hash és ineficient i pot provocar col·lisions (dues claus que s'assignen al mateix índex).

Per evitar col·lisions, podem utilitzar funcions hash més avançades que produeixen una distribució més uniforme dels valors hash a través de la matriu. Un algorisme popular és la funció hash djb2, que utilitza operacions bit a bit per generar un valor hash:

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

Aquesta funció hash pren una cadena com a entrada i retorna un valor hash d'enter llarg sense signe. La funció inicialitza un valor hash de 5381 i després itera sobre cada caràcter de la cadena, utilitzant operacions bit a bit per generar un nou valor hash. Es retorna el valor hash final.

llocs com coomeet

Taules hash en C++

En C++, la biblioteca estàndard proporciona una classe de contenidor de taula hash anomenada unordered_map. El contenidor unordered_map s'implementa mitjançant una taula hash i proporciona un accés ràpid als parells clau-valor. El contenidor unordered_map utilitza una funció hash per calcular el codi hash de les claus i després utilitza l'adreçament obert per resoldre les col·lisions.

Per utilitzar el contenidor unordered_map en C++, heu d'incloure el fitxer de capçalera. Aquí teniu un exemple de com crear un contenidor de mapa_desordenat en 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; } 

Explicació:

• Aquest programa demostra l'ús del contenidor unordered_map en C++, que s'implementa mitjançant una taula hash i proporciona un accés ràpid als parells clau-valor.
• En primer lloc, el programa inclou els fitxers de capçalera necessaris: i.
• Aleshores, el programa crea un contenidor de mapa_desordenat buit anomenat my_map, que té claus de cadena i valors enters. Això es fa utilitzant la sintaxi std::unordered_map my_map;
• A continuació, el programa insereix tres parells clau-valor al contenidor my_map mitjançant l'operador []: 'apple' amb un valor de 10, 'banana' amb un valor de 20 i 'taronja' amb un valor de 30.
• Això es fa utilitzant la sintaxi my_map['apple'] = 10;, my_map['banana'] = 20; i my_map['orange'] = 30; respectivament.
• Finalment, el programa imprimeix el valor associat a la clau 'banana' mitjançant l'operador [] i l'objecte std::cout.

Sortida del programa:

Inserció de dades en una taula hash

Per inserir un parell clau-valor en una taula hash, primer hem de crear un índex a la matriu per emmagatzemar el parell clau-valor. Si una altra clau s'assigna al mateix índex, tenim una col·lisió i hem de gestionar-la adequadament. Un mètode comú és utilitzar l'encadenament, on cada cub de la matriu conté una llista enllaçada de parells clau-valor que tenen el mateix valor hash.

Aquí teniu un exemple de com inserir un parell clau-valor en una taula hash mitjançant l'encadenament:

 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; } } 

Explicació:

• En primer lloc, es defineix una estructura anomenada node, que representa un sol node a la taula hash.
• Cada node té tres membres: una clau char* per emmagatzemar la clau, un valor int per emmagatzemar el valor associat i un punter a un altre node anomenat al costat per gestionar les col·lisions a la taula hash mitjançant una llista enllaçada.
• Es declara una matriu de punters de node anomenada hash_table amb una mida de 100. Aquesta matriu s'utilitzarà per emmagatzemar els elements de la taula hash.
• La funció d'inserció pren com a paràmetres una clau char* i un valor int.
• Comença calculant el valor hash per a la clau donada mitjançant la funció hash, que se suposa que es defineix en qualsevol altre lloc del programa.
• Aleshores, el valor hash es redueix per adaptar-se a la mida de la matriu hash_table mitjançant l'operador mòdul % 100.
• Es crea un nou node mitjançant l'assignació de memòria dinàmica (malloc(sizeof(node))) i els seus membres (clau, valor i següent) s'assignen amb la clau, el valor i NULL proporcionats, respectivament.
• Si la ranura corresponent a la matriu hash_table està buida (NULL), cosa que indica que no s'ha produït cap col·lisió, el nou node s'assigna directament a aquesta ranura (hash_table[hash_value] = new_node).

Tanmateix, si ja hi ha un node present en aquest índex a la matriu hash_table, la funció ha de gestionar la col·lisió. Travessa la llista enllaçada començant des del node actual (hash_table[hash_value]) i es mou al següent node fins que arriba al final (curr_node->next != NULL). Un cop arribat al final de la llista, el nou node s'afegeix com a següent node (curr_node->next = new_node).

Implementació de hashing en C++:

Vegem una implementació de hash en C++ mitjançant l'adreçament obert i el sondeig lineal per a la resolució de col·lisions. Implementarem una taula hash que emmagatzema nombres enters.

 #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;>