Įvadas į maišą duomenų struktūroje:
Maiša yra populiari kompiuterių mokslo technika, apimanti didelių duomenų rinkinių susiejimą su fiksuoto ilgio reikšmėmis. Tai kintamo dydžio duomenų rinkinio konvertavimo į fiksuoto dydžio duomenų rinkinį procesas. Dėl galimybės atlikti efektyvias paieškos operacijas maišos naudojimas yra esminė duomenų struktūrų koncepcija.
java masyvo rūšiavimas
Kas yra Hashing?
Maišos algoritmas naudojamas konvertuoti įvestį (pvz., eilutę arba sveikąjį skaičių) į fiksuoto dydžio išvestį (vadinamą maišos kodu arba maišos reikšme). Tada duomenys saugomi ir gaunami naudojant šią maišos reikšmę kaip indeksą masyve arba maišos lentelėje. Maišos funkcija turi būti deterministinė, kuri garantuoja, kad ji visada duos tą patį rezultatą tam tikrai įvesties atveju.
Maišos naudojimas paprastai naudojamas norint sukurti unikalų duomenų dalies identifikatorių, kurį galima naudoti norint greitai surasti tuos duomenis dideliame duomenų rinkinyje. Pavyzdžiui, žiniatinklio naršyklė gali naudoti maišą, kad saugiai saugotų svetainių slaptažodžius. Kai vartotojas įveda slaptažodį, naršyklė konvertuoja jį į maišos reikšmę ir lygina ją su saugoma maišos reikšme, kad patvirtintų vartotoją.
Kas yra maišos raktas?
Maišos nustatymo kontekste maišos raktas (taip pat žinomas kaip maišos reikšmė arba maišos kodas) yra fiksuoto dydžio skaitmeninis arba raidinis ir skaitmeninis vaizdas, sugeneruotas maišos algoritmo. Jis gaunamas iš įvesties duomenų, pvz., teksto eilutės arba failo, naudojant procesą, žinomą kaip maiša.
Maišos nustatymas apima konkrečios matematinės funkcijos taikymą įvesties duomenims, kuri sukuria unikalų maišos raktą, kuris paprastai yra fiksuoto ilgio, neatsižvelgiant į įvesties dydį. Gautas maišos raktas iš esmės yra skaitmeninis pirminių duomenų piršto atspaudas.
Maišos raktas naudojamas keliems tikslams. Jis dažniausiai naudojamas tikrinant duomenų vientisumą, nes net ir nedidelis įvesties duomenų pakeitimas sukurs žymiai skirtingą maišos raktą. Maišos raktai taip pat naudojami efektyviam duomenų gavimui ir saugojimui maišos lentelėse arba duomenų struktūrose, nes jie leidžia greitai ieškoti ir palyginti operacijas.
Kaip veikia maišymas?
Maišos apdorojimo procesą galima suskirstyti į tris etapus:
- Įvestis: Duomenys, kuriems reikia maišos, įvedami į maišos algoritmą.
- Maišos funkcija: maišos algoritmas paima įvesties duomenis ir taiko matematinę funkciją, kad sukurtų fiksuoto dydžio maišos vertę. Maišos funkcija turėtų būti suprojektuota taip, kad skirtingos įvesties reikšmės sukurtų skirtingas maišos reikšmes, o nedideli įvesties pakeitimai sukeltų didelius išvesties pokyčius.
- Išvestis: grąžinama maišos reikšmė, kuri naudojama kaip indeksas duomenims saugoti arba gauti duomenų struktūroje.
Maišos algoritmai:
Yra daug maišos algoritmų, kurių kiekvienas turi savo privalumų ir trūkumų. Populiariausi algoritmai yra šie:
- MD5: plačiai naudojamas maišos algoritmas, sukuriantis 128 bitų maišos vertę.
- SHA-1: populiarus maišos algoritmas, sukuriantis 160 bitų maišos reikšmę.
- SHA-256: saugesnis maišos algoritmas, sukuriantis 256 bitų maišos vertę.
Maišos funkcija:
Maišos funkcija: maišos funkcija yra matematinės operacijos tipas, kuris paima įvestį (arba klavišą) ir išveda fiksuoto dydžio rezultatą, žinomą kaip maišos kodas arba maišos reikšmė. Kad būtų deterministinė, maišos funkcija visada turi duoti tą patį maišos kodą tai pačiai įvestiei. Be to, maišos funkcija turėtų sukurti unikalų maišos kodą kiekvienai įvestiei, kuri yra žinoma kaip maišos savybė.
Yra įvairių tipų maišos funkcijos, įskaitant:
Šis metodas apima rakto padalijimą iš lentelės dydžio ir likusios dalies paėmimą kaip maišos reikšmę. Pavyzdžiui, jei lentelės dydis yra 10, o raktas yra 23, maišos reikšmė būtų 3 (23 % 10 = 3).
Šis metodas apima rakto padauginimą iš konstantos ir trupmeninės produkto dalies paėmimą kaip maišos vertę. Pavyzdžiui, jei raktas yra 23, o konstanta yra 0,618, maišos reikšmė būtų 2 (floor(10*(0,61823 - floor(0,61823))) = floor(2,236) = 2).
Šis metodas apima atsitiktinės maišos funkcijos naudojimą iš maišos funkcijų šeimos. Tai užtikrina, kad maišos funkcija nebūtų nukreipta į jokią konkrečią įvestį ir yra atspari atakoms.
Susidūrimo raiška
Vienas iš pagrindinių maišos iššūkių yra susidūrimų, atsirandančių, kai dvi ar daugiau įvesties verčių sukuria tą pačią maišos vertę, tvarkymas. Susidūrimams išspręsti naudojami įvairūs būdai, įskaitant:
- Sujungimas: naudojant šią techniką, kiekvienoje maišos lentelės vietoje yra susietas visų reikšmių, turinčių tą pačią maišos reikšmę, sąrašas. Ši technika yra paprasta ir lengvai įgyvendinama, tačiau ji gali prastai veikti, kai susieti sąrašai tampa per ilgi.
- Atviras adresavimas: naudojant šią techniką, kai įvyksta susidūrimas, algoritmas ieško tuščio lizdo maišos lentelėje, tirdamas vienas po kito einančius tarpus, kol randama tuščia vieta. Šis metodas gali būti efektyvesnis nei grandinės sujungimas, kai apkrovos koeficientas yra mažas, tačiau jis gali sukelti grupes ir prastą veikimą, kai apkrovos koeficientas yra didelis.
- Dviguba maiša: tai atvirojo adresavimo variantas, kuris naudoja antrą maišos funkciją, kad nustatytų kitą lizdą, kurį reikia ištirti įvykus susidūrimui. Šis metodas gali padėti sumažinti grupavimą ir pagerinti našumą.
Susidūrimo raiškos pavyzdys
Tęskime 5 dydžio maišos lentelės pavyzdį. Norime maišos lentelėje išsaugoti raktų ir reikšmių poras „Jonas: 123456“ ir „Marija: 987654“. Abu klavišai sukuria tą patį maišos kodą 4, todėl įvyksta susidūrimas.
Norėdami išspręsti susidūrimą, galime naudoti grandininę funkciją. 4 indekse sukuriame susietą sąrašą ir į sąrašą įtraukiame raktų ir reikšmių poras. Maišos lentelė dabar atrodo taip:
js atsisiųsti
0:
1:
2:
3:
atributo klaida python
4: Jonas: 123456 -> Marija: 987654
5:
Maišos lentelė:
Maišos lentelė yra duomenų struktūra, kurioje duomenys saugomi masyve. Paprastai pasirenkamas masyvo dydis, didesnis nei elementų, kurie telpa maišos lentelėje, skaičius. Raktas susietas su indeksu masyve naudojant maišos funkciją.
Maišos funkcija naudojama norint rasti indeksą, kuriame elementas turi būti įterptas į maišos lentelę, kad būtų galima pridėti naują elementą. Elementas pridedamas prie to indekso, jei nėra susidūrimo. Jei įvyksta susidūrimas, susidūrimo skiriamosios gebos metodas naudojamas rasti kitą galimą masyvo lizdą.
Maišos funkcija naudojama norint rasti indeksą, kuriame saugomas elementas, kad būtų galima gauti jį iš maišos lentelės. Jei elementas tame indekse nerastas, elemento paieškai susietame sąraše (jei naudojamas grandinės nustatymas) arba kitame prieinamame lizde (jei naudojamas atvirasis adresavimas) naudojamas susidūrimo sprendimo metodas.
Maišos lentelės operacijos
Yra keletas operacijų, kurias galima atlikti maišos lentelėje, įskaitant:
- Įterpimas: naujos rakto-reikšmių poros įterpimas į maišos lentelę.
- Ištrynimas: rakto ir vertės poros pašalinimas iš maišos lentelės.
- Paieška: ieškoma rakto-reikšmių poros maišos lentelėje.
Maišos lentelės kūrimas:
Maiša dažnai naudojama kuriant maišos lenteles, kurios yra duomenų struktūros, leidžiančios greitai įterpti, ištrinti ir gauti duomenis. Viena ar daugiau raktų ir reikšmių porų gali būti saugomos kiekviename segmentų, sudarančių maišos lentelę, masyve.
Norėdami sukurti maišos lentelę, pirmiausia turime apibrėžti maišos funkciją, kuri kiekvieną raktą susieja su unikaliu masyvo indeksu. Paprasta maišos funkcija gali būti paimti rakto simbolių ASCII reikšmių sumą ir panaudoti likusią dalį, padalytą iš masyvo dydžio. Tačiau ši maišos funkcija yra neveiksminga ir gali sukelti susidūrimus (du raktai, susieti su tuo pačiu indeksu).
Norėdami išvengti susidūrimų, galime naudoti pažangesnes maišos funkcijas, kurios sukuria tolygesnį maišos reikšmių pasiskirstymą visame masyve. Vienas populiarus algoritmas yra djb2 maišos funkcija, kuri naudoja bitines operacijas maišos vertei generuoti:
unsigned long hash(char* str) { unsigned long hash = 5381; int c; while (c = *str++) { hash = ((hash << 5) + hash) + c; } return hash; } Ši maišos funkcija paima eilutę kaip įvestį ir grąžina nepasirašytą ilgo sveikojo skaičiaus maišos reikšmę. Funkcija inicijuoja 5381 maišos reikšmę, o tada kartoja kiekvieną eilutės simbolį, naudodama bitų operacijas, kad sukurtų naują maišos reikšmę. Grąžinama galutinė maišos reikšmė.
Maišos lentelės C++
C++ kalboje standartinė biblioteka pateikia maišos lentelės konteinerio klasę, vadinamą unordered_map. Konteineris unordered_map yra įdiegtas naudojant maišos lentelę ir suteikia greitą prieigą prie raktų ir reikšmių porų. Konteineris unordered_map naudoja maišos funkciją, kad apskaičiuotų raktų maišos kodą, o tada naudoja atvirą adresavimą, kad išspręstų susidūrimus.
Norėdami naudoti unordered_map konteinerį C++, turite įtraukti antraštės failą. Štai pavyzdys, kaip sukurti unordered_map konteinerį 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; } Paaiškinimas:
- Ši programa demonstruoja unordered_map konteinerio naudojimą C++ kalboje, kuris įgyvendinamas naudojant maišos lentelę ir suteikia greitą prieigą prie raktų-reikšmių porų.
- Pirma, programa apima reikalingus antraštės failus: ir.
- Tada programa sukuria tuščią unordered_map konteinerį, vadinamą my_map, kuriame yra eilutės raktai ir sveikųjų skaičių reikšmės. Tai atliekama naudojant sintaksę std::unordered_map my_map;
- Tada programa įterpia tris raktų ir reikšmių poras į „my_map“ konteinerį, naudodama operatorių []: „obuolys“, kurio vertė yra 10, „bananas“, kurios vertė yra 20, ir „oranžinė“, kurios vertė yra 30.
- Tai atliekama naudojant sintaksę mano_žemėlapis['obuolys'] = 10;, mano_žemėlapis['bananas'] = 20; ir mano_žemėlapis['oranžinė'] = 30; atitinkamai.
- Galiausiai programa išspausdina reikšmę, susietą su raktu „bananas“, naudodama operatorių [] ir objektą std::cout.
Programos išvestis:
kortele java
Duomenų įterpimas į maišos lentelę
Norėdami įterpti rakto-reikšmių porą į maišos lentelę, pirmiausia turime į masyvą įtraukti indeksą, kad būtų išsaugota rakto ir vertės pora. Jei kitas raktas susietas su tuo pačiu indeksu, susiduriame su susidūrimu ir turime jį tinkamai tvarkyti. Vienas įprastas būdas yra naudoti grandininę funkciją, kai kiekviename masyvo segmente yra susietas raktų ir reikšmių porų, turinčių tą pačią maišos vertę, sąrašas.
Štai pavyzdys, kaip įterpti rakto-reikšmių porą į maišos lentelę naudojant grandinę:
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; } } Paaiškinimas:
- Pirmiausia apibrėžiama struktūra, vadinama mazgu, kuri žymi vieną maišos lentelės mazgą.
- Kiekvienas mazgas turi tris narius: raktą char*, skirtą raktui saugoti, int reikšmę susijusiai reikšmei saugoti, ir žymeklį į kitą mazgą, kuris iškviečiamas šalia, kad tvarkytų susidūrimus maišos lentelėje, naudojant susietą sąrašą.
- Mazgų rodyklių masyvas, vadinamas hash_table, deklaruojamas 100 dydžio. Šis masyvas bus naudojamas maišos lentelės elementams saugoti.
- Įterpimo funkcija kaip parametrus paima char* klavišą ir int reikšmę.
- Jis pradedamas apskaičiuojant duoto rakto maišos reikšmę naudojant maišos funkciją, kuri, kaip manoma, yra apibrėžta kitur programoje.
- Tada maišos reikšmė sumažinama, kad tilptų į hash_table masyvo dydį, naudojant modulio operatorių % 100.
- Naujas mazgas sukuriamas naudojant dinaminį atminties paskirstymą (malloc(sizeof(node))), o jo nariai (raktas, reikšmė ir next) atitinkamai priskiriami pateiktu raktu, reikšme ir NULL.
- Jei atitinkamas lizdas hash_table masyve yra tuščias (NULL), o tai rodo, kad susidūrimo neįvyko, naujas mazgas tiesiogiai priskiriamas tam lizdui (hash_table[hash_value] = naujas_mazgas).
Tačiau jei masyve hash_table tame indekse jau yra mazgas, funkcija turi tvarkyti susidūrimą. Jis kerta susietą sąrašą, pradedant nuo dabartinio mazgo (hash_table[hash_value]) ir juda į kitą mazgą, kol pasiekia pabaigą (curr_node->next != NULL). Pasiekus sąrašo pabaigą, naujas mazgas pridedamas kaip kitas mazgas (curr_node->next = new_node).
Maišos diegimas C++:
Pažiūrėkime apie maišos diegimą C++, naudojant atvirą adresavimą ir linijinį susidūrimo skyrimo zondavimą. Įdiegsime maišos lentelę, kurioje saugomi sveikieji skaičiai.
#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;>