TechCodeview

Úvod do hašování v datové struktuře:

Hašování je populární technika v informatice, která zahrnuje mapování velkých souborů dat na hodnoty s pevnou délkou. Je to proces převodu datové sady proměnné velikosti na datovou sadu pevné velikosti. Schopnost provádět efektivní vyhledávací operace dělá z hašování základní koncept v datových strukturách.

turbo c++ ke stažení

Co je hashování?

Hashovací algoritmus se používá k převodu vstupu (jako je řetězec nebo celé číslo) na výstup s pevnou velikostí (označovaný jako hash kód nebo hodnota hash). Data jsou poté uložena a načtena pomocí této hodnoty hash jako indexu v poli nebo tabulce hash. Hašovací funkce musí být deterministická, což zaručuje, že pro daný vstup vždy poskytne stejný výsledek.

Hašování se běžně používá k vytvoření jedinečného identifikátoru pro část dat, který lze použít k rychlému vyhledání těchto dat ve velkém souboru dat. Webový prohlížeč může například používat hash k bezpečnému ukládání hesel webových stránek. Když uživatel zadá své heslo, prohlížeč jej převede na hodnotu hash a porovná ji s uloženou hodnotou hash pro ověření uživatele.

Co je hash Key?

V kontextu hašování je hašovací klíč (také známý jako hašovací hodnota nebo hašovací kód) numerická nebo alfanumerická reprezentace s pevnou velikostí generovaná hašovacím algoritmem. Odvozuje se ze vstupních dat, jako je textový řetězec nebo soubor, prostřednictvím procesu známého jako hašování.

Hašování zahrnuje aplikaci specifické matematické funkce na vstupní data, která vytváří jedinečný hash klíč, který má obvykle pevnou délku, bez ohledu na velikost vstupu. Výsledný hash klíč je v podstatě digitálním otiskem původních dat.

Hash klíč slouží k několika účelům. Běžně se používá pro kontrolu integrity dat, protože i malá změna ve vstupních datech vytvoří výrazně odlišný hash klíč. Hash klíče se také používají pro efektivní vyhledávání a ukládání dat v hašovacích tabulkách nebo datových strukturách, protože umožňují rychlé vyhledávání a porovnávání.

Jak hashování funguje?

Proces hashování lze rozdělit do tří kroků:

• Vstup: Data, která mají být hašována, jsou vložena do hašovacího algoritmu.
• Hashovací funkce: Hashovací algoritmus vezme vstupní data a použije matematickou funkci ke generování hash hodnoty pevné velikosti. Hašovací funkce by měla být navržena tak, aby různé vstupní hodnoty produkovaly různé hašovací hodnoty a malé změny na vstupu vedly k velkým změnám na výstupu.
• Výstup: Je vrácena hodnota hash, která se používá jako index k ukládání nebo načítání dat v datové struktuře.

Hashovací algoritmy:

Existuje mnoho hashovacích algoritmů, z nichž každý má své výhody a nevýhody. Mezi nejoblíbenější algoritmy patří následující:

• MD5: Široce používaný hašovací algoritmus, který vytváří 128bitovou hašovací hodnotu.
• SHA-1: Populární hašovací algoritmus, který vytváří 160bitovou hašovací hodnotu.
• SHA-256: Bezpečnější hashovací algoritmus, který vytváří 256bitovou hodnotu hash.

Hashovací funkce:

Hashovací funkce: Hashovací funkce je typ matematické operace, která přijímá vstup (nebo klíč) a vydává výsledek s pevnou velikostí známý jako hash kód nebo hodnota hash. Aby byla hašovací funkce deterministická, musí vždy poskytnout stejný hašovací kód pro stejný vstup. Kromě toho by hashovací funkce měla pro každý vstup vytvořit jedinečný hash kód, který je známý jako vlastnost hash.

Existují různé typy hashovacích funkcí, včetně:

Způsob dělení:

Tato metoda zahrnuje dělení klíče velikostí tabulky a zbytek jako hash hodnotu. Pokud je například velikost tabulky 10 a klíč je 23, hodnota hash by byla 3 (23 % 10 = 3).

Způsob násobení:

Tato metoda zahrnuje vynásobení klíče konstantou a převzetí zlomkové části produktu jako hash hodnoty. Pokud je například klíč 23 a konstanta je 0,618, hodnota hash by byla 2 (podlaží(10*(0,61823 - patro(0,61823))) = patro(2,236) = 2).

Univerzální hashování:

Tato metoda zahrnuje použití náhodné hašovací funkce z rodiny hašovacích funkcí. To zajišťuje, že hashovací funkce není zaujatá vůči žádnému konkrétnímu vstupu a je odolná vůči útokům.

Rozlišení kolize

Jednou z hlavních výzev při hašování je řešení kolizí, ke kterým dochází, když dvě nebo více vstupních hodnot vytvoří stejnou hašovací hodnotu. K řešení kolizí se používají různé techniky, včetně:

• Řetězení: V této technice obsahuje každý slot hašovací tabulky propojený seznam všech hodnot, které mají stejnou hašovací hodnotu. Tato technika je jednoduchá a snadno implementovatelná, ale může vést ke špatnému výkonu, když jsou propojené seznamy příliš dlouhé.
• Otevřené adresování: Při této technice, když dojde ke kolizi, algoritmus hledá prázdný slot v hašovací tabulce zkoumáním po sobě jdoucích slotů, dokud nenajde prázdný slot. Tato technika může být efektivnější než řetězení, když je faktor zatížení nízký, ale může vést ke shlukování a špatnému výkonu, když je faktor zatížení vysoký.
• Dvojité hašování: Toto je varianta otevřeného adresování, která používá druhou hašovací funkci k určení dalšího slotu, který se má zkoumat, když dojde ke kolizi. Tato technika může pomoci snížit shlukování a zlepšit výkon.

Příklad rozlišení kolize

Pokračujme v našem příkladu hashovací tabulky o velikosti 5. Chceme uložit páry klíč-hodnota 'John: 123456' a 'Mary: 987654' do hašovací tabulky. Oba klíče vytvářejí stejný hash kód 4, takže dojde ke kolizi.

K vyřešení kolize můžeme použít řetězení. Vytvoříme propojený seznam na indexu 4 a do seznamu přidáme páry klíč–hodnota. Hašovací tabulka nyní vypadá takto:

co znamená xd

0:

1:

2:

3:

java regex $

4: John: 123456 -> Mary: 987654

5:

Tabulka hash:

Hašovací tabulka je datová struktura, která ukládá data do pole. Typicky je velikost pole vybrána, která je větší než počet prvků, které se vejdou do hašovací tabulky. Klíč je mapován na index v poli pomocí hashovací funkce.

Funkce hash se používá k vyhledání indexu, kam je třeba vložit prvek do tabulky hash, aby bylo možné přidat nový prvek. Prvek se do tohoto indexu přidá, pokud nedojde ke kolizi. Pokud dojde ke kolizi, použije se metoda rozlišení kolize k nalezení dalšího volného slotu v poli.

Hašovací funkce se používá k vyhledání indexu, ve kterém je prvek uložen, aby jej bylo možné získat z hašovací tabulky. Pokud prvek není v tomto indexu nalezen, použije se metoda řešení kolizí k vyhledání prvku v propojeném seznamu (pokud je použito řetězení) nebo v dalším dostupném slotu (pokud je použito otevřené adresování).

Operace hashovací tabulky

Existuje několik operací, které lze provést s hashovací tabulkou, včetně:

• Vložení: Vložení nového páru klíč–hodnota do hashovací tabulky.
• Odstranění: Odstranění páru klíč–hodnota z hašovací tabulky.
• Hledat: Hledání páru klíč–hodnota v hašovací tabulce.

Vytvoření hash tabulky:

Hašování se často používá k vytváření hašovacích tabulek, což jsou datové struktury, které umožňují rychlé vkládání, mazání a načítání dat. V každém z polí segmentů, které tvoří hashovací tabulku, lze uložit jeden nebo více párů klíč–hodnota.

Abychom vytvořili hashovací tabulku, musíme nejprve definovat hashovací funkci, která mapuje každý klíč na jedinečný index v poli. Jednoduchou hashovací funkcí může být vzít součet hodnot ASCII znaků v klíči a použít zbytek, když se vydělí velikostí pole. Tato hašovací funkce je však neefektivní a může vést ke kolizím (dvě klíče, které se mapují na stejný index).

Abychom se vyhnuli kolizím, můžeme použít pokročilejší hašovací funkce, které produkují rovnoměrnější rozložení hašovacích hodnot v poli. Jedním z populárních algoritmů je hashovací funkce djb2, která používá bitové operace ke generování hodnoty hash:

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

Tato hashovací funkce bere řetězec jako vstup a vrací hodnotu hash dlouhého celého čísla bez znaménka. Funkce inicializuje hodnotu hash 5381 a poté iteruje přes každý znak v řetězci pomocí bitových operací ke generování nové hodnoty hash. Vrátí se konečná hodnota hash.

Hash tabulky v C++

V C++ poskytuje standardní knihovna třídu kontejneru hash tabulky s názvem unordered_map. Kontejner unordered_map je implementován pomocí hashovací tabulky a poskytuje rychlý přístup k párům klíč–hodnota. Kontejner unordered_map používá hashovací funkci k výpočtu hash kódu klíčů a poté používá otevřené adresování k vyřešení kolizí.

Chcete-li použít kontejner unordered_map v C++, musíte zahrnout soubor záhlaví. Zde je příklad, jak vytvořit kontejner unordered_map v 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; } 

Vysvětlení:

• Tento program demonstruje použití kontejneru unordered_map v C++, který je implementován pomocí hashovací tabulky a poskytuje rychlý přístup k párům klíč-hodnota.
• Nejprve program obsahuje potřebné hlavičkové soubory: a.
• Poté program vytvoří prázdný kontejner unordered_map s názvem my_map, který má řetězcové klíče a celočíselné hodnoty. To se provádí pomocí syntaxe std::unordered_map my_map;
• Dále program vloží tři páry klíč–hodnota do kontejneru my_map pomocí operátoru []: 'jablko' s hodnotou 10, 'banán' s hodnotou 20 a 'oranžový' s hodnotou 30.
• To se provádí pomocí syntaxe my_map['apple'] = 10;, my_map['banana'] = 20; a my_map['orange'] = 30; respektive.
• Nakonec program vytiskne hodnotu spojenou s klíčem 'banán' pomocí operátoru [] a objektu std::cout.

Výstup programu:

přejmenování adresáře v linuxu

Vkládání dat do hash tabulky

Abychom vložili pár klíč–hodnota do hashovací tabulky, musíme nejprve přidat index do pole, aby se pár klíč–hodnota uložil. Pokud se na stejný index mapuje jiný klíč, dochází ke kolizi a musíme to náležitě zpracovat. Jednou z běžných metod je použití řetězení, kde každý segment v poli obsahuje propojený seznam párů klíč–hodnota, které mají stejnou hodnotu hash.

Zde je příklad, jak vložit pár klíč–hodnota do hašovací tabulky pomocí řetězení:

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

Vysvětlení:

• Nejprve je definována struktura nazvaná uzel, která představuje jeden uzel v hashovací tabulce.
• Každý uzel má tři členy: klíč char* pro uložení klíče, hodnotu int pro uložení přidružené hodnoty a ukazatel na další uzel, který se volá vedle, aby řešil kolize v tabulce hash pomocí propojeného seznamu.
• Pole ukazatelů uzlů s názvem hash_table je deklarováno s velikostí 100. Toto pole bude použito k uložení prvků hash tabulky.
• Funkce insert bere jako parametry klíč char* a hodnotu int.
• Začíná výpočtem hodnoty hash pro daný klíč pomocí hashovací funkce, o které se předpokládá, že je definována jinde v programu.
• Hodnota hash je poté redukována tak, aby se vešla do velikosti pole hash_table pomocí operátoru modulu % 100.
• Nový uzel je vytvořen pomocí dynamické alokace paměti (malloc(sizeof(node))) a jeho členům (klíč, hodnota a další) jsou přiřazeny zadaný klíč, hodnota a NULL.
• Pokud je odpovídající slot v poli hash_table prázdný (NULL), což znamená, že nenastala žádná kolize, je nový uzel přiřazen přímo tomuto slotu (hash_table[hash_value] = nový_uzel).

Pokud však na tomto indexu v poli hash_table již existuje uzel, funkce musí kolizi zpracovat. Prochází propojený seznam počínaje aktuálním uzlem (hash_table[hash_value]) a přesouvá se k dalšímu uzlu, dokud nedosáhne konce (curr_node->next != NULL). Jakmile je dosaženo konce seznamu, je nový uzel připojen jako další uzel (curr_node->next = nový_uzel).

Implementace hashování v C++:

Podívejme se na implementaci hashování v C++ pomocí otevřeného adresování a lineárního sondování pro řešení kolizí. Implementujeme hashovací tabulku, která ukládá celá čísla.

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