HASHING IN DE GEGEVENSSTRUCTUUR

Inleiding tot hashing in de gegevensstructuur:

Hashing is een populaire techniek in de computerwetenschappen waarbij grote datasets worden toegewezen aan waarden met een vaste lengte. Het is een proces waarbij een dataset met een variabele grootte wordt omgezet in een dataset met een vaste grootte. De mogelijkheid om efficiënte opzoekbewerkingen uit te voeren maakt hashing tot een essentieel concept in datastructuren.

Wat is hashen?

Een hash-algoritme wordt gebruikt om invoer (zoals een tekenreeks of geheel getal) om te zetten in een uitvoer met een vaste grootte (ook wel een hash-code of hash-waarde genoemd). De gegevens worden vervolgens opgeslagen en opgehaald met behulp van deze hashwaarde als index in een array of hashtabel. De hashfunctie moet deterministisch zijn, wat garandeert dat deze voor een bepaalde invoer altijd hetzelfde resultaat oplevert.

Hashing wordt vaak gebruikt om een unieke identificatie voor een stuk gegevens te creëren, die kan worden gebruikt om die gegevens snel in een grote dataset op te zoeken. Een webbrowser kan bijvoorbeeld hashing gebruiken om websitewachtwoorden veilig op te slaan. Wanneer een gebruiker zijn wachtwoord invoert, converteert de browser dit naar een hashwaarde en vergelijkt deze met de opgeslagen hashwaarde om de gebruiker te authenticeren.

Wat is een hash-sleutel?

In de context van hashing is een hash-sleutel (ook bekend als hash-waarde of hash-code) een numerieke of alfanumerieke representatie met een vaste grootte die wordt gegenereerd door een hash-algoritme. Het wordt afgeleid van de invoergegevens, zoals een tekstreeks of een bestand, via een proces dat bekend staat als hashing.

Hashing omvat het toepassen van een specifieke wiskundige functie op de invoergegevens, die een unieke hash-sleutel oplevert die doorgaans een vaste lengte heeft, ongeacht de grootte van de invoer. De resulterende hash-sleutel is in wezen een digitale vingerafdruk van de originele gegevens.

De hash-sleutel dient verschillende doeleinden. Het wordt vaak gebruikt voor gegevensintegriteitscontroles, omdat zelfs een kleine verandering in de invoergegevens een aanzienlijk andere hash-sleutel zal opleveren. Hash-sleutels worden ook gebruikt voor het efficiënt ophalen en opslaan van gegevens in hash-tabellen of datastructuren, omdat ze snelle opzoek- en vergelijkingsbewerkingen mogelijk maken.

Hoe hashing werkt?

Het proces van hashen kan in drie stappen worden opgesplitst:

Invoer: De te hashen gegevens worden ingevoerd in het hash-algoritme.
Hash-functie: Het hash-algoritme neemt de invoergegevens en past een wiskundige functie toe om een hash-waarde met een vaste grootte te genereren. De hashfunctie moet zo worden ontworpen dat verschillende invoerwaarden verschillende hashwaarden opleveren, en dat kleine veranderingen in de invoer grote veranderingen in de uitvoer veroorzaken.
Uitvoer: de hashwaarde wordt geretourneerd, die wordt gebruikt als index om gegevens in een gegevensstructuur op te slaan of op te halen.

Hashing-algoritmen:

Er zijn talloze hash-algoritmen, elk met verschillende voor- en nadelen. De meest populaire algoritmen zijn onder meer:

ubuntu welk commando

MD5: Een veelgebruikt hash-algoritme dat een hash-waarde van 128 bits produceert.
SHA-1: Een populair hash-algoritme dat een hash-waarde van 160 bits produceert.
SHA-256: Een veiliger hash-algoritme dat een hash-waarde van 256 bits produceert.

Hash-functie:

Hash-functie: Een hash-functie is een soort wiskundige bewerking waarbij een invoer (of sleutel) wordt gebruikt en een resultaat van vaste grootte wordt uitgevoerd, bekend als een hash-code of hash-waarde. De hashfunctie moet altijd dezelfde hashcode opleveren voor dezelfde invoer om deterministisch te zijn. Bovendien moet de hash-functie voor elke invoer een unieke hash-code produceren, die bekend staat als de hash-eigenschap.

Er zijn verschillende soorten hashfuncties, waaronder:

Verdeelmethode:

Bij deze methode wordt de sleutel gedeeld door de tabelgrootte en wordt de rest als hashwaarde genomen. Als de tabelgrootte bijvoorbeeld 10 is en de sleutel 23, is de hashwaarde 3 (23% 10 = 3).

Vermenigvuldigingsmethode:

Deze methode omvat het vermenigvuldigen van de sleutel met een constante en het nemen van het fractionele deel van het product als de hashwaarde. Als de sleutel bijvoorbeeld 23 is en de constante 0,618, is de hashwaarde 2 (floor(10*(0,61823 - floor(0,61823))) = floor(2,236) = 2).

Universele hashing:

Deze methode omvat het gebruik van een willekeurige hashfunctie uit een familie van hashfuncties. Dit zorgt ervoor dat de hashfunctie niet gericht is op een bepaalde invoer en bestand is tegen aanvallen.

Botsingsresolutie

Een van de belangrijkste uitdagingen bij hashing is het omgaan met botsingen, die optreden wanneer twee of meer invoerwaarden dezelfde hashwaarde opleveren. Er worden verschillende technieken gebruikt om botsingen op te lossen, waaronder:

lijst met lettertypen in gimp

Chaining: Bij deze techniek bevat elke hashtabelslot een gekoppelde lijst van alle waarden die dezelfde hashwaarde hebben. Deze techniek is eenvoudig en gemakkelijk te implementeren, maar kan tot slechte prestaties leiden als de gekoppelde lijsten te lang worden.
Open adressering: bij deze techniek zoekt het algoritme, wanneer er een botsing plaatsvindt, naar een leeg slot in de hashtabel door opeenvolgende slots te onderzoeken totdat een leeg slot wordt gevonden. Deze techniek kan efficiënter zijn dan ketenen als de belastingsfactor laag is, maar kan leiden tot clustering en slechte prestaties als de belastingsfactor hoog is.
Dubbele hashing: Dit is een variant van open adressering die een tweede hashfunctie gebruikt om het volgende slot te bepalen dat moet worden onderzocht wanneer er een botsing plaatsvindt. Deze techniek kan clustering helpen verminderen en de prestaties verbeteren.

Voorbeeld van botsingsresolutie

Laten we doorgaan met ons voorbeeld van een hashtabel met een grootte van 5. We willen de sleutelwaardeparen 'John: 123456' en 'Mary: 987654' opslaan in de hashtabel. Beide sleutels produceren dezelfde hashcode van 4, waardoor er een botsing ontstaat.

We kunnen ketening gebruiken om de botsing op te lossen. We maken een gekoppelde lijst op index 4 en voegen de sleutel-waardeparen toe aan de lijst. De hashtabel ziet er nu als volgt uit:

c++ int naar tekenreeks

4: Johannes: 123456 -> Maria: 987654

Hash-tabel:

Een hashtabel is een gegevensstructuur waarin gegevens in een array worden opgeslagen. Meestal wordt een grootte voor de array geselecteerd die groter is dan het aantal elementen dat in de hashtabel past. Een sleutel wordt toegewezen aan een index in de array met behulp van de hash-functie.

De hashfunctie wordt gebruikt om de index te lokaliseren waar een element in de hashtabel moet worden ingevoegd om een nieuw element toe te voegen. Het element wordt aan die index toegevoegd als er geen botsing is. Als er wel een botsing is, wordt de botsingsresolutiemethode gebruikt om het volgende beschikbare slot in de array te vinden.

De hash-functie wordt gebruikt om de index te lokaliseren waarin het element is opgeslagen, om deze uit de hash-tabel op te halen. Als het element niet in die index wordt gevonden, wordt de botsingsresolutiemethode gebruikt om naar het element te zoeken in de gekoppelde lijst (als ketenschakeling wordt gebruikt) of in het volgende beschikbare slot (als open adressering wordt gebruikt).

Hashtabelbewerkingen

Er zijn verschillende bewerkingen die kunnen worden uitgevoerd op een hashtabel, waaronder:

Invoeging: een nieuw sleutelwaardepaar in de hashtabel invoegen.
Verwijdering: het verwijderen van een sleutel-waardepaar uit de hashtabel.
Zoeken: Zoeken naar een sleutel-waardepaar in de hashtabel.

Een hashtabel maken:

Hashing wordt vaak gebruikt om hashtabellen te bouwen. Dit zijn datastructuren die het snel invoegen, verwijderen en ophalen van gegevens mogelijk maken. Een of meer sleutel-waardeparen kunnen worden opgeslagen in elk van de reeksen buckets waaruit een hashtabel bestaat.

Om een hashtabel te maken, moeten we eerst een hashfunctie definiëren die elke sleutel toewijst aan een unieke index in de array. Een eenvoudige hashfunctie zou kunnen zijn om de som van de ASCII-waarden van de tekens in de sleutel te nemen en de rest te gebruiken, gedeeld door de grootte van de array. Deze hashfunctie is echter inefficiënt en kan tot botsingen leiden (twee sleutels die naar dezelfde index verwijzen).

Om botsingen te voorkomen, kunnen we geavanceerdere hashfuncties gebruiken die een gelijkmatigere verdeling van hashwaarden over de array produceren. Een populair algoritme is de djb2-hashfunctie, die bitsgewijze bewerkingen gebruikt om een hashwaarde te genereren:

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

Deze hash-functie neemt een string als invoer en retourneert een niet-ondertekende lange hash-waarde van gehele getallen. De functie initialiseert een hashwaarde van 5381 en herhaalt vervolgens elk teken in de tekenreeks, waarbij bitsgewijze bewerkingen worden gebruikt om een nieuwe hashwaarde te genereren. De uiteindelijke hashwaarde wordt geretourneerd.

Hashtabellen in C++

In C++ biedt de standaardbibliotheek een hashtabelcontainerklasse met de naam unordered_map. De unordered_map container wordt geïmplementeerd met behulp van een hashtabel en biedt snelle toegang tot sleutelwaardeparen. De unordered_map container gebruikt een hash-functie om de hash-code van de sleutels te berekenen en gebruikt vervolgens open adressering om botsingen op te lossen.

Als u de unordered_map container in C++ wilt gebruiken, moet u het headerbestand opnemen. Hier is een voorbeeld van hoe u een unordered_map container maakt in 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[&apos;apple&apos;] = 10; my_map[&apos;banana&apos;] = 20; my_map[&apos;orange&apos;] = 30; // print the value associated with the &apos;banana&apos; key std::cout &lt;&lt; my_map[&apos;banana&apos;] &lt;&lt; std::endl; return 0; }

Uitleg:

Dit programma demonstreert het gebruik van de unordered_map container in C++, die is geïmplementeerd met behulp van een hashtabel en snelle toegang biedt tot sleutel-waardeparen.
Ten eerste bevat het programma de benodigde headerbestanden: en.
Vervolgens maakt het programma een lege unordered_map-container met de naam my_map, die tekenreekssleutels en gehele waarden bevat. Dit wordt gedaan met behulp van de syntaxis std::unordered_map my_map;
Vervolgens voegt het programma drie sleutel-waardeparen in de my_map-container in met behulp van de operator []: 'apple' met een waarde van 10, 'banaan' met een waarde van 20 en 'orange' met een waarde van 30.
Dit wordt gedaan met behulp van de syntaxis mijn_kaart['appel'] = 10;, mijn_kaart['banaan'] = 20;, en mijn_kaart['orange'] = 30; respectievelijk.
Ten slotte drukt het programma de waarde af die is gekoppeld aan de 'banaan'-sleutel met behulp van de operator [] en het std::cout-object.

Programma-uitvoer:

stringarray in c-taal

Gegevens in een hashtabel invoegen

Om een sleutelwaardepaar in een hashtabel in te voegen, moeten we eerst een index in de array plaatsen om het sleutelwaardepaar op te slaan. Als een andere sleutel naar dezelfde index verwijst, is er sprake van een botsing en moeten we deze op de juiste manier afhandelen. Een veelgebruikte methode is het gebruik van chaining, waarbij elke bucket in de array een gekoppelde lijst van sleutelwaardeparen bevat die dezelfde hashwaarde hebben.

Hier is een voorbeeld van hoe u een sleutel-waardepaar in een hashtabel kunt invoegen met behulp van chaining:

 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-&gt;key = key; new_node-&gt;value = value; new_node-&gt;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-&gt;next != NULL) { curr_node = curr_node-&gt;next; } curr_node-&gt;next = new_node; } }

Uitleg:

Eerst wordt een struct genaamd node gedefinieerd, die een enkel knooppunt in de hashtabel vertegenwoordigt.
Elk knooppunt heeft drie leden: een char*-sleutel om de sleutel op te slaan, een int-waarde om de bijbehorende waarde op te slaan, en een verwijzing naar een ander knooppunt dat hierna wordt aangeroepen om botsingen in de hashtabel af te handelen met behulp van een gekoppelde lijst.
Een array van knooppuntaanwijzers genaamd hash_table wordt gedeclareerd met een grootte van 100. Deze array wordt gebruikt om de elementen van de hashtabel op te slaan.
De invoegfunctie heeft een char*-sleutel en een int-waarde als parameters.
Het begint met het berekenen van de hashwaarde voor de gegeven sleutel met behulp van de hashfunctie, waarvan wordt aangenomen dat deze elders in het programma is gedefinieerd.
De hashwaarde wordt vervolgens verkleind zodat deze binnen de grootte van de hash_table-array past met behulp van de modulusoperator % 100.
Er wordt een nieuw knooppunt gemaakt met behulp van dynamische geheugentoewijzing (malloc(sizeof(node))) en de leden ervan (key, value en next) worden toegewezen met respectievelijk de opgegeven sleutel, waarde en NULL.
Als het overeenkomstige slot in de hash_table-array leeg is (NULL), wat aangeeft dat er geen botsing heeft plaatsgevonden, wordt het nieuwe knooppunt rechtstreeks aan dat slot toegewezen (hash_table[hash_value] = new_node).

Als er echter al een knooppunt aanwezig is op die index in de hash_table-array, moet de functie de botsing afhandelen. Het doorkruist de gekoppelde lijst, beginnend bij het huidige knooppunt (hash_table[hash_value]) en gaat naar het volgende knooppunt totdat het het einde bereikt (curr_node->next != NULL). Zodra het einde van de lijst is bereikt, wordt het nieuwe knooppunt toegevoegd als het volgende knooppunt (curr_node->next = new_node).

Implementatie van hashing in C++:

Laten we eens kijken naar een implementatie van hashing in C++ met behulp van open adressering en lineair onderzoek voor het oplossen van botsingen. We zullen een hashtabel implementeren waarin gehele getallen worden opgeslagen.

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

TechCodeview