TechCodeview

Uvod v zgoščevanje v podatkovni strukturi:

Zgoščevanje je priljubljena tehnika v računalništvu, ki vključuje preslikavo velikih nizov podatkov v vrednosti fiksne dolžine. Je postopek pretvorbe niza podatkov spremenljive velikosti v niz podatkov fiksne velikosti. Zaradi zmožnosti izvajanja učinkovitih operacij iskanja je zgoščevanje bistven koncept v podatkovnih strukturah.

polimorfizem v Javi

Kaj je zgoščevanje?

Algoritem zgoščevanja se uporablja za pretvorbo vnosa (kot je niz ali celo število) v izhod fiksne velikosti (imenovan zgoščevalna koda ali zgoščena vrednost). Podatki se nato shranijo in pridobijo z uporabo te zgoščene vrednosti kot indeksa v matriki ali zgoščeni tabeli. Zgoščevalna funkcija mora biti deterministična, kar zagotavlja, da bo za dani vnos vedno dala enak rezultat.

Zgoščevanje se običajno uporablja za ustvarjanje edinstvenega identifikatorja za del podatkov, ki ga je mogoče uporabiti za hitro iskanje teh podatkov v velikem naboru podatkov. Spletni brskalnik lahko na primer uporablja zgoščevanje za varno shranjevanje gesel spletnih mest. Ko uporabnik vnese svoje geslo, ga brskalnik pretvori v zgoščeno vrednost in primerja s shranjeno zgoščeno vrednostjo za avtentikacijo uporabnika.

Kaj je zgoščeni ključ?

V kontekstu zgoščevanja je zgoščevalni ključ (znan tudi kot zgoščevalna vrednost ali zgoščevalna koda) numerična ali alfanumerična predstavitev fiksne velikosti, ki jo ustvari algoritem zgoščevanja. Izpeljan je iz vhodnih podatkov, kot je besedilni niz ali datoteka, s postopkom, znanim kot zgoščevanje.

Zgoščevanje vključuje uporabo posebne matematične funkcije za vhodne podatke, ki ustvari edinstven zgoščevalni ključ, ki je običajno fiksne dolžine, ne glede na velikost vnosa. Nastali zgoščeni ključ je v bistvu digitalni prstni odtis izvirnih podatkov.

Zgoščevalni ključ ima več namenov. Običajno se uporablja za preverjanje celovitosti podatkov, saj bo že majhna sprememba vhodnih podatkov ustvarila bistveno drugačen zgoščeni ključ. Zgoščevalni ključi se uporabljajo tudi za učinkovito pridobivanje in shranjevanje podatkov v zgoščevalnih tabelah ali podatkovnih strukturah, saj omogočajo hitro iskanje in primerjavo.

Kako deluje zgoščevanje?

Postopek zgoščevanja lahko razdelimo na tri korake:

• Vnos: Podatki za zgoščevanje se vnesejo v algoritem zgoščevanja.
• Funkcija zgoščevanja: Algoritem zgoščevanja vzame vhodne podatke in uporabi matematično funkcijo za ustvarjanje zgoščene vrednosti fiksne velikosti. Zgoščevalna funkcija mora biti zasnovana tako, da različne vhodne vrednosti ustvarijo različne zgoščene vrednosti, majhne spremembe v vhodu pa velike spremembe v izhodu.
• Izhod: vrne se zgoščena vrednost, ki se uporablja kot indeks za shranjevanje ali pridobivanje podatkov v podatkovni strukturi.

Algoritmi zgoščevanja:

Obstaja veliko algoritmov zgoščevanja, od katerih ima vsak svoje prednosti in slabosti. Najbolj priljubljeni algoritmi vključujejo naslednje:

• MD5: široko uporabljen algoritem zgoščevanja, ki ustvari 128-bitno zgoščeno vrednost.
• SHA-1: priljubljen algoritem zgoščevanja, ki ustvari 160-bitno zgoščeno vrednost.
• SHA-256: varnejši algoritem zgoščevanja, ki ustvari 256-bitno zgoščeno vrednost.

Funkcija zgoščevanja:

Zgoščevalna funkcija: zgoščevalna funkcija je vrsta matematične operacije, ki sprejme vnos (ali ključ) in izpiše rezultat s fiksno velikostjo, znan kot zgoščevalna koda ali zgoščena vrednost. Zgoščevalna funkcija mora vedno vrniti isto zgoščevalno kodo za isti vnos, da je deterministična. Poleg tega mora zgoščevalna funkcija ustvariti edinstveno zgoščevalno kodo za vsak vnos, kar je znano kot lastnost zgoščevanja.

Obstajajo različne vrste zgoščevalnih funkcij, vključno z:

Metoda delitve:

Ta metoda vključuje deljenje ključa z velikostjo tabele in preostanek kot zgoščeno vrednost. Na primer, če je velikost tabele 10 in je ključ 23, bi bila zgoščena vrednost 3 (23 % 10 = 3).

Metoda množenja:

Ta metoda vključuje množenje ključa s konstanto in vzetje delnega dela produkta kot zgoščene vrednosti. Na primer, če je ključ 23 in konstanta 0,618, bi bila zgoščena vrednost 2 (floor(10*(0,61823 - floor(0,61823))) = floor(2,236) = 2).

Univerzalno zgoščevanje:

Ta metoda vključuje uporabo naključne zgoščevalne funkcije iz družine zgoščevalnih funkcij. To zagotavlja, da zgoščevalna funkcija ni pristranska glede na določen vnos in je odporna na napade.

Reševanje trkov

Eden glavnih izzivov pri zgoščevanju je obravnavanje kolizij, do katerih pride, ko dve ali več vhodnih vrednosti proizvedejo enako zgoščeno vrednost. Za reševanje kolizij se uporabljajo različne tehnike, vključno z:

poravnava img css

• Veriženje: pri tej tehniki vsaka reža zgoščene tabele vsebuje povezan seznam vseh vrednosti, ki imajo enako zgoščeno vrednost. Ta tehnika je preprosta in enostavna za implementacijo, vendar lahko povzroči slabo delovanje, če povezani seznami postanejo predolgi.
• Odprto naslavljanje: pri tej tehniki, ko pride do kolizije, algoritem išče prazno režo v zgoščeni tabeli tako, da preiskuje zaporedne reže, dokler ne najde prazne reže. Ta tehnika je lahko učinkovitejša od veriženja, ko je faktor obremenitve nizek, vendar lahko povzroči združevanje v gruče in slabo delovanje, ko je faktor obremenitve visok.
• Dvojno zgoščevanje: To je različica odprtega naslavljanja, ki uporablja drugo zgoščevalno funkcijo za določitev naslednje reže za sondiranje, ko pride do kolizije. Ta tehnika lahko pomaga zmanjšati gručenje in izboljša učinkovitost.

Primer reševanja trkov

Nadaljujmo z našim primerom zgoščevalne tabele z velikostjo 5. V zgoščevalno tabelo želimo shraniti para ključ-vrednost 'John: 123456' in 'Mary: 987654'. Oba ključa proizvedeta isto zgoščeno kodo 4, zato pride do kolizije.

Za razrešitev kolizije lahko uporabimo veriženje. Ustvarimo povezan seznam na indeksu 4 in na seznam dodamo pare ključ-vrednost. Zgoščevalna tabela je zdaj videti takole:

0:

1:

če drugače bash

2:

3:

4: Janez: 123456 -> Marija: 987654

5:

Zgoščevalna tabela:

Zgoščevalna tabela je podatkovna struktura, ki shranjuje podatke v matriko. Običajno je izbrana velikost za matriko, ki je večja od števila elementov, ki se lahko prilegajo zgoščevalni tabeli. Ključ je preslikan v indeks v matriki z uporabo zgoščevalne funkcije.

Zgoščevalna funkcija se uporablja za iskanje indeksa, kamor je treba element vstaviti v zgoščevalno tabelo, da se doda nov element. Element se doda temu indeksu, če ni trka. Če pride do trka, se za iskanje naslednje razpoložljive reže v nizu uporabi metoda razreševanja trkov.

shehzad poonawala

Zgoščevalna funkcija se uporablja za iskanje indeksa, v katerem je shranjen element, da se ga pridobi iz zgoščevalne tabele. Če elementa ni mogoče najti na tem indeksu, se za iskanje elementa na povezanem seznamu (če je uporabljeno veriženje) ali v naslednji razpoložljivi reži (če je uporabljeno odprto naslavljanje) uporabi metoda reševanja trkov.

Operacije z zgoščeno tabelo

Na zgoščeni tabeli je mogoče izvesti več operacij, vključno z:

• Vstavljanje: vstavljanje novega para ključ-vrednost v zgoščeno tabelo.
• Brisanje: odstranitev para ključ-vrednost iz zgoščene tabele.
• Iskanje: Iskanje para ključ-vrednost v zgoščeni tabeli.

Ustvarjanje zgoščene tabele:

Zgoščevanje se pogosto uporablja za izdelavo zgoščevalnih tabel, ki so podatkovne strukture, ki omogočajo hitro vstavljanje, brisanje in iskanje podatkov. Enega ali več parov ključ-vrednost je mogoče shraniti v vsako od matrik veder, ki sestavljajo zgoščeno tabelo.

Če želite ustvariti zgoščevalno tabelo, moramo najprej definirati zgoščevalno funkcijo, ki preslika vsak ključ v edinstven indeks v matriki. Preprosta zgoščevalna funkcija bi lahko bila, da vzame vsoto vrednosti ASCII znakov v ključu in uporabi preostanek pri deljenju z velikostjo matrike. Vendar je ta zgoščevalna funkcija neučinkovita in lahko vodi do kolizij (dva ključa, ki se preslikata v isti indeks).

Da bi se izognili kolizijam, lahko uporabimo naprednejše zgoščevalne funkcije, ki ustvarijo enakomernejšo porazdelitev zgoščenih vrednosti po matriki. Eden priljubljenih algoritmov je zgoščevalna funkcija djb2, ki uporablja bitne operacije za ustvarjanje zgoščene vrednosti:

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

Ta zgoščevalna funkcija sprejme niz kot vhod in vrne nepredznačeno dolgo celo število zgoščene vrednosti. Funkcija inicializira zgoščeno vrednost 5381 in nato ponovi vsak znak v nizu z uporabo bitnih operacij za ustvarjanje nove zgoščene vrednosti. Vrne se končna zgoščena vrednost.

Zgoščevalne tabele v C++

V C++ standardna knjižnica ponuja vsebniški razred zgoščene tabele, imenovan unordered_map. Vsebnik unordered_map je implementiran z zgoščeno tabelo in omogoča hiter dostop do parov ključ-vrednost. Vsebnik unordered_map uporablja zgoščevalno funkcijo za izračun zgoščevalne kode ključev in nato uporablja odprto naslavljanje za razreševanje kolizij.

Če želite uporabiti vsebnik unordered_map v C++, morate vključiti datoteko glave. Tukaj je primer, kako ustvariti vsebnik 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; } 

Pojasnilo:

• Ta program prikazuje uporabo vsebnika unordered_map v C++, ki je implementiran z zgoščeno tabelo in omogoča hiter dostop do parov ključ-vrednost.
• Prvič, program vključuje potrebne datoteke glave: in.
• Nato program ustvari prazen vsebnik unordered_map, imenovan my_map, ki ima nizovne ključe in celoštevilske vrednosti. To naredimo s sintakso std::unordered_map my_map;
• Nato program vstavi tri pare ključ-vrednost v vsebnik my_map z uporabo operatorja []: 'apple' z vrednostjo 10, 'banana' z vrednostjo 20 in 'orange' z vrednostjo 30.
• To naredimo s sintakso my_map['apple'] = 10;, my_map['banana'] = 20; in my_map['orange'] = 30; oz.
• Na koncu program natisne vrednost, povezano s ključem 'banana', z uporabo operatorja [] in objekta std::cout.

Izhod programa:

kaj to pomeni xd

Vstavljanje podatkov v zgoščeno tabelo

Če želite v zgoščevalno tabelo vstaviti par ključ-vrednost, moramo najprej dodati indeks v matriko za shranjevanje para ključ-vrednost. Če se drug ključ preslika v isti indeks, pride do kolizije in jo moramo ustrezno obravnavati. Ena pogosta metoda je uporaba veriženja, kjer vsako vedro v matriki vsebuje povezan seznam parov ključ-vrednost, ki imajo enako zgoščeno vrednost.

Tukaj je primer, kako z veriženjem vstavite par ključ-vrednost v zgoščeno tabelo:

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

Pojasnilo:

• Najprej je definirana struktura, imenovana vozlišče, ki predstavlja eno samo vozlišče v zgoščeni tabeli.
• Vsako vozlišče ima tri člane: ključ char* za shranjevanje ključa, vrednost int za shranjevanje povezane vrednosti in kazalec na drugo vozlišče, ki je poklicano poleg za obravnavo trkov v zgoščevalni tabeli z uporabo povezanega seznama.
• Matrika kazalcev vozlišč, imenovana hash_table, je deklarirana z velikostjo 100. Ta matrika bo uporabljena za shranjevanje elementov zgoščene tabele.
• Funkcija vstavljanja vzame ključ char* in vrednost int kot parametra.
• Začne se z izračunom zgoščevalne vrednosti za dani ključ z uporabo zgoščevalne funkcije, za katero se predpostavlja, da je definirana drugje v programu.
• Zgoščevalna vrednost se nato zmanjša, da se prilega velikosti matrike hash_table z uporabo operaterja modula % 100.
• Novo vozlišče je ustvarjeno z uporabo dinamične dodelitve pomnilnika (malloc(sizeof(node))), njegovi člani (ključ, vrednost in naslednji) pa so dodeljeni s podanim ključem, vrednostjo oziroma NULL.
• Če je ustrezna reža v matriki hash_table prazna (NULL), kar pomeni, da ni prišlo do kolizije, je novo vozlišče neposredno dodeljeno tej reži (hash_table[hash_value] = new_node).

Če pa je v tem indeksu v matriki hash_table že prisotno vozlišče, mora funkcija obravnavati trk. Prečka povezani seznam, začenši s trenutnim vozliščem (hash_table[hash_value]) in se premakne na naslednje vozlišče, dokler ne doseže konca (curr_node->next != NULL). Ko je dosežen konec seznama, je novo vozlišče dodano kot naslednje vozlišče (curr_node->next = new_node).

Implementacija zgoščevanja v C++:

Oglejmo si izvedbo zgoščevanja v C++ z uporabo odprtega naslavljanja in linearnega tipanja za reševanje trkov. Implementirali bomo razpršilno tabelo, ki hrani cela števila.

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