Tietorakenteen hajautus:
Hashing on suosittu tietotekniikan tekniikka, johon liittyy suurten tietojoukkojen kartoittaminen kiinteän pituisiin arvoihin. Se on prosessi, jossa muuttuvan kokoinen tietojoukko muunnetaan kiinteän kokoiseksi tietojoukoksi. Kyky suorittaa tehokkaita hakutoimintoja tekee hajauttamisesta olennaisen käsitteen tietorakenteissa.
Mitä hashing on?
Hajautusalgoritmia käytetään syötteen (kuten merkkijonon tai kokonaisluvun) muuntamiseen kiinteän kokoiseksi tulosteeksi (jota kutsutaan hash-koodiksi tai hash-arvoksi). Tiedot tallennetaan ja haetaan käyttämällä tätä hash-arvoa indeksinä taulukossa tai hash-taulukossa. Hajautusfunktion tulee olla deterministinen, mikä takaa, että se antaa aina saman tuloksen tietylle syötteelle.
Hashingia käytetään yleisesti luomaan tiedolle yksilöllinen tunniste, jota voidaan käyttää tietojen nopeaan etsimiseen suuresta tietojoukosta. Esimerkiksi verkkoselain voi käyttää tiivistystä tallentaakseen verkkosivustojen salasanat turvallisesti. Kun käyttäjä syöttää salasanansa, selain muuntaa sen hash-arvoksi ja vertaa sitä tallennettuun hash-arvoon käyttäjän todentamiseksi.
Mikä on hash-avain?
Hajautuksen yhteydessä hash-avain (tunnetaan myös tiivistearvona tai hash-koodina) on kiinteäkokoinen numeerinen tai aakkosnumeerinen esitys, joka on luotu hajautusalgoritmin avulla. Se johdetaan syöttötiedoista, kuten tekstimerkkijonosta tai tiedostosta, hajautusprosessin kautta.
Hashing sisältää tietyn matemaattisen funktion soveltamisen syöttötietoihin, mikä tuottaa ainutlaatuisen hajautusavaimen, joka on tyypillisesti kiinteäpituinen riippumatta syötteen koosta. Tuloksena oleva hash-avain on pohjimmiltaan alkuperäisen tiedon digitaalinen sormenjälki.
Hash-avaimella on useita tarkoituksia. Sitä käytetään yleisesti tietojen eheyden tarkistuksiin, koska pienikin muutos syöttötiedoissa tuottaa merkittävästi erilaisen hash-avaimen. Hash-avaimia käytetään myös tehokkaaseen tietojen hakuun ja tallentamiseen hash-taulukoihin tai tietorakenteisiin, koska ne mahdollistavat nopean haun ja vertailun.
java silmukat
Kuinka hajautus toimii?
Hajautusprosessi voidaan jakaa kolmeen vaiheeseen:
- Syöte: Hajautettavat tiedot syötetään hajautusalgoritmiin.
- Hash-funktio: Hajautusalgoritmi ottaa syötetiedot ja käyttää matemaattista funktiota kiinteän koon hajautusarvon luomiseksi. Hajautusfunktio tulee suunnitella siten, että eri syötearvot tuottavat erilaisia hash-arvoja ja pienet muutokset syötteessä aiheuttavat suuria muutoksia lähdössä.
- Tulos: Palautetaan hash-arvo, jota käytetään hakemistona tietojen tallentamiseen tai hakemiseen tietorakenteessa.
Hajautusalgoritmit:
On olemassa lukuisia hajautusalgoritmeja, joista jokaisella on omat edut ja haitat. Suosituimpia algoritmeja ovat seuraavat:
- MD5: Laajalti käytetty hajautusalgoritmi, joka tuottaa 128-bittisen hajautusarvon.
- SHA-1: Suosittu hajautusalgoritmi, joka tuottaa 160-bittisen hajautusarvon.
- SHA-256: Turvallisempi hajautusalgoritmi, joka tuottaa 256-bittisen hajautusarvon.
Hash-funktio:
Hash-funktio: Hash-funktio on eräänlainen matemaattinen toiminto, joka ottaa syötteen (tai näppäimen) ja tulostaa kiinteän kokoisen tuloksen, joka tunnetaan hash-koodina tai hash-arvona. Hajautusfunktion on aina annettava sama hash-koodi samalle syötteelle, jotta se olisi deterministinen. Lisäksi hajautusfunktion tulisi tuottaa jokaiselle syötteelle ainutlaatuinen hash-koodi, joka tunnetaan nimellä hash-ominaisuus.
Hajautusfunktioita on erilaisia, mukaan lukien:
Tässä menetelmässä avain jaetaan taulukon koolla ja jäännös otetaan hash-arvoksi. Jos taulukon koko on esimerkiksi 10 ja avain on 23, hash-arvo olisi 3 (23 % 10 = 3).
Tässä menetelmässä avain kerrotaan vakiolla ja tuotteen murto-osa otetaan hash-arvoksi. Jos avain on esimerkiksi 23 ja vakio on 0,618, hash-arvo olisi 2 (floor(10*(0,61823 - floor(0,61823))) = floor(2,236) = 2).
"eulerin numero javassa"
Tämä menetelmä sisältää satunnaisen hash-funktion käytön hash-funktioiden perheestä. Tämä varmistaa, että hash-toiminto ei ole vinoutunut mihinkään tiettyyn syötteeseen ja on vastustuskykyinen hyökkäyksille.
Törmäysresoluutio
Yksi tiivistyksen suurimmista haasteista on törmäysten käsittely, joita tapahtuu, kun kaksi tai useampi syötearvo tuottaa saman hajautusarvon. Törmäysten ratkaisemiseen käytetään erilaisia tekniikoita, mukaan lukien:
- Ketjutus: Tässä tekniikassa jokainen hash-taulukon paikka sisältää linkitetyn luettelon kaikista arvoista, joilla on sama hash-arvo. Tämä tekniikka on yksinkertainen ja helppo toteuttaa, mutta se voi johtaa huonoon suorituskykyyn, jos linkitetyistä luetteloista tulee liian pitkiä.
- Avoin osoitus: Tässä tekniikassa, kun törmäys tapahtuu, algoritmi etsii tyhjää paikkaa hash-taulukosta tutkimalla peräkkäisiä aikavälejä, kunnes tyhjä aikaväli löytyy. Tämä tekniikka voi olla tehokkaampi kuin ketjuttaminen, kun kuormituskerroin on alhainen, mutta se voi johtaa klusteroitumiseen ja huonoon suorituskykyyn, kun kuormituskerroin on korkea.
- Kaksoistiivistys: Tämä on muunnelma avoimesta osoitteesta, joka käyttää toista hajautustoimintoa määrittääkseen seuraavan välin, joka tutkitaan törmäyksen sattuessa. Tämä tekniikka voi auttaa vähentämään klusteroitumista ja parantamaan suorituskykyä.
Esimerkki törmäysresoluutiosta
Jatketaan esimerkkiä tiivistetaulukosta, jonka koko on 5. Haluamme tallentaa avainarvoparit 'John: 123456' ja 'Maria: 987654' hash-taulukkoon. Molemmat avaimet tuottavat saman hash-koodin 4, joten törmäys tapahtuu.
Voimme käyttää ketjutusta ratkaisemaan törmäyksen. Luomme linkitetyn luettelon indeksiin 4 ja lisäämme avainarvoparit luetteloon. Hash-taulukko näyttää nyt tältä:
0:
1:
java luettelo
2:
3:
4: John: 123456 -> Mary: 987654
5:
Hash-taulukko:
Hajautustaulukko on tietorakenne, joka tallentaa tiedot taulukkoon. Tyypillisesti taulukolle valitaan koko, joka on suurempi kuin hajautustaulukkoon mahtuvien elementtien määrä. Avain kartoitetaan taulukon indeksiin hash-funktiolla.
Hajautusfunktiota käytetään etsimään indeksi, johon elementti on lisättävä hash-taulukkoon, jotta uusi elementti voidaan lisätä. Elementti lisätään kyseiseen indeksiin, jos törmäystä ei tapahdu. Jos törmäys tapahtuu, törmäysresoluutiomenetelmää käytetään taulukon seuraavan vapaan paikan etsimiseen.
mikä on 10/60
Hajautusfunktiota käytetään paikantamaan indeksi, johon elementti on tallennettu, jotta se voidaan hakea hash-taulukosta. Jos elementtiä ei löydy kyseisestä indeksistä, törmäysratkaisumenetelmää käytetään elementin etsimiseen linkitetystä listasta (jos käytetään ketjutusta) tai seuraavasta vapaasta paikasta (jos käytetään avointa osoitusta).
Hash-taulukon toiminnot
Hajautustaulukossa voidaan suorittaa useita toimintoja, mukaan lukien:
- Lisäys: Uuden avain-arvo-parin lisääminen hash-taulukkoon.
- Poistaminen: avain-arvo-parin poistaminen hash-taulukosta.
- Haku: Etsitään avainarvo-paria hash-taulukosta.
Hash-taulukon luominen:
Tiivistystä käytetään usein hajautustaulukoiden rakentamiseen, jotka ovat tietorakenteita, jotka mahdollistavat nopean tietojen lisäämisen, poistamisen ja noudon. Yksi tai useampi avain-arvo-pari voidaan tallentaa kuhunkin tiivistetaulukon muodostaviin ryhmiin.
Hajautustaulukon luomiseksi meidän on ensin määritettävä hash-funktio, joka yhdistää jokaisen avaimen taulukon ainutlaatuiseen indeksiin. Yksinkertainen hash-funktio voisi olla ottaa avaimen merkkien ASCII-arvojen summa ja käyttää jäännöstä jaettuna taulukon koolla. Tämä hash-toiminto on kuitenkin tehoton ja voi johtaa törmäyksiin (kaksi avainta, jotka liittyvät samaan indeksiin).
Törmäysten välttämiseksi voimme käyttää edistyneempiä hajautusfunktioita, jotka tuottavat tasaisemman hajautusarvojen jakautumisen taulukossa. Yksi suosittu algoritmi on djb2 hash-funktio, joka käyttää bittikohtaisia operaatioita hajautusarvon luomiseen:
unsigned long hash(char* str) { unsigned long hash = 5381; int c; while (c = *str++) { hash = ((hash << 5) + hash) + c; } return hash; } Tämä hash-funktio ottaa syötteenä merkkijonon ja palauttaa etumerkittömän pitkän kokonaisluvun hash-arvon. Funktio alustaa hajautusarvon 5381 ja iteroi sitten merkkijonon jokaisen merkin yli käyttämällä bittikohtaisia toimintoja uuden hajautusarvon luomiseksi. Lopullinen hash-arvo palautetaan.
Hash-taulukot C++:ssa
C++:ssa vakiokirjasto tarjoaa hash-taulukon säilön luokan nimeltä unordered_map. Unordered_map-säilö on toteutettu hash-taulukon avulla ja tarjoaa nopean pääsyn avainarvo-pareihin. Unordered_map-säilö käyttää hash-funktiota avainten hash-koodin laskemiseen ja käyttää sitten avointa osoitetta törmäysten ratkaisemiseen.
Jotta voit käyttää unordered_map-säilöä C++:ssa, sinun on sisällytettävä otsikkotiedosto. Tässä on esimerkki unordered_map-säilön luomisesta C++:ssa:
roomalainen numero 1-100
#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; } Selitys:
- Tämä ohjelma esittelee unordered_map-säilön käyttöä C++:ssa, joka on toteutettu hash-taulukolla ja tarjoaa nopean pääsyn avainarvo-pareihin.
- Ensinnäkin ohjelma sisältää tarvittavat otsikkotiedostot: and.
- Sitten ohjelma luo tyhjän unordered_map-säilön nimeltä my_map, jossa on merkkijonoavaimet ja kokonaislukuarvot. Tämä tehdään käyttämällä syntaksia std::unordered_map my_map;
- Seuraavaksi ohjelma lisää kolme avainarvoparia my_map-säilöön käyttämällä []-operaattoria: 'omena' arvolla 10, 'banaani' arvolla 20 ja 'oranssi' arvolla 30.
- Tämä tehdään käyttämällä syntaksia my_map['omena'] = 10;, oma_kartta['banaani'] = 20; ja oma_kartta['oranssi'] = 30; vastaavasti.
- Lopuksi ohjelma tulostaa 'banaani'-avaimeen liittyvän arvon käyttämällä []-operaattoria ja std::cout-objektia.
Ohjelman lähtö:
Tietojen lisääminen hash-taulukkoon
Jos haluat lisätä avainarvo-parin hash-taulukkoon, meidän on ensin liitettävä taulukkoon indeksi avain-arvo-parin tallentamiseksi. Jos toinen avain liittyy samaan hakemistoon, meillä on törmäys ja meidän on käsiteltävä sitä asianmukaisesti. Yksi yleinen tapa on käyttää ketjutusta, jossa jokainen taulukon segmentti sisältää linkitetyn luettelon avainarvopareista, joilla on sama hash-arvo.
Tässä on esimerkki avain-arvo-parin lisäämisestä hash-taulukkoon ketjutuksen avulla:
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; } } Selitys:
- Ensin määritellään solmuksi kutsuttu rakenne, joka edustaa yhtä solmua hash-taulukossa.
- Jokaisessa solmussa on kolme jäsentä: char*-avain avaimen tallentamiseen, int-arvo liittyvän arvon tallentamiseen ja osoitin toiseen solmuun, jota kutsutaan seuraavaksi käsittelemään törmäyksiä hash-taulukossa linkitetyn luettelon avulla.
- Hash_table-niminen solmuosoittimien joukko on ilmoitettu kooltaan 100. Tätä taulukkoa käytetään hash-taulukon elementtien tallentamiseen.
- Lisää-toiminto ottaa parametreiksi char*-näppäimen ja int-arvon.
- Se alkaa laskemalla hajautusarvo annetulle avaimelle hash-funktiolla, jonka oletetaan olevan määritelty muualla ohjelmassa.
- Hajautusarvoa pienennetään sitten sopimaan hash_table-taulukon kokoon käyttämällä moduulioperaattoria % 100.
- Uusi solmu luodaan käyttämällä dynaamista muistin varausta (malloc(sizeof(node))), ja sen jäsenille (avain, arvo ja next) määritetään annetut avaimet, arvot ja NULL.
- Jos vastaava väli hash_table-taulukossa on tyhjä (NULL), mikä osoittaa, ettei törmäystä ole tapahtunut, uusi solmu osoitetaan suoraan kyseiseen paikkaan (hash_table[hash_value] = uusi_solmu).
Kuitenkin, jos kyseisessä indeksissä on jo solmu hash_table-taulukossa, funktion on käsiteltävä törmäys. Se kulkee linkitetyn luettelon läpi alkaen nykyisestä solmusta (hash_table[hash_value]) ja siirtyy seuraavaan solmuun, kunnes se saavuttaa sen loppuun (curr_node->next != NULL). Kun luettelon loppu on saavutettu, uusi solmu lisätään seuraavaksi solmuksi (curr_node->next = new_node).
Hashingin käyttöönotto C++:ssa:
Katsotaanpa tiivistyksen toteutusta C++:ssa käyttämällä avointa osoitusta ja lineaarista luotausta törmäysresoluutioon. Toteutamme hash-taulukon, joka tallentaa kokonaisluvut.
#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;>