Uvod u hashiranje u strukturi podataka:

Raspršivanje je popularna tehnika u računalnoj znanosti koja uključuje mapiranje velikih skupova podataka u vrijednosti fiksne duljine. To je proces pretvaranja skupa podataka promjenjive veličine u skup podataka fiksne veličine. Sposobnost izvođenja učinkovitih operacija pretraživanja čini raspršivanje bitnim konceptom u strukturama podataka.

Što je hashiranje?

Algoritam raspršivanja koristi se za pretvaranje ulaza (kao što je niz ili cijeli broj) u izlaz fiksne veličine (koji se naziva hash kod ili hash vrijednost). Podaci se zatim pohranjuju i dohvaćaju pomoću te hash vrijednosti kao indeksa u nizu ili hash tablici. Raspršivačka funkcija mora biti deterministička, što jamči da će uvijek dati isti rezultat za dati unos.

Raspršivanje se obično koristi za stvaranje jedinstvenog identifikatora za dio podataka, koji se može koristiti za brzo traženje tih podataka u velikom skupu podataka. Na primjer, web-preglednik može koristiti raspršivanje za sigurno pohranjivanje lozinki web-mjesta. Kada korisnik unese svoju lozinku, preglednik je pretvara u hash vrijednost i uspoređuje je s pohranjenom hash vrijednošću kako bi autentificirao korisnika.

Što je hash ključ?

U kontekstu hashiranja, hash ključ (također poznat kao hash vrijednost ili hash kod) je numerička ili alfanumerička reprezentacija fiksne veličine koju generira algoritam hashiranja. Izvodi se iz ulaznih podataka, kao što je tekstualni niz ili datoteka, kroz proces poznat kao raspršivanje.

usporedivo sučelje u Javi

Raspršivanje uključuje primjenu određene matematičke funkcije na ulazne podatke, koja proizvodi jedinstveni hash ključ koji je obično fiksne duljine, bez obzira na veličinu ulaza. Rezultirajući hash ključ je u biti digitalni otisak izvornih podataka.

Hash ključ služi u nekoliko svrha. Obično se koristi za provjere integriteta podataka, budući da će čak i mala promjena u ulaznim podacima proizvesti značajno drugačiji hash ključ. Hash ključevi također se koriste za učinkovito pronalaženje i pohranjivanje podataka u hash tablicama ili strukturama podataka, budući da omogućuju brzo pretraživanje i operacije usporedbe.

Kako funkcionira raspršivanje?

Proces raspršivanja može se podijeliti u tri koraka:

• Unos: podaci koji se raspršuju unose se u algoritam raspršivanja.
• Raspršivanje: Algoritam raspršivanja uzima ulazne podatke i primjenjuje matematičku funkciju za generiranje raspršivačke vrijednosti fiksne veličine. Funkcija raspršivanja treba biti dizajnirana tako da različite ulazne vrijednosti proizvode različite vrijednosti raspršivanja, a male promjene u ulazu proizvode velike promjene u izlazu.
• Izlaz: Vraća se hash vrijednost koja se koristi kao indeks za pohranjivanje ili dohvaćanje podataka u strukturi podataka.

Algoritmi raspršivanja:

Postoje brojni algoritmi raspršivanja, svaki s različitim prednostima i nedostacima. Najpopularniji algoritmi uključuju sljedeće:

• MD5: široko korišteni algoritam raspršivanja koji proizvodi 128-bitnu vrijednost raspršivanja.
• SHA-1: popularan algoritam raspršivanja koji proizvodi 160-bitnu vrijednost raspršivanja.
• SHA-256: Sigurniji algoritam raspršivanja koji proizvodi 256-bitnu vrijednost raspršivanja.

Hash funkcija:

Funkcija raspršivanja: Funkcija raspršivanja vrsta je matematičke operacije koja uzima unos (ili ključ) i daje rezultat fiksne veličine poznat kao hash kod ili vrijednost raspršivanja. Raspršivačka funkcija uvijek mora dati isti hash kod za isti ulaz kako bi bila deterministička. Dodatno, funkcija raspršivanja treba proizvesti jedinstveni hash kod za svaki unos, što je poznato kao svojstvo raspršivanja.

Postoje različite vrste hash funkcija, uključujući:

zašto string nepromjenjiv u Javi

Metoda podjele:

Ova metoda uključuje dijeljenje ključa s veličinom tablice i uzimanje ostatka kao hash vrijednosti. Na primjer, ako je veličina tablice 10, a ključ 23, hash vrijednost bi bila 3 (23 % 10 = 3).

Metoda množenja:

Ova metoda uključuje množenje ključa s konstantom i uzimanje razlomka umnoška kao hash vrijednosti. Na primjer, ako je ključ 23, a konstanta 0,618, hash vrijednost bi bila 2 (kat(10*(0,61823 - kat(0,61823))) = kat(2,236) = 2).

Univerzalno raspršivanje:

Ova metoda uključuje korištenje slučajne hash funkcije iz obitelji hash funkcija. To osigurava da hash funkcija nije pristrana prema bilo kojem određenom unosu i da je otporna na napade.

Rješavanje sudara

Jedan od glavnih izazova u hashiranju je rukovanje kolizijama do kojih dolazi kada dvije ili više ulaznih vrijednosti daju istu hash vrijednost. Postoje različite tehnike koje se koriste za rješavanje sudara, uključujući:

• Ulančavanje: U ovoj tehnici svaki utor hash tablice sadrži povezani popis svih vrijednosti koje imaju istu hash vrijednost. Ova tehnika je jednostavna i laka za implementaciju, ali može dovesti do loše izvedbe kada povezani popisi postanu predugi.
• Otvoreno adresiranje: U ovoj tehnici, kada dođe do kolizije, algoritam traži prazan utor u hash tablici ispitujući uzastopne utore dok se ne pronađe prazan utor. Ova tehnika može biti učinkovitija od ulančavanja kada je faktor opterećenja nizak, ali može dovesti do grupiranja i loše izvedbe kada je faktor opterećenja visok.
• Dvostruko raspršivanje: Ovo je varijacija otvorenog adresiranja koja koristi drugu funkciju raspršivanja za određivanje sljedećeg mjesta za ispitivanje kada dođe do kolizije. Ova tehnika može pomoći u smanjenju grupiranja i poboljšanju performansi.

Primjer rješavanja sudara

Nastavimo s našim primjerom hash tablice veličine 5. Želimo pohraniti parove ključ-vrijednost 'John: 123456' i 'Mary: 987654' u hash tablicu. Oba ključa proizvode isti hash kod 4, pa dolazi do kolizije.

Možemo koristiti ulančavanje da riješimo sudar. Stvaramo povezani popis na indeksu 4 i dodajemo parove ključ-vrijednost na popis. Raspršena tablica sada izgleda ovako:

0:

1:

10 od 100

2:

3:

4: Ivan: 123456 -> Marija: 987654

5:

Hash tablica:

Raspršena tablica podatkovna je struktura koja pohranjuje podatke u nizu. Tipično se odabire veličina niza koja je veća od broja elemenata koji mogu stati u hash tablicu. Ključ se preslikava na indeks u nizu pomoću hash funkcije.

Funkcija raspršivanja koristi se za lociranje indeksa gdje se element treba umetnuti u tablicu raspršivanja kako bi se dodao novi element. Element se dodaje tom indeksu ako nema sudara. Ako dođe do sudara, koristi se metoda rješavanja sudara za pronalaženje sljedećeg dostupnog mjesta u nizu.

java polimorfizam

Funkcija raspršivanja koristi se za lociranje indeksa u kojem je element pohranjen kako bi se dohvatio iz tablice raspršivanja. Ako element nije pronađen na tom indeksu, koristi se metoda rješavanja sudara za traženje elementa na povezanom popisu (ako se koristi ulančavanje) ili u sljedećem dostupnom utoru (ako se koristi otvoreno adresiranje).

Operacije hash tablice

Postoji nekoliko operacija koje se mogu izvesti na hash tablici, uključujući:

• Umetanje: Umetanje novog para ključ-vrijednost u hash tablicu.
• Brisanje: Uklanjanje para ključ-vrijednost iz hash tablice.
• Pretraživanje: Pretraživanje para ključ-vrijednost u hash tablici.

Stvaranje hash tablice:

Raspršivanje se često koristi za izradu hash tablica, koje su podatkovne strukture koje omogućuju brzo umetanje, brisanje i dohvaćanje podataka. Jedan ili više parova ključ-vrijednost mogu se pohraniti u svakom nizu spremnika koji čine hash tablicu.

Da bismo stvorili hash tablicu, prvo moramo definirati hash funkciju koja preslikava svaki ključ u jedinstveni indeks u nizu. Jednostavna hash funkcija može biti uzimanje zbroja ASCII vrijednosti znakova u ključu i korištenje ostatka kada se podijeli s veličinom niza. Međutim, ova hash funkcija je neučinkovita i može dovesti do kolizije (dva ključa koja se preslikavaju na isti indeks).

Kako bismo izbjegli sudare, možemo koristiti naprednije hash funkcije koje proizvode ravnomjerniju distribuciju hash vrijednosti u nizu. Jedan popularan algoritam je djb2 hash funkcija, koja koristi operacije po bitovima za generiranje hash vrijednosti:

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

Ova hash funkcija uzima niz kao ulaz i vraća nepredznačenu hash vrijednost dugog cijelog broja. Funkcija inicijalizira hash vrijednost od 5381 i zatim ponavlja svaki znak u nizu, koristeći bitwise operacije za generiranje nove hash vrijednosti. Vraća se konačna hash vrijednost.

igrica pigeon android

Hash tablice u C++

U C++ standardna biblioteka pruža klasu spremnika hash tablice pod nazivom unordered_map. Spremnik unordered_map implementiran je pomoću hash tablice i omogućuje brz pristup parovima ključ-vrijednost. Spremnik unordered_map koristi hash funkciju za izračunavanje hash koda ključeva, a zatim koristi otvoreno adresiranje za rješavanje kolizija.

Da biste koristili spremnik unordered_map u C++-u, trebate uključiti datoteku zaglavlja. Evo primjera kako stvoriti unordered_map spremnik u 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; } 

Obrazloženje:

• Ovaj program demonstrira upotrebu kontejnera unordered_map u C++, koji je implementiran pomoću hash tablice i omogućuje brz pristup parovima ključ-vrijednost.
• Prvo, program uključuje potrebne datoteke zaglavlja: i.
• Zatim program stvara prazan unordered_map spremnik pod nazivom my_map, koji ima nizove ključeva i cjelobrojne vrijednosti. To se radi korištenjem sintakse std::unordered_map my_map;
• Zatim program umeće tri para ključ-vrijednost u spremnik my_map pomoću operatora []: 'jabuka' s vrijednošću 10, 'banana' s vrijednošću 20 i 'naranča' s vrijednošću 30.
• To se radi pomoću sintakse my_map['apple'] = 10;, my_map['banana'] = 20; i my_map['orange'] = 30; odnosno.
• Na kraju, program ispisuje vrijednost povezanu s ključem 'banana' pomoću operatora [] i objekta std::cout.

Izlaz programa:

Umetanje podataka u hash tablicu

Da bismo umetnuli par ključ-vrijednost u hash tablicu, prvo trebamo unijeti indeks u polje za pohranjivanje para ključ-vrijednost. Ako se drugi ključ preslika na isti indeks, imamo koliziju i moramo je ispravno riješiti. Jedna uobičajena metoda je korištenje lančanog povezivanja, gdje svaki spremnik u nizu sadrži povezani popis parova ključ-vrijednost koji imaju istu hash vrijednost.

Evo primjera kako umetnuti par ključ-vrijednost u hash tablicu pomoću ulančavanja:

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

Obrazloženje:

• Prvo se definira struktura nazvana čvor, koja predstavlja jedan čvor u hash tablici.
• Svaki čvor ima tri člana: ključ char* za pohranjivanje ključa, int vrijednost za pohranjivanje pridružene vrijednosti i pokazivač na drugi čvor koji se poziva pored radi rukovanja kolizijama u hash tablici pomoću povezanog popisa.
• Niz pokazivača čvorova nazvan hash_table deklariran je s veličinom 100. Ovaj niz će se koristiti za pohranjivanje elemenata hash tablice.
• Funkcija umetanja uzima char* ključ i int vrijednost kao parametre.
• Započinje izračunavanjem hash vrijednosti za dani ključ pomoću hash funkcije, za koju se pretpostavlja da je definirana negdje drugdje u programu.
• Vrijednost hash-a zatim se smanjuje kako bi stala unutar veličine niza hash_table pomoću operatora modula % 100.
• Novi čvor se stvara korištenjem dinamičke dodjele memorije (malloc(sizeof(node))), a njegovim članovima (ključ, vrijednost i sljedeći) dodjeljuje se navedeni ključ, vrijednost odnosno NULL.
• Ako je odgovarajući utor u polju hash_table prazan (NULL), što znači da nije došlo do kolizije, novi se čvor izravno dodjeljuje tom utoru (hash_table[hash_value] = new_node).

Međutim, ako već postoji čvor na tom indeksu u polju hash_table, funkcija mora riješiti koliziju. Prolazi povezanim popisom počevši od trenutnog čvora (hash_table[hash_value]) i pomiče se na sljedeći čvor dok ne dođe do kraja (curr_node->next != NULL). Kada se dosegne kraj liste, novi čvor se dodaje kao sljedeći čvor (curr_node->next = new_node).

Implementacija hashiranja u C++:

Pogledajmo implementaciju raspršivanja u C++ koristeći otvoreno adresiranje i linearno ispitivanje za rješavanje sudara. Implementirat ćemo hash tablicu koja pohranjuje cijele brojeve.

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