Úvod do hašovania v dátovej štruktúre:

Hašovanie je populárna technika v informatike, ktorá zahŕňa mapovanie veľkých súborov údajov na hodnoty s pevnou dĺžkou. Ide o proces premeny súboru údajov s premenlivou veľkosťou na súbor údajov s pevnou veľkosťou. Schopnosť vykonávať efektívne operácie vyhľadávania robí z hašovania základný koncept v dátových štruktúrach.

Čo je hashovanie?

Hašovací algoritmus sa používa na konverziu vstupu (ako je reťazec alebo celé číslo) na výstup s pevnou veľkosťou (označovaný ako hašovací kód alebo hašovacia hodnota). Údaje sa potom uložia a získajú pomocou tejto hašovacej hodnoty ako indexu v poli alebo hašovacej tabuľke. Hašovacia funkcia musí byť deterministická, čo zaručuje, že pre daný vstup prinesie vždy rovnaký výsledok.

Hašovanie sa bežne používa na vytvorenie jedinečného identifikátora pre časť údajov, ktorý možno použiť na rýchle vyhľadanie týchto údajov vo veľkom súbore údajov. Napríklad webový prehliadač môže použiť hash na bezpečné ukladanie hesiel webových stránok. Keď používateľ zadá svoje heslo, prehliadač ho skonvertuje na hodnotu hash a porovná ju s uloženou hodnotou hash, aby overil používateľa.

Čo je hash Key?

V kontexte hašovania je hašovací kľúč (známy aj ako hašovacia hodnota alebo hašovací kód) numerická alebo alfanumerická reprezentácia s pevnou veľkosťou generovaná hašovacím algoritmom. Odvodzuje sa zo vstupných údajov, ako je textový reťazec alebo súbor, prostredníctvom procesu známeho ako hašovanie.

Hašovanie zahŕňa aplikáciu špecifickej matematickej funkcie na vstupné údaje, ktorá vytvára jedinečný hash kľúč, ktorý má zvyčajne pevnú dĺžku bez ohľadu na veľkosť vstupu. Výsledný hash kľúč je v podstate digitálny odtlačok pôvodných údajov.

filmová herečka rekha

Hash kľúč slúži na niekoľko účelov. Bežne sa používa na kontrolu integrity údajov, pretože aj malá zmena vo vstupných údajoch vytvorí výrazne odlišný hash kľúč. Hash kľúče sa tiež používajú na efektívne vyhľadávanie a ukladanie údajov v hašovacích tabuľkách alebo dátových štruktúrach, pretože umožňujú rýchle vyhľadávanie a porovnávacie operácie.

Ako funguje hashovanie?

Proces hashovania možno rozdeliť do troch krokov:

• Vstup: Údaje, ktoré sa majú hašovať, sa zadajú do hašovacieho algoritmu.
• Hašovacia funkcia: Hašovací algoritmus berie vstupné údaje a aplikuje matematickú funkciu na generovanie hašovacej hodnoty s pevnou veľkosťou. Hašovacia funkcia by mala byť navrhnutá tak, aby rôzne vstupné hodnoty vytvárali rôzne hašovacie hodnoty a malé zmeny na vstupe viedli k veľkým zmenám vo výstupe.
• Výstup: Vráti sa hodnota hash, ktorá sa používa ako index na ukladanie alebo získavanie údajov v dátovej štruktúre.

Hašovacie algoritmy:

Existuje množstvo hashovacích algoritmov, z ktorých každý má svoje výhody a nevýhody. Medzi najobľúbenejšie algoritmy patria:

• MD5: Široko používaný hašovací algoritmus, ktorý vytvára 128-bitovú hašovaciu hodnotu.
• SHA-1: Populárny hašovací algoritmus, ktorý vytvára 160-bitovú hašovaciu hodnotu.
• SHA-256: Bezpečnejší hašovací algoritmus, ktorý vytvára 256-bitovú hašovaciu hodnotu.

Hash funkcia:

Hašovacia funkcia: Hašovacia funkcia je typ matematickej operácie, ktorá preberá vstup (alebo kľúč) a vydáva výsledok s pevnou veľkosťou známy ako hašovací kód alebo hašovacia hodnota. Hašovacia funkcia musí vždy poskytnúť rovnaký hašovací kód pre rovnaký vstup, aby bola deterministická. Okrem toho by hašovacia funkcia mala vytvoriť jedinečný hašovací kód pre každý vstup, ktorý je známy ako hašovacia vlastnosť.

Existujú rôzne typy hashovacích funkcií, vrátane:

Spôsob delenia:

Táto metóda zahŕňa rozdelenie kľúča veľkosťou tabuľky a zvyšok ako hash hodnotu. Ak je napríklad veľkosť tabuľky 10 a kľúč je 23, hodnota hash by bola 3 (23 % 10 = 3).

Metóda násobenia:

Táto metóda zahŕňa vynásobenie kľúča konštantou a prevzatie zlomkovej časti produktu ako hašovacej hodnoty. Ak je napríklad kľúč 23 a konštanta 0,618, hodnota hash by bola 2 (poschodie(10*(0,61823 - poschodie(0,61823))) = poschodie(2,236) = 2).

Univerzálne hashovanie:

Táto metóda zahŕňa použitie náhodnej hašovacej funkcie z rodiny hašovacích funkcií. To zaisťuje, že hašovacia funkcia nie je zameraná na žiadny konkrétny vstup a je odolná voči útokom.

Rozlíšenie kolízie

Jednou z hlavných výziev pri hašovaní je riešenie kolízií, ku ktorým dochádza, keď dve alebo viaceré vstupné hodnoty vytvárajú rovnakú hašovaciu hodnotu. Na riešenie kolízií sa používajú rôzne techniky, vrátane:

• Reťazenie: Pri tejto technike obsahuje každý slot hašovacej tabuľky prepojený zoznam všetkých hodnôt, ktoré majú rovnakú hašovaciu hodnotu. Táto technika je jednoduchá a ľahko implementovateľná, ale môže viesť k slabému výkonu, keď sú prepojené zoznamy príliš dlhé.
• Otvorené adresovanie: Pri tejto technike, keď dôjde ku kolízii, algoritmus hľadá prázdny slot v hašovacej tabuľke sondovaním po sebe nasledujúcich slotov, kým nenájde prázdny slot. Táto technika môže byť efektívnejšia ako reťazenie, keď je faktor zaťaženia nízky, ale môže viesť k zhlukovaniu a slabému výkonu, keď je faktor zaťaženia vysoký.
• Dvojité hašovanie: Toto je variácia otvoreného adresovania, ktorá používa druhú hašovaciu funkciu na určenie ďalšieho slotu, ktorý sa má testovať, keď dôjde ku kolízii. Táto technika môže pomôcť znížiť zhlukovanie a zlepšiť výkon.

Príklad rozlíšenia kolízie

Pokračujme v našom príklade hašovacej tabuľky s veľkosťou 5. Do hašovacej tabuľky chceme uložiť páry kľúč – hodnota 'John: 123456' a 'Mary: 987654'. Oba kľúče vytvárajú rovnaký hash kód 4, takže dôjde ku kolízii.

Na vyriešenie kolízie môžeme použiť reťazenie. Vytvoríme prepojený zoznam na indexe 4 a do zoznamu pridáme páry kľúč – hodnota. Tabuľka hash teraz vyzerá takto:

0:

1:

2:

3:

4: Ján: 123456 -> Mária: 987654

5:

Tabuľka hash:

Hašovacia tabuľka je dátová štruktúra, ktorá ukladá údaje do poľa. Typicky sa vyberie veľkosť poľa, ktorá je väčšia ako počet prvkov, ktoré sa zmestia do hašovacej tabuľky. Kľúč sa mapuje na index v poli pomocou hašovacej funkcie.

Hašovacia funkcia sa používa na nájdenie indexu, do ktorého je potrebné vložiť prvok do hašovacej tabuľky, aby bolo možné pridať nový prvok. Ak nedôjde ku kolízii, prvok sa pridá do tohto indexu. Ak dôjde ku kolízii, na nájdenie ďalšieho voľného slotu v poli sa použije metóda rozlíšenia kolízie.

Hašovacia funkcia sa používa na nájdenie indexu, v ktorom je prvok uložený, aby ho bolo možné získať z hašovacej tabuľky. Ak sa prvok v tomto indexe nenájde, metóda rozlíšenia kolízie sa použije na vyhľadanie prvku v prepojenom zozname (ak sa použije reťazenie) alebo v ďalšom dostupnom slote (ak sa použije otvorené adresovanie).

Operácie hash table

Existuje niekoľko operácií, ktoré možno vykonať na hašovacej tabuľke, vrátane:

• Vloženie: Vloženie nového páru kľúč – hodnota do hašovacej tabuľky.
• Odstránenie: Odstránenie páru kľúč – hodnota z hašovacej tabuľky.
• Hľadať: Hľadá sa pár kľúč – hodnota v hašovacej tabuľke.

Vytvorenie tabuľky hash:

Hašovanie sa často používa na vytváranie hašovacích tabuliek, čo sú dátové štruktúry, ktoré umožňujú rýchle vkladanie, odstraňovanie a získavanie údajov. V každom poli segmentov, ktoré tvoria hašovaciu tabuľku, možno uložiť jeden alebo viacero párov kľúč – hodnota.

Na vytvorenie hašovacej tabuľky musíme najprv definovať hašovaciu funkciu, ktorá mapuje každý kľúč na jedinečný index v poli. Jednoduchá hašovacia funkcia môže spočívať v tom, že vezmete súčet hodnôt ASCII znakov v kľúči a zvyšok použijete pri delení veľkosťou poľa. Táto hašovacia funkcia je však neefektívna a môže viesť ku kolíziám (dva kľúče, ktoré sa mapujú na rovnaký index).

Aby sme sa vyhli kolíziám, môžeme použiť pokročilejšie hašovacie funkcie, ktoré vytvárajú rovnomernejšie rozloženie hašovacích hodnôt v poli. Jedným z populárnych algoritmov je hašovacia funkcia djb2, ktorá používa bitové operácie na generovanie hašovacej hodnoty:

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

Táto hašovacia funkcia berie reťazec ako vstup a vracia hodnotu hash dlhého celého čísla bez znamienka. Funkcia inicializuje hodnotu hash 5381 a potom iteruje každý znak v reťazci pomocou bitových operácií na vygenerovanie novej hodnoty hash. Vráti sa konečná hodnota hash.

Hash tabuľky v C++

V C++ štandardná knižnica poskytuje triedu kontajnera hash tabuľky s názvom unordered_map. Kontajner unordered_map je implementovaný pomocou hašovacej tabuľky a poskytuje rýchly prístup k párom kľúč – hodnota. Kontajner unordered_map používa hašovaciu funkciu na výpočet hašovacieho kódu kľúčov a potom používa otvorené adresovanie na riešenie kolízií.

Ak chcete použiť kontajner unordered_map v C++, musíte zahrnúť hlavičkový súbor. Tu je príklad, ako vytvoriť kontajner unordered_map v 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; } 

Vysvetlenie:

• Tento program demonštruje použitie kontajnera unordered_map v C++, ktorý je implementovaný pomocou hash tabuľky a poskytuje rýchly prístup k párom kľúč-hodnota.
• Po prvé, program obsahuje potrebné hlavičkové súbory: a.
• Potom program vytvorí prázdny kontajner unordered_map s názvom my_map, ktorý má reťazcové kľúče a celočíselné hodnoty. To sa vykonáva pomocou syntaxe std::unordered_map moja_mapa;
• Potom program vloží tri páry kľúč – hodnota do kontajnera my_map pomocou operátora []: „jablko“ s hodnotou 10, „banán“ s hodnotou 20 a „oranžový“ s hodnotou 30.
• Toto sa vykonáva pomocou syntaxe my_map['apple'] = 10;, my_map['banana'] = 20; a my_map['orange'] = 30; resp.
• Nakoniec program vytlačí hodnotu spojenú s kľúčom 'banán' pomocou operátora [] a objektu std::cout.

Výstup programu:

Vkladanie údajov do tabuľky hash

Ak chcete vložiť pár kľúč-hodnota do hašovacej tabuľky, najprv musíme zadať index do poľa, aby sa pár kľúč-hodnota uložil. Ak sa iný kľúč namapuje na rovnaký index, máme kolíziu a musíme ju primerane zvládnuť. Jednou z bežných metód je použitie reťazenia, kde každý segment v poli obsahuje prepojený zoznam párov kľúč – hodnota, ktoré majú rovnakú hodnotu hash.

Tu je príklad, ako vložiť pár kľúč – hodnota do hašovacej tabuľky pomocou reťazenia:

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

Vysvetlenie:

• Najprv je definovaná štruktúra nazývaná uzol, ktorá predstavuje jeden uzol v hašovacej tabuľke.
• Každý uzol má tri členy: kľúč char* na uloženie kľúča, hodnotu int na uloženie pridruženej hodnoty a ukazovateľ na ďalší uzol, ktorý sa volá vedľa na spracovanie kolízií v hašovacej tabuľke pomocou prepojeného zoznamu.
• Pole ukazovateľov uzla s názvom hash_table je deklarované s veľkosťou 100. Toto pole sa použije na uloženie prvkov hašovacej tabuľky.
• Funkcia vloženia berie ako parametre kľúč char* a hodnotu int.
• Začína sa výpočtom hašovacej hodnoty pre daný kľúč pomocou hašovacej funkcie, o ktorej sa predpokladá, že je definovaná inde v programe.
• Hodnota hash sa potom zníži tak, aby sa zmestila do veľkosti poľa hash_table pomocou operátora modulu % 100.
• Nový uzol sa vytvorí pomocou dynamickej alokácie pamäte (malloc(sizeof(node))) a jeho členom (kľúč, hodnota a ďalšie) sa priradí poskytnutý kľúč, hodnota a NULL.
• Ak je zodpovedajúci slot v poli hash_table prázdny (NULL), čo znamená, že nenastala kolízia, nový uzol sa priradí priamo k tomuto slotu (hash_table[hash_value] = nový_uzol).

Ak sa však už na tomto indexe nachádza uzol v poli hash_table, funkcia musí zvládnuť kolíziu. Prechádza prepojeným zoznamom počnúc od aktuálneho uzla (hash_table[hash_value]) a presúva sa na ďalší uzol, kým nedosiahne koniec (curr_node->next != NULL). Po dosiahnutí konca zoznamu sa nový uzol pripojí ako ďalší uzol (curr_node->next = nový_uzol).

Implementácia hashovania v C++:

Pozrime sa na implementáciu hashovania v C++ pomocou otvoreného adresovania a lineárneho snímania na riešenie kolízií. Implementujeme hašovaciu tabuľku, ktorá ukladá celé čísla.

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