Wprowadzenie do haszowania w strukturze danych:

Haszowanie to popularna technika w informatyce, która polega na mapowaniu dużych zbiorów danych na wartości o stałej długości. Jest to proces przekształcania zbioru danych o zmiennym rozmiarze w zbiór danych o stałym rozmiarze. Możliwość wykonywania wydajnych operacji wyszukiwania sprawia, że ​​haszowanie jest istotną koncepcją w strukturach danych.

Co to jest haszowanie?

Algorytm mieszający służy do konwertowania danych wejściowych (takich jak ciąg znaków lub liczba całkowita) na dane wyjściowe o stałym rozmiarze (określane jako kod skrótu lub wartość skrótu). Dane są następnie przechowywane i pobierane przy użyciu tej wartości skrótu jako indeksu w tablicy lub tabeli mieszającej. Funkcja skrótu musi być deterministyczna, co gwarantuje, że dla danego wejścia zawsze da ten sam wynik.

Haszowanie jest powszechnie stosowane w celu utworzenia unikalnego identyfikatora fragmentu danych, którego można użyć do szybkiego wyszukania tych danych w dużym zbiorze danych. Na przykład przeglądarka internetowa może używać skrótu do bezpiecznego przechowywania haseł do witryn internetowych. Gdy użytkownik wprowadza swoje hasło, przeglądarka konwertuje je na wartość skrótu i ​​porównuje z przechowywaną wartością skrótu w celu uwierzytelnienia użytkownika.

Co to jest klucz skrótu?

W kontekście mieszania klucz skrótu (znany również jako wartość skrótu lub kod skrótu) to reprezentacja numeryczna lub alfanumeryczna o stałym rozmiarze, generowana przez algorytm mieszający. Jest on uzyskiwany z danych wejściowych, takich jak ciąg tekstowy lub plik, w procesie znanym jako haszowanie.

Haszowanie polega na zastosowaniu określonej funkcji matematycznej do danych wejściowych, w wyniku czego powstaje unikalny klucz mieszający, który ma zazwyczaj stałą długość, niezależnie od rozmiaru danych wejściowych. Powstały klucz skrótu jest zasadniczo cyfrowym odciskiem palca oryginalnych danych.

Klucz mieszający służy kilku celom. Jest powszechnie używany do sprawdzania integralności danych, ponieważ nawet niewielka zmiana w danych wejściowych spowoduje powstanie znacząco innego klucza skrótu. Klucze skrótu służą również do wydajnego wyszukiwania i przechowywania danych w tabelach skrótów lub strukturach danych, ponieważ umożliwiają szybkie wyszukiwanie i porównywanie.

pętla do i while w Javie

Jak działa haszowanie?

Proces mieszania można podzielić na trzy etapy:

• Dane wejściowe: Dane przeznaczone do mieszania są wprowadzane do algorytmu mieszającego.
• Funkcja mieszająca: Algorytm mieszający pobiera dane wejściowe i stosuje funkcję matematyczną w celu wygenerowania wartości skrótu o stałym rozmiarze. Funkcja skrótu powinna być zaprojektowana w taki sposób, aby różne wartości wejściowe generowały różne wartości skrótu, a małe zmiany na wejściu powodowały duże zmiany na wyjściu.
• Dane wyjściowe: zwracana jest wartość skrótu, która służy jako indeks do przechowywania lub pobierania danych w strukturze danych.

Algorytmy mieszające:

Istnieje wiele algorytmów mieszania, każdy z odrębnymi zaletami i wadami. Do najpopularniejszych algorytmów należą:

• MD5: Szeroko stosowany algorytm mieszający, który generuje 128-bitową wartość skrótu.
• SHA-1: popularny algorytm mieszający, który generuje 160-bitową wartość skrótu.
• SHA-256: bezpieczniejszy algorytm mieszający, który generuje 256-bitową wartość skrótu.

Funkcja skrótu:

Funkcja skrótu: Funkcja skrótu to rodzaj operacji matematycznej, która pobiera dane wejściowe (lub klucz) i generuje wynik o stałym rozmiarze, znany jako kod skrótu lub wartość skrótu. Aby funkcja skrótu była deterministyczna, musi zawsze dawać ten sam kod skrótu dla tych samych danych wejściowych. Ponadto funkcja skrótu powinna generować unikalny kod skrótu dla każdego wejścia, co jest znane jako właściwość skrótu.

Istnieją różne typy funkcji skrótu, w tym:

Metoda podziału:

Ta metoda polega na podzieleniu klucza przez rozmiar tabeli i przyjęciu reszty jako wartości skrótu. Na przykład, jeśli rozmiar tabeli wynosi 10, a klucz to 23, wartość skrótu będzie wynosić 3 (23% 10 = 3).

Metoda mnożenia:

Metoda ta polega na pomnożeniu klucza przez stałą i przyjęciu części ułamkowej iloczynu jako wartości skrótu. Na przykład, jeśli klucz ma wartość 23, a stała wynosi 0,618, wartość skrótu będzie wynosić 2 (podłoga(10*(0,61823 - podłoga(0,61823))) = podłoga(2,236) = 2).

Uniwersalne hashowanie:

Metoda ta polega na użyciu losowej funkcji skrótu z rodziny funkcji skrótu. Dzięki temu funkcja skrótu nie jest ukierunkowana na żadne konkretne dane wejściowe i jest odporna na ataki.

Rozwiązywanie kolizji

Jednym z głównych wyzwań związanych z mieszaniem jest obsługa kolizji, które występują, gdy dwie lub więcej wartości wejściowych daje tę samą wartość skrótu. Istnieją różne techniki rozwiązywania kolizji, w tym:

• Łańcuch: W tej technice każde miejsce w tabeli skrótów zawiera połączoną listę wszystkich wartości, które mają tę samą wartość skrótu. Technika ta jest prosta i łatwa do wdrożenia, ale może prowadzić do niskiej wydajności, gdy połączone listy staną się zbyt długie.
• Adresowanie otwarte: W tej technice, gdy nastąpi kolizja, algorytm szuka pustego miejsca w tablicy mieszającej, sondując kolejne gniazda, aż do znalezienia pustego miejsca. Technika ta może być bardziej wydajna niż łączenie łańcuchowe, gdy współczynnik obciążenia jest niski, ale może prowadzić do tworzenia klastrów i słabej wydajności, gdy współczynnik obciążenia jest wysoki.
• Podwójne mieszanie: Jest to odmiana otwartego adresowania, która wykorzystuje drugą funkcję mieszającą do określenia następnego gniazda do sprawdzenia w przypadku wystąpienia kolizji. Ta technika może pomóc w ograniczeniu grupowania i poprawie wydajności.

Przykład rozwiązania kolizji

Kontynuujmy nasz przykład tabeli mieszającej o rozmiarze 5. Chcemy przechowywać pary klucz-wartość „John: 123456” i „Mary: 987654” w tabeli mieszającej. Obydwa klucze dają ten sam kod skrótu równy 4, więc następuje kolizja.

Możemy użyć łańcucha, aby rozwiązać kolizję. Tworzymy połączoną listę pod indeksem 4 i dodajemy do niej pary klucz-wartość. Tabela skrótów wygląda teraz tak:

0:

1:

2:

3:

4: Jan: 123456 -> Maryja: 987654

5:

Tabela mieszająca:

Tabela mieszająca to struktura danych przechowująca dane w tablicy. Zwykle wybierany jest rozmiar tablicy większy niż liczba elementów, które mogą zmieścić się w tabeli mieszającej. Klucz jest mapowany na indeks w tablicy za pomocą funkcji skrótu.

Funkcja skrótu służy do zlokalizowania indeksu, w którym należy wstawić element do tablicy mieszającej, aby dodać nowy element. Element zostaje dodany do tego indeksu, jeśli nie ma kolizji. W przypadku kolizji stosowana jest metoda rozwiązywania kolizji w celu znalezienia następnego dostępnego miejsca w tablicy.

Funkcja skrótu służy do zlokalizowania indeksu, w którym przechowywany jest element, w celu pobrania go z tablicy mieszającej. Jeśli element nie zostanie znaleziony pod tym indeksem, do wyszukania elementu na liście połączonej (w przypadku stosowania łączenia łańcuchowego) lub w następnym dostępnym slocie (w przypadku stosowania adresowania otwartego) stosowana jest metoda rozwiązywania kolizji.

Operacje na tablicy mieszającej

Na tablicy mieszającej można wykonać kilka operacji, w tym:

• Wstawianie: Wstawianie nowej pary klucz-wartość do tabeli skrótów.
• Usunięcie: usunięcie pary klucz-wartość z tabeli skrótów.
• Szukaj: Wyszukiwanie pary klucz-wartość w tabeli mieszającej.

Tworzenie tabeli mieszającej:

Haszowanie jest często używane do tworzenia tabel skrótów, które są strukturami danych umożliwiającymi szybkie wstawianie, usuwanie i pobieranie danych. W każdej tablicy segmentów tworzących tabelę mieszającą można przechowywać jedną lub więcej par klucz-wartość.

Aby utworzyć tabelę skrótów, musimy najpierw zdefiniować funkcję skrótu, która odwzorowuje każdy klucz na unikalny indeks w tablicy. Prostą funkcją skrótu może być wzięcie sumy wartości ASCII znaków w kluczu i wykorzystanie reszty z dzielenia przez rozmiar tablicy. Jednak ta funkcja skrótu jest nieefektywna i może prowadzić do kolizji (dwa klucze mapowane na ten sam indeks).

Aby uniknąć kolizji, możemy użyć bardziej zaawansowanych funkcji skrótu, które zapewniają bardziej równomierny rozkład wartości skrótu w tablicy. Jednym z popularnych algorytmów jest funkcja skrótu djb2, która wykorzystuje operacje bitowe do wygenerowania wartości skrótu:

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

Ta funkcja mieszająca przyjmuje ciąg znaków jako dane wejściowe i zwraca wartość skrótu typu long integer bez znaku. Funkcja inicjuje wartość skrótu 5381, a następnie wykonuje iterację po każdym znaku w ciągu, używając operacji bitowych do wygenerowania nowej wartości skrótu. Zwracana jest końcowa wartość skrótu.

Tablice mieszające w C++

W C++ standardowa biblioteka udostępnia klasę kontenera tabeli mieszającej o nazwie unordered_map. Kontener unordered_map jest zaimplementowany przy użyciu tabeli skrótów i zapewnia szybki dostęp do par klucz-wartość. Kontener unordered_map używa funkcji skrótu do obliczenia kodu skrótu kluczy, a następnie używa otwartego adresowania w celu rozwiązania kolizji.

Aby użyć kontenera unordered_map w C++, musisz dołączyć plik nagłówkowy. Oto przykład tworzenia kontenera unordered_map w 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; } 

Wyjaśnienie:

• Ten program demonstruje użycie kontenera unordered_map w C++, który jest zaimplementowany przy użyciu tablicy mieszającej i zapewnia szybki dostęp do par klucz-wartość.
• Po pierwsze, program zawiera niezbędne pliki nagłówkowe: i.
• Następnie program tworzy pusty kontener unordered_map o nazwie my_map, który zawiera klucze łańcuchowe i wartości całkowite. Odbywa się to za pomocą składni std::unordered_map my_map;
• Następnie program wstawia do kontenera my_map trzy pary klucz-wartość za pomocą operatora []: „jabłko” o wartości 10, „banan” o wartości 20 i „pomarańcza” o wartości 30.
• Odbywa się to za pomocą składni my_map['apple'] = 10;, moja_mapa['banan'] = 20; i moja_mapa['orange'] = 30; odpowiednio.
• Na koniec program wypisuje wartość związaną z kluczem „banan”, używając operatora [] i obiektu std::cout.

Dane wyjściowe programu:

Wstawianie danych do tabeli mieszającej

Aby wstawić parę klucz-wartość do tabeli mieszającej, musimy najpierw utworzyć indeks w tablicy, w którym będzie przechowywana para klucz-wartość. Jeśli inny klucz jest mapowany na ten sam indeks, mamy kolizję i musimy sobie z tym odpowiednio poradzić. Jedną z powszechnych metod jest użycie łańcucha, w którym każdy segment w tablicy zawiera połączoną listę par klucz-wartość, które mają tę samą wartość skrótu.

Oto przykład wstawiania pary klucz-wartość do tabeli skrótów za pomocą łączenia:

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

Wyjaśnienie:

• Najpierw definiowana jest struktura zwana węzłem, która reprezentuje pojedynczy węzeł w tabeli mieszającej.
• Każdy węzeł ma trzech członków: klucz char* do przechowywania klucza, wartość int do przechowywania powiązanej wartości oraz wskaźnik do innego węzła wywoływanego obok w celu obsługi kolizji w tabeli mieszającej przy użyciu połączonej listy.
• Zadeklarowana jest tablica wskaźników węzłów zwana hash_table o rozmiarze 100. Tablica ta będzie używana do przechowywania elementów tablicy mieszającej.
• Funkcja wstawiania przyjmuje jako parametry klucz char* i wartość int.
• Rozpoczyna się od obliczenia wartości skrótu dla danego klucza za pomocą funkcji skrótu, która zakłada, że ​​jest zdefiniowana w innym miejscu programu.
• Wartość skrótu jest następnie zmniejszana, aby zmieścić się w rozmiarze tablicy hash_table przy użyciu operatora modułu % 100.
• Nowy węzeł jest tworzony przy użyciu dynamicznej alokacji pamięci (malloc(sizeof(node))), a jego członkom (klucz, wartość i następny) przypisuje się odpowiednio podany klucz, wartość i NULL.
• Jeśli odpowiednie miejsce w tablicy hash_table jest puste (NULL), co oznacza, że ​​nie wystąpiła żadna kolizja, nowy węzeł jest przypisywany bezpośrednio do tego gniazda (tabela hash_wartość_hash] = nowy_węzeł).

Jeśli jednak pod tym indeksem tablicy hash_table znajduje się już węzeł, funkcja musi obsłużyć kolizję. Przechodzi przez połączoną listę zaczynając od bieżącego węzła (tabela_hash[wartość_hash]) i przechodzi do następnego węzła, aż dotrze do końca (curr_node->next != NULL). Po osiągnięciu końca listy nowy węzeł jest dołączany jako następny węzeł (curr_node->next = new_node).

Implementacja haszowania w C++:

Zobaczmy implementację mieszania w C++ przy użyciu otwartego adresowania i sondowania liniowego w celu rozwiązywania kolizji. Zaimplementujemy tablicę mieszającą przechowującą liczby całkowite.

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