TechCodeview

Въведение в хеширането в структурата на данните:

Хеширането е популярна техника в компютърните науки, която включва картографиране на големи набори от данни към стойности с фиксирана дължина. Това е процес на преобразуване на набор от данни с променлив размер в набор от данни с фиксиран размер. Способността за извършване на ефективни операции за търсене прави хеширането основна концепция в структурите на данни.

Какво е хеширане?

Алгоритъм за хеширане се използва за преобразуване на вход (като низ или цяло число) в изход с фиксиран размер (наричан хеш код или хеш стойност). След това данните се съхраняват и извличат, като се използва тази хеш стойност като индекс в масив или хеш таблица. Хеш функцията трябва да е детерминистична, което гарантира, че винаги ще дава един и същ резултат за даден вход.

Хеширането обикновено се използва за създаване на уникален идентификатор за част от данни, който може да се използва за бързо търсене на тези данни в голям набор от данни. Например, уеб браузър може да използва хеширане, за да съхранява сигурно паролите за уебсайтове. Когато потребител въведе своята парола, браузърът я преобразува в хеш стойност и я сравнява със съхранената хеш стойност, за да удостовери потребителя.

Какво е хеш ключ?

В контекста на хеширането хеш ключът (известен също като хеш стойност или хеш код) е числово или буквено-цифрово представяне с фиксиран размер, генерирано от алгоритъм за хеширане. Извлича се от входните данни, като текстов низ или файл, чрез процес, известен като хеширане.

Хеширането включва прилагане на специфична математическа функция към входните данни, която произвежда уникален хеш ключ, който обикновено е с фиксирана дължина, независимо от размера на входа. Полученият хеш ключ е по същество цифров отпечатък на оригиналните данни.

Хеш ключът служи за няколко цели. Обикновено се използва за проверки на целостта на данните, тъй като дори малка промяна във входните данни ще доведе до значително различен хеш ключ. Хеш ключовете също се използват за ефективно извличане и съхранение на данни в хеш таблици или структури от данни, тъй като позволяват бързи операции за търсене и сравнение.

Как работи хеширането?

Процесът на хеширане може да бъде разделен на три стъпки:

• Вход: Данните за хеширане се въвеждат в алгоритъма за хеширане.
• Хеш функция: Алгоритъмът за хеширане взема входните данни и прилага математическа функция, за да генерира хеш стойност с фиксиран размер. Хеш функцията трябва да бъде проектирана така, че различните входни стойности да произвеждат различни хеш стойности, а малките промени във входа да водят до големи промени в изхода.
• Изход: Връща се хеш стойността, която се използва като индекс за съхраняване или извличане на данни в структура от данни.

Алгоритми за хеширане:

Има множество алгоритми за хеширане, всеки с различни предимства и недостатъци. Най-популярните алгоритми включват следното:

• MD5: Широко използван алгоритъм за хеширане, който произвежда 128-битова хеш стойност.
• SHA-1: Популярен алгоритъм за хеширане, който произвежда 160-битова хеш стойност.
• SHA-256: По-сигурен алгоритъм за хеширане, който произвежда 256-битова хеш стойност.

Хеш функция:

Хеш функция: Хеш функцията е вид математическа операция, която приема вход (или ключ) и извежда резултат с фиксиран размер, известен като хеш код или хеш стойност. Хеш функцията трябва винаги да дава един и същ хеш код за един и същ вход, за да бъде детерминистична. Освен това хеш функцията трябва да произвежда уникален хеш код за всеки вход, който е известен като свойството хеш.

Има различни видове хеш функции, включително:

chmod 755

Метод на разделяне:

Този метод включва разделяне на ключа на размера на таблицата и вземане на остатъка като хеш стойност. Например, ако размерът на таблицата е 10 и ключът е 23, хеш стойността ще бъде 3 (23 % 10 = 3).

Метод на умножение:

Този метод включва умножаване на ключа по константа и вземане на дробната част от продукта като хеш стойност. Например, ако ключът е 23 и константата е 0,618, хеш-стойността ще бъде 2 (floor(10*(0.61823 - floor(0.61823))) = floor(2.236) = 2).

Универсално хеширане:

Този метод включва използване на произволна хеш функция от семейство хеш функции. Това гарантира, че хеш функцията не е предубедена към конкретен вход и е устойчива на атаки.

Разрешаване на сблъсъци

Едно от основните предизвикателства при хеширането е справянето с колизии, които възникват, когато две или повече входни стойности произвеждат една и съща хеш стойност. Има различни техники, използвани за разрешаване на сблъсъци, включително:

• Верижно свързване: При тази техника всеки слот за хеш таблица съдържа свързан списък на всички стойности, които имат една и съща хеш стойност. Тази техника е проста и лесна за изпълнение, но може да доведе до лоша производителност, когато свързаните списъци станат твърде дълги.
• Отворено адресиране: При тази техника, когато възникне сблъсък, алгоритъмът търси празен слот в хеш-таблицата, като изследва последователни слотове, докато се намери празен слот. Тази техника може да бъде по-ефективна от верижното свързване, когато факторът на натоварване е нисък, но може да доведе до групиране и лоша производителност, когато факторът на натоварване е висок.
• Двойно хеширане: Това е вариант на отворено адресиране, който използва втора хеш функция, за да определи следващия слот за изследване, когато възникне сблъсък. Тази техника може да помогне за намаляване на клъстерирането и подобряване на производителността.

Пример за разрешаване на сблъсък

Нека продължим с нашия пример за хеш-таблица с размер 5. Искаме да съхраним двойките ключ-стойност „Джон: 123456“ и „Мери: 987654“ в хеш-таблицата. И двата ключа произвеждат един и същ хеш код от 4, така че възниква сблъсък.

Можем да използваме верижно свързване, за да разрешим сблъсъка. Създаваме свързан списък на индекс 4 и добавяме двойките ключ-стойност към списъка. Сега хеш-таблицата изглежда така:

0:

1:

2:

3:

4: Джон: 123456 -> Мери: 987654

5:

Хеш таблица:

Хеш-таблицата е структура от данни, която съхранява данни в масив. Обикновено се избира размер за масива, който е по-голям от броя на елементите, които могат да се поберат в хеш-таблицата. Ключ се съпоставя с индекс в масива с помощта на хеш функцията.

Хеш функцията се използва за намиране на индекса, където даден елемент трябва да бъде вмъкнат в хеш таблицата, за да се добави нов елемент. Елементът се добавя към този индекс, ако няма сблъсък. Ако има сблъсък, методът за разрешаване на сблъсък се използва за намиране на следващия наличен слот в масива.

Хеш функцията се използва за намиране на индекса, в който елементът се съхранява, за да бъде извлечен от хеш таблицата. Ако елементът не е намерен на този индекс, методът за разрешаване на сблъсъци се използва за търсене на елемента в свързания списък (ако се използва верижно свързване) или в следващия наличен слот (ако се използва отворено адресиране).

Операции с хеш таблица

Има няколко операции, които могат да бъдат извършени върху хеш таблица, включително:

• Вмъкване: Вмъкване на нова двойка ключ-стойност в хеш-таблицата.
• Изтриване: Премахване на двойка ключ-стойност от хеш-таблицата.
• Търсене: Търсене на двойка ключ-стойност в хеш-таблицата.

Създаване на хеш таблица:

Хеширането често се използва за изграждане на хеш-таблици, които са структури от данни, които позволяват бързо вмъкване, изтриване и извличане на данни. Една или повече двойки ключ-стойност могат да се съхраняват във всеки от масивите от кофи, които съставляват хеш-таблица.

За да създадем хеш таблица, първо трябва да дефинираме хеш функция, която съпоставя всеки ключ с уникален индекс в масива. Една проста хеш функция може да бъде да вземе сумата от ASCII стойностите на знаците в ключа и да използва остатъка, когато се раздели на размера на масива. Въпреки това, тази хеш функция е неефективна и може да доведе до сблъсъци (два ключа, които се съпоставят с един и същ индекс).

За да избегнем сблъсъци, можем да използваме по-усъвършенствани хеш функции, които произвеждат по-равномерно разпределение на хеш стойностите в масива. Един популярен алгоритъм е хеш функцията djb2, която използва побитови операции за генериране на хеш стойност:

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

Тази функция за хеширане приема низ като вход и връща хеш-стойност с дълго цяло число без знак. Функцията инициализира хеш стойност от 5381 и след това итерира всеки знак в низа, като използва побитови операции за генериране на нова хеш стойност. Връща се крайната хеш стойност.

Хеш таблици в C++

В C++ стандартната библиотека предоставя клас контейнер на хеш таблица, наречен unordered_map. Контейнерът unordered_map е реализиран с помощта на хеш-таблица и осигурява бърз достъп до двойки ключ-стойност. Контейнерът unordered_map използва хеш функция за изчисляване на хеш кода на ключовете и след това използва отворено адресиране за разрешаване на сблъсъци.

За да използвате контейнера unordered_map в C++, трябва да включите заглавния файл. Ето пример за това как да създадете контейнер unordered_map в 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; } 

Обяснение:

меню за настройки на android

• Тази програма демонстрира използването на контейнера unordered_map в C++, който се реализира с помощта на хеш-таблица и осигурява бърз достъп до двойки ключ-стойност.
• Първо, програмата включва необходимите заглавни файлове: и.
• След това програмата създава празен контейнер unordered_map, наречен my_map, който има ключове за низове и цели числа. Това се прави с помощта на синтаксиса std::unordered_map my_map;
• След това програмата вмъква три двойки ключ-стойност в контейнера my_map с помощта на оператора []: 'apple' със стойност 10, 'banana' със стойност 20 и 'orange' със стойност 30.
• Това се прави с помощта на синтаксиса my_map['apple'] = 10;, my_map['banana'] = 20; и my_map['orange'] = 30; съответно.
• Накрая програмата отпечатва стойността, свързана с ключа „банан“, използвайки оператора [] и обекта std::cout.

Резултат от програмата:

Вмъкване на данни в хеш таблица

За да вмъкнем двойка ключ-стойност в хеш-таблица, първо трябва да добавим индекс в масива, за да съхраним двойката ключ-стойност. Ако друг ключ се съпостави със същия индекс, имаме сблъсък и трябва да го обработим по подходящ начин. Един често срещан метод е да се използва верижно свързване, при което всяка група в масива съдържа свързан списък от двойки ключ-стойност, които имат една и съща хеш стойност.

Ето пример за това как да вмъкнете двойка ключ-стойност в хеш таблица с помощта на верижно свързване:

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

Обяснение:

• Първо се дефинира структура, наречена възел, която представлява единичен възел в хеш-таблицата.
• Всеки възел има три члена: ключ char* за съхраняване на ключа, int стойност за съхраняване на свързаната стойност и указател към друг възел, извикан next за обработка на сблъсъци в хеш-таблицата с помощта на свързан списък.
• Масив от указатели на възли, наречен hash_table, се декларира с размер 100. Този масив ще се използва за съхраняване на елементите на хеш-таблицата.
• Функцията за вмъкване приема ключ char* и int стойност като параметри.
• Започва с изчисляване на хеш стойността за дадения ключ с помощта на хеш функцията, за която се предполага, че е дефинирана другаде в програмата.
• След това хеш-стойността се редуцира, за да се побере в размера на масива hash_table, като се използва модулният оператор % 100.
• Нов възел се създава с помощта на динамично разпределение на паметта (malloc(sizeof(node))) и неговите членове (ключ, стойност и следващ) се присвояват съответно с предоставения ключ, стойност и NULL.
• Ако съответният слот в масива hash_table е празен (NULL), което показва, че не е настъпил сблъсък, новият възел се присвоява директно на този слот (hash_table[hash_value] = new_node).

Ако обаче вече има възел на този индекс в масива hash_table, функцията трябва да се справи със сблъсъка. Той преминава през свързания списък, започвайки от текущия възел (hash_table[hash_value]) и преминава към следващия възел, докато стигне до края (curr_node->next != NULL). След като бъде достигнат краят на списъка, новият възел се добавя като следващ възел (curr_node->next = new_node).

Внедряване на хеширане в C++:

Нека видим имплементация на хеширане в C++, използвайки отворено адресиране и линейно изследване за разрешаване на сблъсъци. Ще имплементираме хеш таблица, която съхранява цели числа.

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