hash table c programs implement hash table
Цей підручник пояснює хеш-таблиці C ++ та хеш-карти. Ви також дізнаєтесь про застосування та впровадження хеш-таблиць у C ++:
Хешування - це техніка, за допомогою якої ми можемо зіставити велику кількість даних у меншу таблицю за допомогою “хеш-функції”.
Використовуючи техніку хешування, ми можемо шукати дані швидше та ефективніше порівняно з іншими методами пошуку, такими як лінійний та двійковий пошук.
Давайте розберемося в техніці хешування на прикладі цього підручника.
=> Прочитайте серію навчальних програм Easy C ++.
лиття char в int c ++
Що ви дізнаєтесь:
Хешування в C ++
Візьмемо приклад бібліотеки коледжу, де зберігаються тисячі книг. Книги розташовані відповідно до предметів, відділів тощо. Але все ж у кожному розділі буде безліч книг, які тим самим ускладнюють пошук книг.
Таким чином, щоб подолати цю складність, ми присвоюємо кожній книзі унікальний номер або ключ, щоб миттєво дізнатись про місцезнаходження книги. Це справді досягається шляхом хешування.
Продовжуючи приклад нашої бібліотеки, замість ідентифікації кожної книги на основі її відділу, теми, розділу тощо, що може призвести до дуже довгого рядка, ми обчислюємо унікальне ціле значення або ключ для кожної книги в бібліотеці, використовуючи унікальну функцію і зберігайте ці ключі в окремій таблиці.
Унікальна функція, згадана вище, називається “функцією хеш-функції”, а окрема таблиця - таблицею хеш-таблиці. Хеш-функція використовується для зіставлення заданого значення з певним унікальним ключем у Хеш-таблиці. Це призводить до швидшого доступу до елементів. Чим ефективніше функція хешування, тим ефективніше буде відображення кожного елемента в унікальний ключ.
Розглянемо хеш-функцію h (x) що відображає значення “ х ”На“ х% 10 ”У масиві. Для даних даних ми можемо створити хеш-таблицю, що містить ключі, хеш-коди чи хеші, як показано на діаграмі нижче.
На наведеній вище схемі ми бачимо, що записи в масиві зіставляються з їхніми позиціями в хеш-таблиці за допомогою хеш-функції.
Таким чином, можна сказати, що хешування реалізується двома кроками, як зазначено нижче:
# 1) Значення перетворюється в унікальний цілочисельний ключ або хеш за допомогою хеш-функції. Він використовується як індекс для зберігання вихідного елемента, який потрапляє в хеш-таблицю.
На наведеній вище схемі значення 1 у хеш-таблиці є унікальним ключем для зберігання елемента 1 із масиву даних, поданого на LHS діаграми.
# два) Елемент із масиву даних зберігається в хеш-таблиці, де його можна швидко отримати за допомогою хеш-ключа. На наведеній вище схемі ми побачили, що ми зберегли всі елементи в хеш-таблиці після обчислення їх відповідних розташувань за допомогою хеш-функції. Ми можемо використовувати наступні вирази для отримання хеш-значень та індексу.
hash = hash_func(key) index = hash % array_sizeХеш-функція
Ми вже згадували, що ефективність відображення залежить від ефективності хеш-функції, яку ми використовуємо.
Хеш-функція в основному повинна відповідати наступним вимогам:
- Простота обчислення: Хеш-функція повинна легко обчислювати унікальні ключі.
- Менше зіткнень: Коли елементи прирівнюються до тих самих ключових значень, відбувається зіткнення. У використовуваній хеш-функції має бути мінімум зіткнень, наскільки це можливо. Оскільки зіткнення неодмінно трапляються, ми повинні використовувати відповідні методи вирішення колізій, щоб подбати про зіткнення.
- Рівномірний розподіл: Хеш-функція повинна привести до рівномірного розподілу даних по хеш-таблиці і тим самим запобігти кластеризації.
Хеш-таблиця C ++
Хеш-таблиця або хеш-карта - це структура даних, яка зберігає вказівники на елементи вихідного масиву даних.
У нашому прикладі бібліотеки хеш-таблиця для бібліотеки міститиме вказівники на кожну з книг у бібліотеці.
Наявність записів у хеш-таблиці полегшує пошук певного елемента в масиві.
Як вже було видно, хеш-таблиця використовує хеш-функцію для обчислення індексу в масиві сегментів або слотів, за допомогою яких можна знайти потрібне значення.
Розглянемо інший приклад із наступним масивом даних:
Припустимо, що ми маємо хеш-таблицю розміром 10, як показано нижче:
Тепер давайте використаємо хеш-функцію, наведену нижче.
Hash_code = Key_value % size_of_hash_tableЦе буде дорівнювати Hash_code = Значення ключа_10
Використовуючи вищезазначену функцію, ми прив'язуємо значення ключів до розташування хеш-таблиці, як показано нижче.
| Елемент даних | Хеш-функція | Хеш-код |
|---|---|---|
| 22 | 22% 10 = 2 | два |
| 25 | 25% 10 = 5 | 5 |
| 27 | 27% 10 = 7 | 7 |
| 46 | 46% 10 = 6 | 6 |
| 70 | 70% 10 = 0 | 0 |
| 89 | 89% 10 = 9 | 9 |
| 31 | 31% 10 = 1 | 1 |
Використовуючи наведену вище таблицю, ми можемо представити хеш-таблицю наступним чином.
Таким чином, коли нам потрібен доступ до елемента з хеш-таблиці, для пошуку потрібно просто час O (1).
Зіткнення
Зазвичай ми обчислюємо хеш-код, використовуючи хеш-функцію, щоб ми могли зіставити значення ключа з хеш-кодом у хеш-таблиці. У наведеному вище прикладі масиву даних вставимо значення 12. У такому випадку хеш-код для значення ключа 12 буде 2. (12% 10 = 2).
Але в хеш-таблиці ми вже маємо відображення ключа-значення 22 для hash_code 2, як показано нижче:
Як показано вище, у нас однаковий хеш-код для двох значень, 12 і 22, тобто 2. Коли одне або кілька значень ключа прирівнюються до одного і того ж місця, це призводить до зіткнення. Таким чином, місце розташування хеш-коду вже зайняте одним значенням ключа, і є інше значення ключа, яке потрібно розмістити в тому ж місці.
У випадку хешування, навіть якщо ми маємо хеш-таблицю дуже великого розміру, зіткнення обов’язково має бути. Це тому, що ми знаходимо невелике унікальне значення для великого ключа загалом, отже, цілком можливо, що одне або кілька значень мають однаковий хеш-код у будь-який момент часу.
Враховуючи, що зіткнення неминуче при хешуванні, ми завжди повинні шукати шляхи запобігання або вирішення зіткнення. Існують різні методи розв’язання зіткнень, які ми можемо застосувати для вирішення зіткнення, що відбувається під час хешування.
Методи вирішення зіткнень
Нижче наведено методи, які ми можемо застосувати для вирішення зіткнень у хеш-таблиці.
Окремий ланцюжок (відкритий хешування)
Це найпоширеніша техніка вирішення зіткнень. Це також відомо як відкрите хешування і реалізується за допомогою пов'язаного списку.
новий приватний сервер world of warcraft - -
В окремій техніці ланцюжка кожен запис у хеш-таблиці є пов’язаним списком. Коли ключ відповідає хеш-коду, він вноситься до списку, що відповідає цьому конкретному хеш-коду. Таким чином, коли два ключі мають однаковий хеш-код, тоді обидва записи вносяться до зв’язаного списку.
У наведеному вище прикладі окремий ланцюжок представлений нижче.
Наведена діаграма представляє ланцюжок. Тут ми використовуємо функцію mod (%). Ми бачимо, що коли два ключові значення прирівнюються до одного і того ж хеш-коду, тоді ми пов'язуємо ці елементи з цим хеш-кодом за допомогою пов'язаного списку.
Якщо ключі рівномірно розподілені по хеш-таблиці, тоді середня вартість пошуку конкретного ключа залежить від середньої кількості ключів у зв’язаному списку. Таким чином, роздільна ланцюжок залишається ефективною навіть тоді, коли кількість записів збільшується, ніж слотів.
Найгірший випадок для окремого ланцюжка - це коли всі ключі прирівнюються до одного і того ж хеш-коду і, таким чином, вставляються лише в один пов'язаний список. Отже, нам потрібно шукати всі записи в хеш-таблиці та вартість, які пропорційні кількості ключів у таблиці.
Лінійне зондування (відкрита адресація / закритий хешування)
У техніці відкритої адресації або лінійного зондування всі записи введення зберігаються в самій хеш-таблиці. Коли ключ-значення відображається у хеш-код і позиція, на яку вказує хеш-код, не зайнята, тоді значення ключа вставляється в це місце.
Якщо позиція вже зайнята, то за допомогою послідовності зондування значення ключа вставляється в наступну позицію, яка не зайнята в хеш-таблиці.
Для лінійного зондування хеш-функція може змінюватися, як показано нижче:
hash = хеш% hashTableSize
хеш = (хеш + 1)% hashTableSize
hash = (hash + 2)% hashTableSize
хеш = (хеш + 3)% hashTableSize
Ми бачимо, що у випадку лінійного зондування інтервал між слотами або послідовними зондами є постійним, тобто 1.
На наведеній вище схемі ми бачимо, що в 0горозташування ми вводимо 10 за допомогою хеш-функції “hash = hash% hash_tableSize”.
Тепер елемент 70 також прирівнює до місця 0 у хеш-таблиці. Але це місце вже зайняте. Отже, використовуючи лінійне зондування, ми знайдемо наступне місце, яке дорівнює 1. Оскільки це місце незайняте, ми розміщуємо ключ 70 у цьому місці, як показано стрілкою.
Отримана таблиця хеш-зображень наведена нижче.
Лінійне зондування може страждати від проблеми «Первинного скупчення», при якому існує ймовірність того, що суцільні комірки можуть зайнятись, і ймовірність вставки нового елемента зменшується.
Крім того, якщо два елементи отримують одне і те ж значення при першій хеш-функції, тоді обидва ці елементи будуть дотримуватися однакової послідовності зондування.
Квадратичне зондування
Квадратичне зондування те саме, що лінійне зондування з тією лише різницею, що є інтервал, що використовується для зондування. Як випливає з назви, цей метод використовує нелінійну або квадратичну відстань, щоб зайняти слоти, коли відбувається зіткнення замість лінійної відстані.
При квадратичному зондуванні інтервал між слотами обчислюється шляхом додавання довільного значення полінома до вже хешованого індексу. Цей метод значно зменшує первинну кластеризацію, але не покращує вторинну кластеризацію.
Подвійне хешування
Техніка подвійного перемішування схожа на лінійне зондування. Єдина різниця між подвійним хешуванням та лінійним зондуванням полягає в тому, що в техніці подвійного хешування інтервал, який використовується для зондування, обчислюється за допомогою двох хеш-функцій. Оскільки ми застосовуємо хеш-функцію до ключа один за одним, це виключає первинну кластеризацію, а також вторинну кластеризацію.
Різниця між ланцюжком (відкритий хешування) та лінійним зондуванням (відкрита адресація)
| Мережа (відкритий хешування) | Лінійне зондування (відкрита адресація) |
|---|---|
| Значення ключів можна зберігати поза таблицею за допомогою окремого пов'язаного списку. | Значення ключів слід зберігати лише в таблиці. |
| Кількість елементів у хеш-таблиці може перевищувати розмір хеш-таблиці. | Кількість елементів, присутніх у хеш-таблиці, не перевищуватиме кількість індексів у хеш-таблиці. |
| Делеція є ефективною в техніці ланцюжків. | Видалення може бути громіздким. Можна уникнути, якщо не потрібно. |
| Оскільки для кожного місця ведеться окремий зв’язаний список, займаний простір великий. | Оскільки всі записи розміщені в одній таблиці, місце займає менше. |
Впровадження хеш-таблиці C ++
Ми можемо реалізувати хешування, використовуючи масиви або зв’язані списки для програмування хеш-таблиць. У C ++ ми також маємо функцію під назвою «карта хешу», яка є структурою, подібною до хеш-таблиці, але кожен запис є парою ключ-значення. У C ++ це називається хеш-карта або просто карта. Карта хешів у C ++ зазвичай не упорядкована.
Існує заголовок, визначений у стандартній бібліотеці шаблонів (STL) на C ++, який реалізує функціональність карт. Ми охопили Карти STL детально в нашому посібнику з STL.
Наступна реалізація призначена для хешування з використанням пов'язаних списків як структури даних для хеш-таблиці. У цій реалізації ми також використовуємо “ланцюжок” як метод розв’язання зіткнень.
#include #include using namespace std; class Hashing { int hash_bucket; // No. of buckets // Pointer to an array containing buckets list *hashtable; public: Hashing(int V); // Constructor // inserts a key into hash table void insert_key(int val); // deletes a key from hash table void delete_key(int key); // hash function to map values to key int hashFunction(int x) { return (x % hash_bucket); } void displayHash(); }; Hashing::Hashing(int b) { this->hash_bucket = b; hashtable = new list (hash_bucket); } //insert to hash table void Hashing::insert_key(int key) { int index = hashFunction(key); hashtable(index).push_back(key); } void Hashing::delete_key(int key) { // get the hash index for key int index = hashFunction(key); // find the key in (inex)th list list :: iterator i; for (i = hashtable(index).begin(); i != hashtable(index).end(); i++) { if (*i == key) break; } // if key is found in hash table, remove it if (i != hashtable(index).end()) hashtable(index).erase(i); } // display the hash table void Hashing::displayHash() { for (int i = 0; i ' << x; cout << endl; } } // main program int main() { // array that contains keys to be mapped int hash_array() = {11,12,21, 14, 15}; int n = sizeof(hash_array)/sizeof(hash_array(0)); Hashing h(7); // Number of buckets = 7 //insert the keys into the hash table for (int i = 0; i < n; i++) h.insert_key(hash_array(i)); // display the Hash table cout<<'Hash table created:'< Вихід:
Створена хеш-таблиця:
0 -> 21 -> 14
1 -> 15
два
3
4 -> 11
5 -> 12
6
Хеш-таблиця після видалення ключа 12:
0 -> 21 -> 14
1 -> 15
два
3
4 -> 11
5
6
На виході виводиться хеш-таблиця, яка створена розміром 7. Ми використовуємо ланцюжок для вирішення зіткнення. Хеш-таблицю відображаємо після видалення однієї з клавіш.
Застосування хешування
# 1) Перевірка паролів: Перевірка паролів зазвичай здійснюється за допомогою криптографічних хеш-функцій. Після введення пароля система обчислює хеш пароля, а потім відправляється на сервер для перевірки. На сервері зберігаються хеш-значення вихідних паролів.
# 2) Структури даних: Різні структури даних, такі як unordered_set і unordered_map у C ++, словники в python або C #, HashSet і хеш-карта в Java, використовують пару ключ-значення, де ключі є унікальними значеннями. Значення можуть бути однаковими для різних ключів. Для реалізації цих структур даних використовується хешування.
# 3) Дайджест повідомлення: Це ще одна програма, яка використовує криптографічний хеш. У дайджестах повідомлень ми обчислюємо хеш для даних, що надсилаються та отримуються або навіть файлів, і порівнюємо їх із збереженими значеннями, щоб переконатися, що файли даних не підробляються. Найпоширенішим алгоритмом тут є “SHA 256”.
# 4) Робота компілятора: Коли компілятор компілює програму, ключові слова для мови програмування зберігаються інакше, ніж інші ідентифікує. Компілятор використовує хеш-таблицю для зберігання цих ключових слів.
# 5) Індексація бази даних: Хеш-таблиці використовуються для індексації баз даних та структур даних на основі дисків.
# 6) Асоціативні масиви: Асоціативні масиви - це масиви, індекси яких мають тип даних, відмінний від цілочисельних рядків чи інших типів об’єктів. Хеш-таблиці можна використовувати для реалізації асоціативних масивів.
Висновок
Хешування є найбільш широко використовуваною структурою даних, оскільки для операцій вставки, видалення та пошуку потрібен постійний час O (1). Хешування в основному реалізується за допомогою хеш-функції, яка обчислює унікальне менше значення ключа для великих записів даних. Ми можемо реалізувати хешування за допомогою масивів та пов'язаних списків.
скільки типів файлів є python
Всякий раз, коли один або кілька записів даних прирівнюються до однакових значень ключів, це призводить до зіткнення. Ми бачили різні методи розв’язання зіткнень, включаючи лінійне зондування, ланцюжок тощо. Ми також бачили реалізацію хешування в C ++.
На закінчення можна сказати, що хешування на сьогоднішній день є найефективнішою структурою даних у світі програмування.
=> Шукайте тут цілу серію навчальних програм C ++.
Рекомендована література
- Як писати складні сценарії тестування бізнес-логіки, використовуючи техніку таблиць рішень
- Таблиця перевірки поля (FVT): Техніка проектування випробувань для перевірки поля
- Підручник з QTP # 15 - Використання контрольної точки в області тексту, таблиці та сторінки в QTP
- КАРТИ У STL
- Все про маршрутизатори: типи маршрутизаторів, таблиця маршрутизації та IP-маршрутизація
- 40 найкращих запитань та відповідей на інтерв’ю MySQL (2021 запитання)
- Найпопулярніші 90 запитань та відповідей на інтерв’ю SQL (ОСТАННІ)
- Команди програм Unix Utilities: Which, Man, Find Su, Sudo (Частина D)