TechCodeview

Bevezetés a kivonatolásba az adatszerkezetben:

A kivonatolás egy népszerű technika a számítástechnikában, amely magában foglalja a nagy adatkészletek rögzített hosszúságú értékekre való leképezését. Ez egy változó méretű adatkészlet fix méretű adatkészletté való konvertálásának folyamata. A hatékony keresési műveletek végrehajtásának képessége a kivonatolást alapvető fogalommá teszi az adatstruktúrákban.

Mi az a Hashing?

A hash algoritmus segítségével egy bemenetet (például karakterláncot vagy egész számot) fix méretű kimenetté alakítanak át (ezt hash kódnak vagy hash értéknek nevezik). Az adatokat ezután eltárolja és lekéri, ezzel a hash értékkel indexként egy tömbben vagy hash táblában. A hash függvénynek determinisztikusnak kell lennie, ami garantálja, hogy adott bemenetre mindig ugyanazt az eredményt adja.

A kivonatolást általában egy adatrész egyedi azonosítójának létrehozására használják, amellyel gyorsan megkereshetők az adatok egy nagy adatkészletben. Például egy webböngésző hash-t használhat a webhelyjelszavak biztonságos tárolására. Amikor a felhasználó beírja jelszavát, a böngésző azt hash értékké alakítja, és összehasonlítja a tárolt hash értékkel a felhasználó hitelesítése érdekében.

Mi az a hash kulcs?

A kivonatolás összefüggésében a hash kulcs (más néven hash érték vagy hash kód) egy kivonatoló algoritmus által generált rögzített méretű numerikus vagy alfanumerikus ábrázolás. A bemeneti adatokból, például egy szöveges karakterláncból vagy egy fájlból származik, egy hash-nek nevezett folyamaton keresztül.

A kivonatolás során egy adott matematikai függvényt alkalmaznak a bemeneti adatokra, amely egyedi hash kulcsot hoz létre, amely jellemzően rögzített hosszúságú, függetlenül a bemenet méretétől. Az eredményül kapott hash kulcs lényegében az eredeti adatok digitális ujjlenyomata.

A hash kulcs több célt szolgál. Általában adatintegritás-ellenőrzésre használják, mivel a bemeneti adatok kis változtatása is jelentősen eltérő hash kulcsot eredményez. A hash kulcsokat hatékony adatlekérésre és hash táblákban vagy adatstruktúrákban való tárolásra is használják, mivel lehetővé teszik a gyors keresést és összehasonlítást.

Hogyan működik a kivonatolás?

A kivonatolás folyamata három lépésre bontható:

• Bemenet: A kivonatolni kívánt adatok bekerülnek a kivonatoló algoritmusba.
• Kivonatolási függvény: A kivonatoló algoritmus veszi a bemeneti adatokat, és matematikai függvényt alkalmaz egy rögzített méretű hash érték létrehozásához. A hash függvényt úgy kell megtervezni, hogy a különböző bemeneti értékek különböző hash értékeket adjanak, és a bemenet kis változásai nagy változásokat okozzanak a kimenetben.
• Kimenet: A hash értéket adja vissza, amelyet indexként használnak az adatok tárolására vagy lekérésére egy adatstruktúrában.

Kivonatolási algoritmusok:

Számos kivonatolási algoritmus létezik, mindegyiknek külön előnyei és hátrányai vannak. A legnépszerűbb algoritmusok a következők:

• MD5: Széles körben használt hash algoritmus, amely 128 bites hash értéket állít elő.
• SHA-1: Népszerű kivonatoló algoritmus, amely 160 bites hash értéket állít elő.
• SHA-256: Biztonságosabb kivonatolási algoritmus, amely 256 bites hash értéket állít elő.

Hash függvény:

Hash függvény: A hash függvény egyfajta matematikai művelet, amely egy bemenetet (vagy kulcsot) vesz fel, és egy rögzített méretű eredményt ad ki, amelyet hash kódnak vagy hash értéknek nevezünk. A hash függvénynek mindig ugyanazt a hash kódot kell adnia ugyanahhoz a bemenethez, hogy determinisztikus legyen. Ezenkívül a hash függvénynek egyedi hash kódot kell létrehoznia minden egyes bemenethez, amelyet hash tulajdonságnak nevezünk.

A karakterlánc java-t tartalmaz

Különféle típusú hash-függvények léteznek, többek között:

Osztási módszer:

Ez a módszer abból áll, hogy a kulcsot elosztjuk a táblázat méretével, és a maradékot hash értékként veszik. Például, ha a táblázat mérete 10, a kulcs pedig 23, akkor a hash értéke 3 (23 % 10 = 3).

Szorzási módszer:

Ez a módszer abból áll, hogy a kulcsot megszorozzuk egy konstanssal, és a szorzat tört részét veszi hash értéknek. Például, ha a kulcs 23, a konstans pedig 0,618, akkor a hash értéke 2 lesz (floor(10*(0,61823 - floor(0,61823))) = floor(2,236) = 2).

Univerzális kivonatolás:

Ez a módszer egy véletlenszerű hash függvény használatát foglalja magában a hash függvények családjából. Ez biztosítja, hogy a hash függvény ne legyen torzítva semmilyen adott bemenet felé, és ellenálljon a támadásoknak.

Ütközésfelbontás

A kivonatolás egyik fő kihívása az ütközések kezelése, amelyek akkor fordulnak elő, ha két vagy több bemeneti érték ugyanazt a hash értéket állítja elő. Különféle technikákat használnak az ütközések megoldására, többek között:

• Láncolás: Ennél a technikánál minden hash tábla slot tartalmaz egy linkelt listát az összes olyan értékről, amelyek azonos hash értékkel rendelkeznek. Ez a technika egyszerű és könnyen megvalósítható, de gyenge teljesítményhez vezethet, ha a hivatkozott listák túl hosszúak lesznek.
• Nyílt címzés: Ennél a technikánál ütközés esetén az algoritmus üres helyet keres a hash-táblázatban úgy, hogy az egymást követő réseket vizsgálja, amíg üres helyet nem talál. Ez a technika alacsony terhelési tényező esetén hatékonyabb lehet, mint a láncolás, de magas terhelési tényező esetén klaszterezéshez és gyenge teljesítményhez vezethet.
• Kettős hash: Ez a nyílt címzés egy olyan változata, amely egy második hash függvényt használ annak meghatározására, hogy ütközés esetén melyik szakaszt kell vizsgálni. Ez a technika segíthet csökkenteni a klaszterezést és javítani a teljesítményt.

Példa az ütközésfeloldásra

Folytassuk példánkat egy 5-ös hash-táblázattal. A „János: 123456” és a „Mária: 987654” kulcs-érték párokat a hash-táblázatban szeretnénk tárolni. Mindkét kulcs ugyanazt a 4-es hash kódot állítja elő, így ütközés történik.

Láncolást használhatunk az ütközés megoldására. A 4. indexnél létrehozunk egy linkelt listát, és hozzáadjuk a kulcs-érték párokat a listához. A hash táblázat most így néz ki:

0:

hangya vs maven

1:

2:

3:

4: János: 123456 -> Mária: 987654

5:

Hash táblázat:

A hash tábla olyan adatstruktúra, amely egy tömbben tárolja az adatokat. Általában a tömb mérete nagyobb, mint a hash táblában elférő elemek száma. A kulcs a tömbben lévő indexhez van leképezve a hash függvény segítségével.

A hash függvény arra szolgál, hogy megkeresse az indexet, ahol egy elemet be kell illeszteni a hash-táblázatba, hogy új elemet adjon hozzá. Az elem hozzáadódik ehhez az indexhez, ha nincs ütközés. Ha ütközés történik, az ütközésfeloldási módszert használja a tömb következő elérhető nyílásának megkeresésére.

A hash függvény az elem tárolt indexének megkeresésére szolgál, hogy lekérje azt a hash táblából. Ha az elem nem található ezen az indexen, az ütközésfeloldási módszerrel keresi az elemet a csatolt listában (ha láncolást használ) vagy a következő elérhető résben (ha nyílt címzést használ).

Hash tábla műveletek

Számos műveletet lehet végrehajtani egy hash táblán, többek között:

• Beszúrás: Új kulcs-érték pár beillesztése a hash táblába.
• Törlés: Kulcs-érték pár eltávolítása a hash táblából.
• Keresés: Kulcs-érték pár keresése a hash táblában.

Hash tábla létrehozása:

A kivonatolást gyakran használják hash-táblázatok készítésére, amelyek olyan adatstruktúrák, amelyek lehetővé teszik az adatok gyors beillesztését, törlését és visszakeresését. Egy vagy több kulcs-érték pár tárolható a hash táblát alkotó gyűjtők mindegyikében.

Hash-tábla létrehozásához először meg kell határoznunk egy hash-függvényt, amely minden kulcsot leképez egy egyedi indexre a tömbben. Egy egyszerű hash-függvény lehet a kulcsban lévő karakterek ASCII-értékeinek összege, és a maradék felhasználása, ha elosztjuk a tömb méretével. Ez a hash funkció azonban nem hatékony, és ütközésekhez vezethet (két kulcs, amelyek ugyanarra az indexre vannak leképezve).

Az ütközések elkerülése érdekében fejlettebb hash függvényeket használhatunk, amelyek a hash értékek egyenletesebb eloszlását eredményezik a tömbben. Az egyik népszerű algoritmus a djb2 hash függvény, amely bitenkénti műveleteket használ a hash érték létrehozásához:

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

Ez a hash függvény egy karakterláncot vesz be bemenetként, és egy előjel nélküli hosszú egész hash értéket ad vissza. A függvény inicializálja az 5381-es hash értéket, majd a karakterlánc minden egyes karakterén át iterál, bitenkénti műveletek segítségével új hash értéket generál. A végső hash érték kerül visszaadásra.

Hash táblák C++ nyelven

A C++ nyelven a szabványos könyvtár egy unordered_map nevű hash tábla tároló osztályt biztosít. Az unordered_map tároló egy hash tábla segítségével valósul meg, és gyors hozzáférést biztosít a kulcs-érték párokhoz. Az unordered_map tároló egy hash függvényt használ a kulcsok hash kódjának kiszámításához, majd nyílt címzést használ az ütközések feloldására.

Az unordered_map konténer C++ nyelven való használatához hozzá kell adni a fejlécfájlt. Íme egy példa egy unordered_map tároló létrehozására C++ nyelven:

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

Magyarázat:

• Ez a program bemutatja az unordered_map konténer használatát C++ nyelven, amely hash-táblázat segítségével valósul meg, és gyors hozzáférést biztosít a kulcs-érték párokhoz.
• Először is, a program tartalmazza a szükséges fejléc fájlokat: és.
• Ezután a program létrehoz egy üres unordered_map tárolót my_map néven, amely karakterlánc-kulcsokat és egész értékeket tartalmaz. Ez az std::unordered_map szintaxissal tehető meg: my_map;
• Ezután a program három kulcsérték-párt szúr be a my_map tárolóba a [] operátor használatával: 'alma' 10 értékű, 'banán' 20 értékű és 'narancs' 30 értékű.
• Ez a saját_térkép['alma'] = 10;, my_map['banán'] = 20; és a saját_térkép['narancs'] = 30 szintaxis használatával történik; illetőleg.
• Végül a program kiírja a 'banana' kulcshoz tartozó értéket a [] operátor és az std::cout objektum segítségével.

Program kimenet:

Adatok beszúrása egy hash táblába

Ahhoz, hogy egy kulcs-érték párt beszúrhassunk egy hash-táblázatba, először egy indexet kell beillesztenünk a tömbbe a kulcs-érték pár tárolására. Ha egy másik kulcs ugyanarra az indexre van leképezve, akkor ütközünk, és megfelelően kell kezelnünk. Az egyik elterjedt módszer a láncolás használata, ahol a tömb minden egyes gyűjtője tartalmazza az azonos hash értékkel rendelkező kulcs-érték párok összekapcsolt listáját.

Íme egy példa arra, hogyan lehet kulcs-érték párt beszúrni egy hash táblába láncolás segítségével:

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

Magyarázat:

• Először meg kell határozni egy csomópont nevű struktúrát, amely egyetlen csomópontot képvisel a hash táblában.
• Minden csomópontnak három tagja van: egy char* kulcs a kulcs tárolására, egy int érték a társított érték tárolására, és egy másik csomópontra mutató mutató, amely a hash táblában egy csatolt lista segítségével az ütközéseket kezeli.
• A hash_table nevű csomópontmutatók tömbje 100-as mérettel van deklarálva. Ez a tömb lesz használva a hash tábla elemeinek tárolására.
• Az insert függvény paraméterként egy char* kulcsot és egy int értéket vesz fel.
• Úgy kezdődik, hogy kiszámítja az adott kulcs hash értékét a hash függvény segítségével, amely feltételezhetően máshol van definiálva a programban.
• A hash értéke ezután lecsökken, hogy beleférjen a hash_table tömb méretébe a % 100 modulus operátor használatával.
• Egy új csomópont dinamikus memóriafoglalással jön létre (malloc(sizeof(node))), és tagjai (kulcs, érték és next) a megadott kulccsal, értékkel és NULL-lel vannak hozzárendelve.
• Ha a hash_table tömb megfelelő slotja üres (NULL), ami azt jelzi, hogy nem történt ütközés, akkor az új csomópont közvetlenül ehhez a réshez lesz rendelve (hash_table[hash_value] = new_node).

Ha azonban már van egy csomópont ezen az indexen a hash_table tömbben, akkor a függvénynek kezelnie kell az ütközést. Bejárja a csatolt listát az aktuális csomóponttól kezdve (hash_table[hash_value]), és a következő csomópontra lép, amíg el nem éri a végét (curr_node->next != NULL). Amint a lista végét elérjük, az új csomópont hozzáfűződik a következő csomópontként (curr_node->next = new_node).

A kivonat megvalósítása C++ nyelven:

Lássuk a kivonatolás megvalósítását C++ nyelven nyílt címzés és az ütközésfeloldás lineáris vizsgálata segítségével. Megvalósítunk egy hash táblát, amely egész számokat tárol.

tömb java-ban

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