Introduktion till hash i datastruktur:
Hashing är en populär teknik inom datavetenskap som går ut på att kartlägga stora datamängder till värden med fast längd. Det är en process för att konvertera en datamängd av variabel storlek till en datamängd av fast storlek. Möjligheten att utföra effektiva uppslagsoperationer gör hash till ett viktigt koncept i datastrukturer.
java bruksdatum
Vad är Hashing?
En hashalgoritm används för att konvertera en indata (som en sträng eller ett heltal) till en utdata med fast storlek (kallas en hashkod eller ett hashvärde). Data lagras sedan och hämtas med detta hashvärde som ett index i en array eller hashtabell. Hashfunktionen måste vara deterministisk, vilket garanterar att den alltid kommer att ge samma resultat för en given ingång.
Hashing används vanligtvis för att skapa en unik identifierare för en bit data, som kan användas för att snabbt slå upp den datan i en stor datamängd. En webbläsare kan till exempel använda hashing för att lagra webbläsaren på ett säkert sätt. När en användare anger sitt lösenord konverterar webbläsaren det till ett hashvärde och jämför det med det lagrade hashvärdet för att autentisera användaren.
Vad är en hashnyckel?
I hashsammanhang är en hashnyckel (även känd som ett hashvärde eller hashkod) en numerisk eller alfanumerisk representation med fast storlek genererad av en hashalgoritm. Den härleds från indata, såsom en textsträng eller en fil, genom en process som kallas hashing.
Hashing innebär att en specifik matematisk funktion appliceras på indata, vilket ger en unik hash-nyckel som vanligtvis har en fast längd, oavsett storleken på inmatningen. Den resulterande hash-nyckeln är i huvudsak ett digitalt fingeravtryck av originaldata.
Hashnyckeln tjänar flera syften. Det används vanligtvis för dataintegritetskontroller, eftersom även en liten förändring i indata kommer att producera en väsentligt annorlunda hash-nyckel. Hash-nycklar används också för effektiv datahämtning och lagring i hashtabeller eller datastrukturer, eftersom de tillåter snabb uppslags- och jämförelseoperationer.
Hur fungerar hashing?
Processen med hashning kan delas upp i tre steg:
- Indata: Datan som ska hashas matas in i hashalgoritmen.
- Hash-funktion: Hashingalgoritmen tar indata och tillämpar en matematisk funktion för att generera ett hashvärde med fast storlek. Hashfunktionen bör utformas så att olika ingångsvärden ger olika hashvärden och små förändringar i ingången ger stora förändringar i utdata.
- Utdata: Hashvärdet returneras, vilket används som ett index för att lagra eller hämta data i en datastruktur.
Hashing-algoritmer:
Det finns många hashalgoritmer, var och en med distinkta fördelar och nackdelar. De mest populära algoritmerna inkluderar följande:
- MD5: En allmänt använd hashalgoritm som producerar ett 128-bitars hashvärde.
- SHA-1: En populär hashalgoritm som producerar ett 160-bitars hashvärde.
- SHA-256: En säkrare hashalgoritm som producerar ett 256-bitars hashvärde.
Hash funktion:
Hash-funktion: En hash-funktion är en typ av matematisk operation som tar en ingång (eller nyckel) och matar ut ett resultat med fast storlek, känt som en hash-kod eller hash-värde. Hashfunktionen måste alltid ge samma hashkod för samma ingång för att vara deterministisk. Dessutom bör hash-funktionen producera en unik hash-kod för varje ingång, vilket är känt som hash-egenskapen.
Det finns olika typer av hashfunktioner, inklusive:
Denna metod innebär att man delar nyckeln med tabellstorleken och tar resten som hashvärde. Till exempel, om tabellstorleken är 10 och nyckeln är 23, skulle hashvärdet vara 3 (23 % 10 = 3).
Denna metod går ut på att multiplicera nyckeln med en konstant och ta del av produkten som hashvärde. Till exempel, om nyckeln är 23 och konstanten är 0,618, skulle hashvärdet vara 2 (floor(10*(0,61823 - floor(0,61823))) = floor(2,236) = 2).
Denna metod innebär att man använder en slumpmässig hashfunktion från en familj av hashfunktioner. Detta säkerställer att hashfunktionen inte är partisk mot någon speciell ingång och är resistent mot attacker.
Kollisionsupplösning
En av de största utmaningarna i hash är att hantera kollisioner, som uppstår när två eller flera ingångsvärden producerar samma hashvärde. Det finns olika tekniker som används för att lösa kollisioner, inklusive:
- Chaining: I den här tekniken innehåller varje hash-tabellplats en länkad lista över alla värden som har samma hashvärde. Denna teknik är enkel och lätt att implementera, men den kan leda till dålig prestanda när de länkade listorna blir för långa.
- Öppen adressering: I denna teknik, när en kollision inträffar, söker algoritmen efter en tom lucka i hashtabellen genom att sondera efter varandra följande luckor tills en tom lucka hittas. Denna teknik kan vara effektivare än kedja när belastningsfaktorn är låg, men den kan leda till klusterbildning och dålig prestanda när belastningsfaktorn är hög.
- Dubbel hash: Detta är en variant av öppen adressering som använder en andra hashfunktion för att bestämma nästa lucka som ska undersökas när en kollision inträffar. Denna teknik kan hjälpa till att minska klustring och förbättra prestanda.
Exempel på kollisionsupplösning
Låt oss fortsätta med vårt exempel på en hashtabell med storleken 5. Vi vill lagra nyckel-värdeparen 'John: 123456' och 'Mary: 987654' i hashtabellen. Båda nycklarna producerar samma hashkod på 4, så en kollision inträffar.
Vi kan använda kedja för att lösa kollisionen. Vi skapar en länkad lista vid index 4 och lägger till nyckel-värdeparen till listan. Hashtabellen ser nu ut så här:
hur får jag reda på min skärmstorlek
0:
1:
2:
3:
kylie jenner syskon
4: John: 123456 -> Mary: 987654
5:
Hashtabell:
En hashtabell är en datastruktur som lagrar data i en array. Vanligtvis väljs en storlek för arrayen som är större än antalet element som får plats i hashtabellen. En nyckel mappas till ett index i arrayen med hjälp av hash-funktionen.
Hashfunktionen används för att lokalisera indexet där ett element måste infogas i hashtabellen för att lägga till ett nytt element. Elementet läggs till det indexet om det inte finns en kollision. Om det sker en kollision används kollisionsupplösningsmetoden för att hitta nästa tillgängliga plats i arrayen.
Hashfunktionen används för att lokalisera indexet som elementet är lagrat för att hämta det från hashtabellen. Om elementet inte hittas vid det indexet, används kollisionsupplösningsmetoden för att söka efter elementet i den länkade listan (om kedja används) eller i nästa tillgängliga lucka (om öppen adressering används).
Hash-tabelloperationer
Det finns flera operationer som kan utföras på en hashtabell, inklusive:
- Infogning: Infogar ett nytt nyckel-värdepar i hashtabellen.
- Borttagning: Ta bort ett nyckel-värdepar från hashtabellen.
- Sök: Söker efter ett nyckel-värdepar i hashtabellen.
Skapa en hashtabell:
Hashing används ofta för att bygga hashtabeller, som är datastrukturer som möjliggör snabb datainsättning, radering och hämtning. Ett eller flera nyckel-värdepar kan lagras i var och en av de arrayer av hinkar som utgör en hashtabell.
För att skapa en hashtabell måste vi först definiera en hashfunktion som mappar varje nyckel till ett unikt index i arrayen. En enkel hashfunktion kan vara att ta summan av ASCII-värdena för tecknen i nyckeln och använda resten när de divideras med storleken på matrisen. Denna hash-funktion är dock ineffektiv och kan leda till kollisioner (två nycklar som mappar till samma index).
För att undvika kollisioner kan vi använda mer avancerade hashfunktioner som ger en jämnare fördelning av hashvärden över arrayen. En populär algoritm är djb2 hash-funktionen, som använder bitvisa operationer för att generera ett hashvärde:
unsigned long hash(char* str) { unsigned long hash = 5381; int c; while (c = *str++) { hash = ((hash << 5) + hash) + c; } return hash; } Denna hashfunktion tar en sträng som indata och returnerar ett hashvärde utan tecken med långt heltalsvärde. Funktionen initierar ett hashvärde på 5381 och itererar sedan över varje tecken i strängen, med hjälp av bitvisa operationer för att generera ett nytt hashvärde. Det slutliga hashvärdet returneras.
Hash-tabeller i C++
I C++ tillhandahåller standardbiblioteket en hashtabellbehållarklass som heter unordered_map. Unordered_map-behållaren implementeras med hjälp av en hashtabell och ger snabb åtkomst till nyckel-värdepar. Unordered_map-behållaren använder en hashfunktion för att beräkna hashkoden för nycklarna och använder sedan öppen adressering för att lösa kollisioner.
För att använda unordered_map-behållaren i C++ måste du inkludera rubrikfilen. Här är ett exempel på hur man skapar en unordered_map-behållare i 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; } Förklaring:
- Det här programmet demonstrerar användningen av unordered_map-behållaren i C++, som implementeras med hjälp av en hashtabell och ger snabb åtkomst till nyckel-värdepar.
- Först innehåller programmet de nödvändiga rubrikfilerna: och.
- Sedan skapar programmet en tom unordered_map-behållare som heter my_map, som har strängnycklar och heltalsvärden. Detta görs med syntaxen std::unordered_map my_map;
- Därefter infogar programmet tre nyckel-värdepar i my_map-behållaren med []-operatorn: 'äpple' med värdet 10, 'banan' med värdet 20 och 'orange' med värdet 30.
- Detta görs med syntaxen my_map['apple'] = 10;, my_map['banan'] = 20;, och my_map['orange'] = 30; respektive.
- Slutligen skriver programmet ut värdet som är associerat med 'banan'-nyckeln med []-operatorn och std::cout-objektet.
Programutgång:
strängformaterare
Infoga data i en hash-tabell
För att infoga ett nyckel-värde-par i en hash-tabell måste vi först lägga ett index i arrayen för att lagra nyckel-värde-paret. Om en annan nyckel mappar till samma index har vi en kollision och måste hantera den på rätt sätt. En vanlig metod är att använda chaining, där varje hink i arrayen innehåller en länkad lista med nyckel-värdepar som har samma hashvärde.
Här är ett exempel på hur man infogar ett nyckel-värdepar i en hashtabell med hjälp av kedja:
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; } } Förklaring:
- Först definieras en struktur som kallas nod, som representerar en enda nod i hashtabellen.
- Varje nod har tre medlemmar: en char*-nyckel för att lagra nyckeln, ett int-värde för att lagra det associerade värdet och en pekare till en annan nod som kallas bredvid för att hantera kollisioner i hashtabellen med hjälp av en länkad lista.
- En array av nodpekare som kallas hash_table deklareras med storleken 100. Denna array kommer att användas för att lagra elementen i hashtabellen.
- Insert-funktionen tar en char*-nyckel och ett int-värde som parametrar.
- Den börjar med att beräkna hashvärdet för den givna nyckeln med hjälp av hashfunktionen, som antas vara definierad på annat håll i programmet.
- Hashvärdet reduceras sedan för att passa inom storleken på hash_table-matrisen med hjälp av moduloperatorn % 100.
- En ny nod skapas med hjälp av dynamisk minnesallokering (malloc(sizeof(nod))), och dess medlemmar (nyckel, värde och nästa) tilldelas den angivna nyckeln, värdet respektive NULL.
- Om motsvarande lucka i hash_table-matrisen är tom (NULL), vilket indikerar att ingen kollision har inträffat, tilldelas den nya noden den luckan direkt (hash_table[hash_value] = new_node).
Men om det redan finns en nod vid det indexet i hash_table-matrisen, måste funktionen hantera kollisionen. Den korsar den länkade listan med början från den aktuella noden (hash_table[hash_value]) och flyttar till nästa nod tills den når slutet (curr_node->next != NULL). När slutet av listan nås, läggs den nya noden till som nästa nod (curr_node->next = new_node).
Implementering av hashing i C++:
Låt oss se en implementering av hash i C++ med öppen adressering och linjär sondering för kollisionsupplösning. Vi kommer att implementera en hashtabell som lagrar heltal.
#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;>