TechCodeview

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

Хешування — це популярна техніка в інформатиці, яка передбачає зіставлення великих наборів даних із значеннями фіксованої довжини. Це процес перетворення набору даних змінного розміру в набір даних фіксованого розміру. Здатність виконувати ефективні операції пошуку робить хешування важливою концепцією в структурах даних.

Що таке хешування?

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

Хешування зазвичай використовується для створення унікального ідентифікатора для частини даних, який можна використовувати для швидкого пошуку цих даних у великому наборі даних. Наприклад, веб-браузер може використовувати хешування для безпечного зберігання паролів веб-сайтів. Коли користувач вводить свій пароль, браузер перетворює його на хеш-значення та порівнює його зі збереженим хеш-значенням для автентифікації користувача.

Що таке хеш-ключ?

У контексті хешування хеш-ключ (також відомий як хеш-значення або хеш-код) — це числове або буквено-цифрове представлення фіксованого розміру, згенероване алгоритмом хешування. Його отримують із вхідних даних, таких як текстовий рядок або файл, за допомогою процесу, відомого як хешування.

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

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

Як працює хешування?

Процес хешування можна розбити на три етапи:

• Вхід: дані для хешування вводяться в алгоритм хешування.
• Хеш-функція. Алгоритм хешування бере вхідні дані та застосовує математичну функцію для створення хеш-значення фіксованого розміру. Хеш-функція має бути розроблена так, щоб різні вхідні значення створювали різні хеш-значення, а невеликі зміни у вхідних даних викликали значні зміни у вихідних даних.
• Вихід: повертається хеш-значення, яке використовується як індекс для зберігання або отримання даних у структурі даних.

Алгоритми хешування:

Існує безліч алгоритмів хешування, кожен з яких має свої переваги та недоліки. До найпопулярніших алгоритмів можна віднести наступні:

• MD5: широко використовуваний алгоритм хешування, який створює 128-бітове хеш-значення.
• SHA-1: популярний алгоритм хешування, який створює 160-бітове хеш-значення.
• SHA-256: безпечніший алгоритм хешування, який створює 256-бітове хеш-значення.

Хеш-функція:

Хеш-функція: хеш-функція — це тип математичної операції, яка приймає вхідні дані (або ключ) і виводить результат фіксованого розміру, відомий як хеш-код або хеш-значення. Щоб бути детермінованою, хеш-функція завжди повинна видавати однаковий хеш-код для того самого вхідного елемента. Крім того, хеш-функція повинна виробляти унікальний хеш-код для кожного введення, який відомий як властивість хешування.

Існують різні типи хеш-функцій, зокрема:

Метод поділу:

Цей метод передбачає ділення ключа на розмір таблиці та прийняття залишку як хеш-значення. Наприклад, якщо розмір таблиці дорівнює 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; } 

Пояснення:

• Ця програма демонструє використання контейнера 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.

Вихід програми:

Вставлення даних у хеш-таблицю

Щоб вставити пару ключ-значення в хеш-таблицю, нам спочатку потрібно додати індекс до масиву для зберігання пари ключ-значення. Якщо інший ключ відповідає тому самому індексу, у нас виникла колізія, і її потрібно обробити належним чином. Одним із поширених методів є використання ланцюжків, коли кожне відро в масиві містить зв’язаний список пар ключ-значення, які мають однакове хеш-значення.

Ось приклад того, як вставити пару ключ-значення в хеш-таблицю за допомогою ланцюжка:

програмування struct array c

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

Пояснення:

• Спочатку визначається структура під назвою 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;>