HASHING ÎN STRUCTURA DATELOR

Introducere în hashing în structura datelor:

Hashing-ul este o tehnică populară în informatică care implică maparea unor seturi mari de date la valori cu lungime fixă. Este un proces de conversie a unui set de date de dimensiune variabilă într-un set de date de dimensiune fixă. Capacitatea de a efectua operațiuni eficiente de căutare face ca hashingul să fie un concept esențial în structurile de date.

Ce este Hashing?

Un algoritm de hashing este utilizat pentru a converti o intrare (cum ar fi un șir sau un întreg) într-o ieșire de dimensiune fixă (denumită cod hash sau valoare hash). Datele sunt apoi stocate și preluate folosind această valoare hash ca index într-o matrice sau tabel hash. Funcția hash trebuie să fie deterministă, ceea ce garantează că va produce întotdeauna același rezultat pentru o intrare dată.

Hashingul este folosit în mod obișnuit pentru a crea un identificator unic pentru o bucată de date, care poate fi folosit pentru a căuta rapid acele date într-un set de date mare. De exemplu, un browser web poate folosi hashing pentru a stoca în siguranță parolele site-ului web. Când un utilizator își introduce parola, browserul o convertește într-o valoare hash și o compară cu valoarea hash stocată pentru a autentifica utilizatorul.

Ce este o cheie hash?

În contextul hash-ului, o cheie hash (cunoscută și ca valoare hash sau cod hash) este o reprezentare numerică sau alfanumerică de dimensiune fixă generată de un algoritm de hash. Este derivat din datele de intrare, cum ar fi un șir de text sau un fișier, printr-un proces cunoscut sub numele de hashing.

Hashing implică aplicarea unei anumite funcții matematice datelor de intrare, care produce o cheie hash unică, care este de obicei de lungime fixă, indiferent de dimensiunea intrării. Cheia hash rezultată este în esență o amprentă digitală a datelor originale.

Tasta hash servește mai multor scopuri. Este folosit în mod obișnuit pentru verificările integrității datelor, deoarece chiar și o mică modificare a datelor de intrare va produce o cheie hash semnificativ diferită. Cheile hash sunt, de asemenea, folosite pentru recuperarea și stocarea eficientă a datelor în tabele hash sau structuri de date, deoarece permit operațiuni rapide de căutare și comparare.

Cum funcționează hashingul?

Procesul de hashing poate fi împărțit în trei etape:

Intrare: datele care urmează să fie analizate prin hashing sunt introduse în algoritmul de hashing.
Funcția hash: algoritmul hash preia datele de intrare și aplică o funcție matematică pentru a genera o valoare hash de dimensiune fixă. Funcția hash ar trebui să fie proiectată astfel încât valorile de intrare diferite să producă valori hash diferite, iar modificările mici ale intrării produc modificări mari în ieșire.
Ieșire: este returnată valoarea hash, care este utilizată ca index pentru a stoca sau a prelua date într-o structură de date.

Algoritmi de hashing:

Există numeroși algoritmi de hashing, fiecare cu avantaje și dezavantaje distincte. Cei mai populari algoritmi includ următorii:

MD5: Un algoritm de hashing utilizat pe scară largă care produce o valoare hash de 128 de biți.
SHA-1: Un algoritm de hashing popular care produce o valoare hash de 160 de biți.
SHA-256: Un algoritm de hashing mai sigur care produce o valoare hash de 256 de biți.

Funcția Hash:

Funcția hash: o funcție hash este un tip de operație matematică care ia o intrare (sau cheie) și emite un rezultat de dimensiune fixă cunoscut sub numele de cod hash sau valoare hash. Funcția hash trebuie să producă întotdeauna același cod hash pentru aceeași intrare pentru a fi deterministă. În plus, funcția hash ar trebui să producă un cod hash unic pentru fiecare intrare, care este cunoscut sub numele de proprietate hash.

Există diferite tipuri de funcții hash, inclusiv:

Metoda de împărțire:

Această metodă implică împărțirea cheii la dimensiunea tabelului și luarea restului ca valoare hash. De exemplu, dacă dimensiunea tabelului este 10 și cheia este 23, valoarea hash ar fi 3 (23 % 10 = 3).

Metoda de înmulțire:

Această metodă implică înmulțirea cheii cu o constantă și luarea părții fracționale a produsului ca valoare hash. De exemplu, dacă cheia este 23 și constanta este 0,618, valoarea hash ar fi 2 (floor(10*(0.61823 - floor(0.61823))) = floor(2.236) = 2).

Hashing universal:

Această metodă implică utilizarea unei funcții hash aleatoare dintr-o familie de funcții hash. Acest lucru asigură că funcția de hash nu este orientată către nicio intrare anume și este rezistentă la atacuri.

Rezolvarea coliziunilor

Una dintre principalele provocări în hashing este gestionarea coliziunilor, care apar atunci când două sau mai multe valori de intrare produc aceeași valoare hash. Există diferite tehnici utilizate pentru a rezolva coliziunile, inclusiv:

Înlănțuire: în această tehnică, fiecare slot de tabel hash conține o listă legată de toate valorile care au aceeași valoare hash. Această tehnică este simplă și ușor de implementat, dar poate duce la performanțe slabe atunci când listele legate devin prea lungi.
Adresare deschisă: în această tehnică, atunci când are loc o coliziune, algoritmul caută un slot gol în tabelul hash prin sondarea sloturilor succesive până când este găsit un slot gol. Această tehnică poate fi mai eficientă decât înlănțuirea atunci când factorul de sarcină este scăzut, dar poate duce la grupare și performanță slabă atunci când factorul de sarcină este mare.
Hashing dublu: aceasta este o variație a adresei deschise care utilizează o a doua funcție hash pentru a determina următorul slot de sondat atunci când are loc o coliziune. Această tehnică poate ajuta la reducerea grupării și la îmbunătățirea performanței.

Exemplu de rezoluție a coliziunilor

Să continuăm cu exemplul nostru de tabel hash cu dimensiunea de 5. Dorim să stocăm perechile cheie-valoare „John: 123456” și „Mary: 987654” în tabelul hash. Ambele taste produc același cod hash de 4, așa că are loc o coliziune.

Putem folosi înlănțuirea pentru a rezolva coliziunea. Creăm o listă legată la indexul 4 și adăugăm perechile cheie-valoare la listă. Tabelul hash arată acum astfel:

4: Ioan: 123456 -> Maria: 987654

Tabel Hash:

Un tabel hash este o structură de date care stochează date într-o matrice. De obicei, este selectată o dimensiune pentru matrice care este mai mare decât numărul de elemente care pot încadra în tabelul hash. O cheie este mapată la un index din matrice folosind funcția hash.

Funcția hash este folosită pentru a localiza indexul în care un element trebuie să fie inserat în tabelul hash pentru a adăuga un nou element. Elementul este adăugat la acel index dacă nu există o coliziune. Dacă există o coliziune, metoda de rezoluție a coliziunii este utilizată pentru a găsi următorul slot disponibil din matrice.

Funcția hash este folosită pentru a localiza indexul pe care este stocat elementul pentru a-l prelua din tabelul hash. Dacă elementul nu este găsit la acel index, metoda de rezoluție a coliziunilor este utilizată pentru a căuta elementul în lista legată (dacă se folosește înlănțuirea) sau în următorul slot disponibil (dacă se utilizează adresarea deschisă).

Operații cu tabelul hash

Există mai multe operații care pot fi efectuate pe o tabelă hash, inclusiv:

Inserare: inserarea unei noi perechi cheie-valoare în tabelul hash.
Ștergere: eliminarea unei perechi cheie-valoare din tabelul hash.
Căutare: căutarea unei perechi cheie-valoare în tabelul hash.

Crearea unui tabel Hash:

Hashingul este frecvent utilizat pentru a construi tabele hash, care sunt structuri de date care permit inserarea, ștergerea și preluarea rapidă a datelor. Una sau mai multe perechi cheie-valoare pot fi stocate în fiecare dintre matricele de compartimente care alcătuiesc un tabel hash.

Pentru a crea un tabel hash, trebuie mai întâi să definim o funcție hash care mapează fiecare cheie la un index unic din matrice. O funcție hash simplă ar putea fi să luați suma valorilor ASCII ale caracterelor din cheie și să utilizați restul atunci când este împărțit la dimensiunea matricei. Cu toate acestea, această funcție hash este ineficientă și poate duce la coliziuni (două chei care se mapează la același index).

Pentru a evita coliziunile, putem folosi funcții hash mai avansate care produc o distribuție mai uniformă a valorilor hash în cadrul matricei. Un algoritm popular este funcția hash djb2, care utilizează operații pe biți pentru a genera o valoare hash:

modele de programare java

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

Această funcție hash ia un șir de caractere ca intrare și returnează o valoare hash cu un întreg lung fără semn. Funcția inițializează o valoare hash de 5381 și apoi iterează peste fiecare caracter din șir, folosind operații pe biți pentru a genera o nouă valoare hash. Valoarea hash finală este returnată.

Tabele Hash în C++

În C++, biblioteca standard oferă o clasă de container de tabel hash numită unordered_map. Containerul unordered_map este implementat folosind un tabel hash și oferă acces rapid la perechile cheie-valoare. Containerul unordered_map folosește o funcție hash pentru a calcula codul hash al cheilor și apoi folosește adresarea deschisă pentru a rezolva coliziunile.

Pentru a utiliza containerul unordered_map în C++, trebuie să includeți fișierul antet. Iată un exemplu despre cum să creați un container neordonat_map în 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[&apos;apple&apos;] = 10; my_map[&apos;banana&apos;] = 20; my_map[&apos;orange&apos;] = 30; // print the value associated with the &apos;banana&apos; key std::cout &lt;&lt; my_map[&apos;banana&apos;] &lt;&lt; std::endl; return 0; }

Explicaţie:

Acest program demonstrează utilizarea containerului unordered_map în C++, care este implementat folosind un tabel hash și oferă acces rapid la perechile cheie-valoare.
În primul rând, programul include fișierele de antet necesare: și.
Apoi, programul creează un container neordonat_map gol numit my_map, care are chei șir și valori întregi. Acest lucru se face folosind sintaxa std::unordered_map my_map;
Apoi, programul inserează trei perechi cheie-valoare în containerul my_map folosind operatorul []: „apple” cu o valoare de 10, „banana” cu o valoare de 20 și „orange” cu o valoare de 30.
Acest lucru se face folosind sintaxa my_map['apple'] = 10;, my_map['banana'] = 20; și my_map['orange'] = 30; respectiv.
În cele din urmă, programul imprimă valoarea asociată tastei „banana” folosind operatorul [] și obiectul std::cout.

Ieșire program:

Inserarea datelor într-un tabel Hash

Pentru a insera o pereche cheie-valoare într-un tabel hash, trebuie mai întâi să creăm un index în matrice pentru a stoca perechea cheie-valoare. Dacă o altă cheie se mapează la același index, avem o coliziune și trebuie să o gestionăm în mod corespunzător. O metodă obișnuită este utilizarea înlănțuirii, în care fiecare grupă din matrice conține o listă legată de perechi cheie-valoare care au aceeași valoare hash.

Iată un exemplu despre cum să inserați o pereche cheie-valoare într-un tabel hash folosind înlănțuirea:

 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-&gt;key = key; new_node-&gt;value = value; new_node-&gt;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-&gt;next != NULL) { curr_node = curr_node-&gt;next; } curr_node-&gt;next = new_node; } }

Explicaţie:

Mai întâi, este definită o structură numită nod, care reprezintă un singur nod în tabelul hash.
Fiecare nod are trei membri: o cheie char* pentru a stoca cheia, o valoare int pentru a stoca valoarea asociată și un pointer către un alt nod numit lângă pentru a gestiona coliziunile din tabelul hash folosind o listă legată.
O matrice de pointeri de noduri numită hash_table este declarată cu o dimensiune de 100. Această matrice va fi folosită pentru a stoca elementele tabelului hash.
Funcția de inserare ia ca parametri o cheie char* și o valoare int.
Începe prin a calcula valoarea hash pentru cheia dată folosind funcția hash, care se presupune că este definită în altă parte a programului.
Valoarea hash este apoi redusă pentru a se încadra în dimensiunea matricei hash_table folosind operatorul de modul % 100.
Un nou nod este creat folosind alocarea dinamică a memoriei (malloc(sizeof(node))), iar membrii săi (key, value și next) sunt alocați cu cheia, valoarea și respectiv NULL furnizate.
Dacă slotul corespunzător din matricea hash_table este gol (NULL), indicând că nu a avut loc nicio coliziune, noul nod este atribuit în mod direct acelui slot (hash_table[hash_value] = new_node).

Cu toate acestea, dacă există deja un nod prezent la acel index în matricea hash_table, funcția trebuie să gestioneze coliziunea. Parcurge lista legată pornind de la nodul curent (hash_table[hash_value]) și trece la următorul nod până când ajunge la sfârșit (curr_node->next != NULL). Odată ajuns la sfârșitul listei, noul nod este adăugat ca următor nod (curr_node->next = new_node).

Implementarea hashingului în C++:

Să vedem o implementare a hashingului în C++ folosind adresarea deschisă și sondarea liniară pentru rezoluția coliziunilor. Vom implementa un tabel hash care stochează numere întregi.

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

TechCodeview