TechCodeview

Ievads par jaukšanu datu struktūrā:

Jaukšana ir populārs paņēmiens datorzinātnēs, kas ietver lielu datu kopu kartēšanu uz fiksēta garuma vērtībām. Tas ir process, kurā mainīga izmēra datu kopa tiek pārveidota par fiksēta izmēra datu kopu. Spēja veikt efektīvas uzmeklēšanas darbības padara jaukšanu par būtisku jēdzienu datu struktūrās.

Kas ir jaukšana?

Jaukšanas algoritms tiek izmantots, lai pārvērstu ievadi (piemēram, virkni vai veselu skaitli) fiksēta izmēra izvadē (saukta par jaucējkodu vai jaucējvērtību). Pēc tam dati tiek saglabāti un izgūti, izmantojot šo jaucējvērtību kā indeksu masīvā vai jaucēj tabulā. Jaucējfunkcijai jābūt deterministiskai, kas garantē, ka tā vienmēr dos tādu pašu rezultātu konkrētai ievadei.

Jaukšanu parasti izmanto, lai izveidotu unikālu datu identifikatoru, ko var izmantot, lai ātri meklētu šos datus lielā datu kopā. Piemēram, tīmekļa pārlūkprogramma var izmantot jaukšanu, lai droši saglabātu vietņu paroles. Kad lietotājs ievada savu paroli, pārlūkprogramma to pārvērš par jaucējvērtību un salīdzina to ar saglabāto jaucējvērtību, lai autentificētu lietotāju.

Kas ir hash atslēga?

Jaukšanas kontekstā jaukšanas atslēga (pazīstama arī kā jaucējvērtība vai jaucējkods) ir fiksēta izmēra skaitlisks vai burtciparu attēlojums, ko ģenerē jaukšanas algoritms. Tas tiek iegūts no ievades datiem, piemēram, teksta virknes vai faila, izmantojot procesu, kas pazīstams kā jaukšana.

Jaukšana ietver noteiktas matemātiskas funkcijas piemērošanu ievades datiem, kas rada unikālu jaucējatslēgu, kas parasti ir fiksēta garuma neatkarīgi no ievades lieluma. Iegūtā jaucējatslēga būtībā ir sākotnējo datu digitālais pirkstu nospiedums.

Jaukšanas atslēga kalpo vairākiem mērķiem. To parasti izmanto datu integritātes pārbaudēm, jo ​​pat nelielas izmaiņas ievaddatos radīs ievērojami atšķirīgu jaucējatslēgu. Jaucējatslēgas tiek izmantotas arī efektīvai datu izguvei un glabāšanai hash tabulās vai datu struktūrās, jo tās ļauj ātri meklēt un veikt salīdzināšanas darbības.

css treknrakstā

Kā darbojas jaukšana?

Jaukšanas procesu var iedalīt trīs posmos:

• Ievade: jaukšanai paredzētie dati tiek ievadīti jaukšanas algoritmā.
• Jaukšanas funkcija: jaukšanas algoritms ņem ievades datus un izmanto matemātisko funkciju, lai ģenerētu fiksēta izmēra jaukšanas vērtību. Jaucējfunkcija ir jāveido tā, lai dažādas ievades vērtības radītu dažādas jaucējvērtības, un nelielas izmaiņas ievadē radītu lielas izmaiņas izvadē.
• Izvade: tiek atgriezta jaucējvērtība, kas tiek izmantota kā indekss, lai saglabātu vai izgūtu datus datu struktūrā.

Jaukšanas algoritmi:

Ir daudz jaukšanas algoritmu, katram no kuriem ir atšķirīgas priekšrocības un trūkumi. Populārākie algoritmi ir šādi:

• MD5: plaši izmantots jaukšanas algoritms, kas rada 128 bitu jaukšanas vērtību.
• SHA-1: populārs jaukšanas algoritms, kas rada 160 bitu jaukšanas vērtību.
• SHA-256: drošāks jaukšanas algoritms, kas rada 256 bitu jaukšanas vērtību.

Jaucējfunkcija:

Jaucējfunkcija: jaucējfunkcija ir matemātiskas darbības veids, kas izmanto ievadi (vai taustiņu) un izvada fiksēta izmēra rezultātu, kas pazīstams kā jaucējkods vai jaucējvērtība. Lai jaucējfunkcija būtu deterministiska, vienai un tai pašai ievadei vienmēr ir jādod tāds pats jaucējkods. Turklāt jaucējfunkcijai ir jāizveido unikāls jaucējkods katrai ievadei, ko sauc par jaucējkodu.

Ir dažādi jaukšanas funkciju veidi, tostarp:

Sadalīšanas metode:

Šī metode ietver atslēgas dalīšanu ar tabulas lielumu un atlikušās daļas ņemšanu kā jaucējvērtību. Piemēram, ja tabulas izmērs ir 10 un atslēga ir 23, jaucējvērtība būtu 3 (23 % 10 = 3).

Reizināšanas metode:

Šī metode ietver atslēgas reizināšanu ar konstanti un produkta daļējās daļas ņemšanu kā jaucējvērtību. Piemēram, ja atslēga ir 23 un konstante ir 0,618, jaucējvērtība būtu 2 (floor(10*(0,61823 - floor(0,61823))) = floor(2,236) = 2).

štati ASV

Universālā jaukšana:

Šī metode ietver nejaušas jaucējfunkcijas izmantošanu no jaukšanas funkciju saimes. Tas nodrošina, ka jaucējfunkcija nav novirzīta uz kādu konkrētu ievadi un ir izturīga pret uzbrukumiem.

Sadursmes izšķirtspēja

Viens no galvenajiem izaicinājumiem jaukšanā ir sadursmju apstrāde, kas rodas, ja divas vai vairākas ievades vērtības rada vienādu jaucējvērtību. Sadursmju novēršanai tiek izmantotas dažādas metodes, tostarp:

• Ķēdēšana: izmantojot šo paņēmienu, katrā hash tabulas slotā ir saistīts saraksts ar visām vērtībām, kurām ir vienāda jaucējvērtība. Šis paņēmiens ir vienkāršs un viegli īstenojams, taču tas var izraisīt sliktu veiktspēju, ja saistītie saraksti kļūst pārāk gari.
• Atvērtā adresēšana: šajā tehnikā, kad notiek sadursme, algoritms meklē tukšu slotu jaucēj tabulā, pārbaudot secīgus slotus, līdz tiek atrasts tukšs slots. Šis paņēmiens var būt efektīvāks par ķēdes pievienošanu, ja slodzes koeficients ir zems, taču tas var izraisīt klasterizāciju un sliktu veiktspēju, ja slodzes koeficients ir augsts.
• Dubultā jaukšana: šī ir atvērtās adresācijas variācija, kas izmanto otro jaukšanas funkciju, lai noteiktu nākamo slotu, kas jāpārbauda sadursmes gadījumā. Šī metode var palīdzēt samazināt klasteru veidošanos un uzlabot veiktspēju.

Sadursmes izšķirtspējas piemērs

Turpināsim ar mūsu piemēru par jaukšanas tabulu ar izmēru 5. Mēs vēlamies jaucēj tabulā saglabāt atslēgu-vērtību pārus “Jānis: 123456” un “Mērija: 987654”. Abas atslēgas rada to pašu jaucējkodu 4, tāpēc notiek sadursme.

Mēs varam izmantot ķēdi, lai atrisinātu sadursmi. Mēs izveidojam saistīto sarakstu 4. rādītājā un pievienojam atslēgu un vērtību pārus sarakstam. Jauktā tabula tagad izskatās šādi:

0:

1:

numpy meshgrid

2:

3:

4: Jānis: 123456 -> Marija: 987654

5:

Hash tabula:

Jauktabula ir datu struktūra, kas glabā datus masīvā. Parasti tiek atlasīts masīva izmērs, kas ir lielāks par elementu skaitu, ko var ievietot jaukšanas tabulā. Atslēga tiek kartēta uz indeksu masīvā, izmantojot jaucējfunkciju.

Jaucējfunkcija tiek izmantota, lai atrastu indeksu, kur elements ir jāievieto jaukšanas tabulā, lai pievienotu jaunu elementu. Elements tiek pievienots šim indeksam, ja nenotiek sadursme. Ja notiek sadursme, tiek izmantota sadursmes izšķirtspējas metode, lai atrastu nākamo pieejamo slotu masīvā.

binārā koka šķērsošana

Jaucējfunkciju izmanto, lai atrastu indeksu, kurā elements tiek glabāts, lai izgūtu to no hash tabulas. Ja elements šajā indeksā netiek atrasts, elementa meklēšanai saistītajā sarakstā (ja tiek izmantota ķēde) vai nākamajā pieejamajā slotā (ja tiek izmantota atvērtā adresācija) tiek izmantota sadursmes izšķiršanas metode.

Hash tabulas darbības

Ir vairākas darbības, ko var veikt hash tabulā, tostarp:

• Ievietošana: jauna atslēgas-vērtības pāra ievietošana hash tabulā.
• Dzēšana: atslēgas-vērtības pāra noņemšana no hash tabulas.
• Meklēt: jaucēj tabulā tiek meklēts atslēgas-vērtības pāris.

Hash tabulas izveide:

Jaukšanu bieži izmanto, lai izveidotu jaucējtabulas, kas ir datu struktūras, kas nodrošina ātru datu ievietošanu, dzēšanu un izgūšanu. Katrā segmentu masīvā, kas veido jaukšanas tabulu, var saglabāt vienu vai vairākus atslēgu-vērtību pārus.

Lai izveidotu hash tabulu, mums vispirms ir jādefinē jaucējfunkcija, kas katru atslēgu kartē unikāls masīva indekss. Vienkārša jaukšanas funkcija varētu būt atslēgas rakstzīmju ASCII vērtību summa un izmantot atlikušo daļu, dalītu ar masīva lielumu. Tomēr šī jaucējfunkcija ir neefektīva un var izraisīt sadursmes (divas atslēgas, kas tiek piesaistītas vienam indeksam).

Lai izvairītos no sadursmēm, mēs varam izmantot uzlabotas jaucējfunkcijas, kas nodrošina vienmērīgāku jaucējvērtību sadalījumu visā masīvā. Viens populārs algoritms ir djb2 jaucējfunkcija, kas izmanto bitu darbības, lai ģenerētu jaucējvērtību:

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

Šī jaucējfunkcija izmanto virkni kā ievadi un atgriež neparakstītu garu veselu jaucējvērtību. Funkcija inicializē jaucējvērtību 5381 un pēc tam atkārto katru virknes rakstzīmi, izmantojot bitu darbības, lai ģenerētu jaunu jaucējvērtību. Tiek atgriezta galīgā jaucējvērtība.

Hash tabulas C++ valodā

Programmā C++ standarta bibliotēka nodrošina hash tabulas konteinera klasi ar nosaukumu unordered_map. Konteiners unordered_map ir ieviests, izmantojot hash tabulu, un nodrošina ātru piekļuvi atslēgu un vērtību pāriem. Konteiners unordered_map izmanto jaucējfunkciju, lai aprēķinātu atslēgu jaucējkodu, un pēc tam izmanto atvērto adresēšanu, lai atrisinātu sadursmes.

Lai izmantotu unordered_map konteineru programmā C++, ir jāiekļauj galvenes fails. Šeit ir piemērs, kā izveidot unordered_map konteineru programmā C++:

kas ir reģistrs sql

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

Paskaidrojums:

• Šī programma demonstrē konteinera unordered_map izmantošanu C++ valodā, kas tiek ieviests, izmantojot jaucējtabulu un nodrošina ātru piekļuvi atslēgu-vērtību pāriem.
• Pirmkārt, programmā ir iekļauti nepieciešamie galvenes faili: un.
• Pēc tam programma izveido tukšu unordered_map konteineru ar nosaukumu my_map, kurā ir virknes atslēgas un veselu skaitļu vērtības. Tas tiek darīts, izmantojot sintaksi std::unordered_map my_map;
• Pēc tam programma ievieto trīs atslēgu vērtību pārus my_map konteinerā, izmantojot operatoru []: 'ābols' ar vērtību 10, 'banāns' ar vērtību 20 un 'apelsīns' ar vērtību 30.
• Tas tiek darīts, izmantojot sintaksi mana_karte['ābols'] = 10;, mana_karte['banāns'] = 20; un mana_karte['oranžs'] = 30; attiecīgi.
• Visbeidzot, programma izdrukā vērtību, kas saistīta ar taustiņu 'banāns', izmantojot operatoru [] un objektu std::cout.

Programmas izvade:

Datu ievietošana hash tabulā

Lai ievietotu atslēgu-vērtību pāri jaukšanas tabulā, vispirms masīvā ir jāiekļauj indekss, lai saglabātu atslēgu un vērtību pāri. Ja cita atslēga tiek saistīta ar to pašu indeksu, notiek sadursme un tā ir jārīkojas atbilstoši. Viena izplatīta metode ir ķēdes izmantošana, kur katrs masīva segments satur saistītu atslēgu un vērtību pāru sarakstu, kuriem ir vienāda jaucējvērtība.

Šeit ir piemērs, kā ievietot atslēgu-vērtību pāri jaukšanas tabulā, izmantojot ķēdi.

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

Paskaidrojums:

• Pirmkārt, tiek definēta struktūra, ko sauc par mezglu, kas ir viens mezgls hash tabulā.
• Katram mezglam ir trīs dalībnieki: atslēga char*, lai saglabātu atslēgu, int vērtība, lai saglabātu saistīto vērtību, un rādītājs uz citu mezglu, kas tiek izsaukts blakus, lai apstrādātu sadursmes hash tabulā, izmantojot saistīto sarakstu.
• Mezglu rādītāju masīvs, ko sauc par hash_table, ir deklarēts ar izmēru 100. Šis masīvs tiks izmantots, lai saglabātu jaucēj tabulas elementus.
• Ievietošanas funkcija kā parametrus izmanto taustiņu char* un int vērtību.
• Tas sākas ar jaucējvērtības aprēķināšanu dotajai atslēgai, izmantojot jaucējfunkciju, kas tiek pieņemts, ka tā ir definēta citur programmā.
• Pēc tam jaucējvērtība tiek samazināta, lai ietilptu masīva hash_table izmērā, izmantojot moduļa operatoru % 100.
• Jauns mezgls tiek izveidots, izmantojot dinamisko atmiņas piešķiršanu (malloc(sizeof(node))), un tā dalībnieki (atslēga, vērtība un next) tiek piešķirti attiecīgi ar norādīto atslēgu, vērtību un NULL.
• Ja atbilstošais slots hash_table masīvā ir tukšs (NULL), norādot, ka sadursme nav notikusi, jaunais mezgls tiek tieši piešķirts šim slotam (hash_table[hash_value] = new_node).

Tomēr, ja šajā indeksā masīvā hash_table jau ir mezgls, funkcijai ir jārisina sadursme. Tas šķērso saistīto sarakstu, sākot no pašreizējā mezgla (hash_table[hash_value]) un pārvietojas uz nākamo mezglu, līdz tas sasniedz beigas (curr_node->next != NULL). Kad ir sasniegts saraksta beigas, jaunais mezgls tiek pievienots kā nākamais mezgls (curr_node->next = new_node).

Jaukšanas ieviešana programmā C++:

Apskatīsim jaukšanas ieviešanu programmā C++, izmantojot atklāto adresāciju un lineāro zondēšanu sadursmes izšķiršanai. Mēs ieviesīsim hash tabulu, kurā tiek saglabāti veseli skaitļi.

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