hash table c programs implement hash table
Този урок обяснява хеш таблици на C ++ и хеш карти. Също така ще научите за приложенията за хеш таблици и внедряването в C ++:
Хеширането е техника, при която можем да картографираме голямо количество данни в по-малка таблица, използвайки „хеш функция“.
Използвайки техниката на хеширане, можем да търсим данните по-бързо и ефективно в сравнение с други техники за търсене като линейно и двоично търсене.
Нека разберем техниката на хеширане с пример в този урок.
=> Прочетете серията Easy C ++ Training.
Какво ще научите:
Хеширане в C ++
Нека вземем пример за колежанска библиотека, която съхранява хиляди книги. Книгите са подредени според теми, отдели и т.н. Но все пак във всеки раздел ще има множество книги, които по този начин затрудняват търсенето на книги.
По този начин, за да преодолеем тази трудност, ние присвояваме уникален номер или ключ на всяка книга, така че незабавно да знаем местоположението на книгата. Това наистина се постига чрез хеширане.
Продължавайки с нашия пример за библиотека, вместо да идентифицираме всяка книга въз основа на нейния отдел, предмет, раздел и т.н., което може да доведе до много дълъг низ, ние изчисляваме уникална целочислена стойност или ключ за всяка книга в библиотеката, използвайки уникална функция и съхранявайте тези ключове в отделна таблица.
Уникалната функция, спомената по-горе, се нарича „Hash функция“, а отделната таблица се нарича „Hash Table“. Хеш функция се използва за картографиране на дадената стойност към определен уникален ключ в хеш таблицата. Това води до по-бърз достъп до елементи. Колкото по-ефективна е функцията за хеширане, толкова по-ефективно ще бъде картографирането на всеки елемент към уникалния ключ.
Нека разгледаме хеш функция h (x) което картографира стойността „ х ”В„ 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. В този случай hash_code за ключова стойност 12 ще бъде 2. (12% 10 = 2).
най-доброто безплатно сканиране и ремонт на компютър
Но в хеш таблицата вече имаме съпоставяне на ключ-стойност 22 за hash_code 2, както е показано по-долу:
Както е показано по-горе, имаме един и същ хеш код за две стойности, 12 и 22, т.е. 2. Когато една или повече ключови стойности се приравняват на едно и също място, това води до сблъсък. По този начин местоположението на хеш кода вече е заето от една ключова стойност и има друга ключова стойност, която трябва да бъде поставена на същото място.
В случай на хеширане, дори ако имаме хеш таблица с много големи размери, сблъсъкът непременно трябва да е налице. Това е така, защото като цяло намираме малка уникална стойност за голям ключ, следователно е напълно възможно една или повече стойности да имат един и същ хеш код по всяко време.
Като се има предвид, че сблъсъкът е неизбежен при хеширане, винаги трябва да търсим начини да предотвратим или разрешим сблъсъка. Има различни техники за разрешаване на сблъсъци, които можем да използваме, за да разрешим сблъсъка, възникнал по време на хеширане.
Техники за разрешаване на сблъсъци
Следват техниките, които можем да използваме за разрешаване на сблъсък в хеш таблицата.
Отделно верижно обвързване (Open Hashing)
Това е най-често срещаната техника за разрешаване на сблъсък. Това е известно още като отворено хеширане и се прилага с помощта на свързан списък.
В отделна техника на веригиране всеки запис в хеш таблицата е свързан списък. Когато ключът съвпада с хеш кода, той се въвежда в списък, съответстващ на този конкретен хеш код. По този начин, когато два ключа имат един и същ хеш код, тогава и двата записа се въвеждат в свързания списък.
За горния пример по-долу е представено отделно верижно обвързване.
Горната схема представлява верига. Тук използваме функцията mod (%). Виждаме, че когато две ключови стойности се равняват на един и същ хеш код, тогава свързваме тези елементи с този хеш код с помощта на свързан списък.
Ако ключовете са равномерно разпределени в хеш таблицата, тогава средната цена за търсене на конкретния ключ зависи от средния брой ключове в този свързан списък. По този начин отделната верига остава ефективна, дори когато има увеличение на броя на влизанията, отколкото на слотовете.
Най-лошият случай за отделна верига е, когато всички ключове се равняват на един и същ хеш код и по този начин се вмъкват само в един свързан списък. Следователно трябва да търсим всички записи в хеш таблицата и разходите, които са пропорционални на броя на ключовете в таблицата.
Линейно сондиране (отворено адресиране / затворено хеширане)
При техниката на отворено адресиране или линейно сондиране всички записи за запис се съхраняват в самата хеш таблица. Когато ключ-стойност се преобразува в хеш код и позицията, посочена от хеш код, е незаета, тогава стойността на ключа се вмъква на това място.
Ако позицията вече е заета, след това с помощта на сондираща последователност стойността на ключа се вмъква в следващата позиция, която е незаета в хеш таблицата.
За линейно сондиране хеш функцията може да се промени, както е показано по-долу:
hash = хеш% hashTableSize
hash = (hash + 1)% hashTableSize
hash = (hash + 2)% hashTableSize
hash = (hash + 3)% hashTableSize
Виждаме, че в случай на линейно сондиране интервалът между слотовете или последователните сонди е постоянен, т.е.1.
В горната диаграма виждаме, че в 0тиместоположение въвеждаме 10 с помощта на хеш функцията “hash = hash% hash_tableSize”.
Сега елементът 70 също се равнява на местоположение 0 в хеш таблицата. Но това място вече е заето. Следователно с помощта на линейно сондиране ще намерим следващото място, което е 1. Тъй като това място е незаето, ние поставяме ключа 70 на това място, както е показано със стрелка.
Получената таблица на хеш е показана по-долу.
Линейното сондиране може да страда от проблема с „Първичното клъстериране“, при който съществува вероятност непрекъснатите клетки да се заемат и вероятността за вмъкване на нов елемент да се намали.
Също така, ако два елемента получат една и съща стойност при първата хеш функция, тогава и двата елемента ще следват една и съща последователност на сондата.
Квадратично сондиране
Квадратичното сондиране е същото като линейното сондиране, като единствената разлика е интервалът, използван за сондиране. Както подсказва името, тази техника използва нелинейно или квадратно разстояние, за да заеме слотове, когато се случи сблъсък вместо линейно разстояние.
При квадратично сондиране интервалът между слотовете се изчислява чрез добавяне на произволна полиномиална стойност към вече хеширания индекс. Тази техника намалява първичната клъстеризация в значителна степен, но не подобрява вторичната клъстеризация.
Двойно хеширане
Техниката на двойно хеширане е подобна на линейното сондиране. Единствената разлика между двойното хеширане и линейното сондиране е, че при техниката на двойно хеширане интервалът, използван за сондиране, се изчислява с помощта на две хеш функции. Тъй като прилагаме хеш функцията към ключа един след друг, тя елиминира първичното клъстериране, както и вторичното клъстериране.
Разлика между верига (отворено хеширане) и линейно сондиране (отворено адресиране)
| Верига (Open Hashing) | Линейно сондиране (отворено адресиране) |
|---|---|
| Стойностите на ключовете могат да се съхраняват извън таблицата, като се използва отделен свързан списък. | Стойностите на ключовете трябва да се съхраняват само в таблицата. |
| Броят на елементите в хеш таблицата може да надвишава размера на хеш таблицата. | Броят на елементите, присъстващи в хеш таблицата, няма да надвишава броя на индексите в хеш таблицата. |
| Изтриването е ефективно в техниката на веригиране. | Изтриването може да бъде тромаво. Може да се избегне, ако не се изисква. |
| Тъй като за всяко място се поддържа отделен свързан списък, заетото пространство е голямо. | Тъй като всички записи са поместени в една и съща таблица, заетото място е по-малко. |
Внедряване на хеш таблица на C ++
Можем да приложим хеширане, като използваме масиви или свързани списъци за програмиране на хеш таблиците. В C ++ имаме и функция, наречена „хеш карта“, която е структура, подобна на хеш таблица, но всеки запис е двойка ключ-стойност. В C ++ се нарича хеш карта или просто карта. Хеш картата в C ++ обикновено е неподредена.
Има заглавие, дефинирано в библиотеката на стандартните шаблони (STL) на C ++, което реализира функционалността на картите. Ние покрихме Карти на STL подробно в нашия урок за STL.
Следващото изпълнение е за хеширане, като се използват свързаните списъци като структура на данни за хеш таблицата. Ние също използваме “Chaining” като техника за разрешаване на сблъсък при това изпълнение.
#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) за операции по вмъкване, изтриване и търсене. Хеширането се реализира най-вече чрез използване на хеш функция, която изчислява уникална по-малка стойност на ключа за големи записи на данни. Можем да реализираме хеширане с помощта на масиви и свързани списъци.
Винаги, когато един или повече записи от данни се приравняват на едни и същи стойности на ключове, това води до сблъсък. Виждали сме различни техники за разрешаване на сблъсъци, включително линейно сондиране, вериги и др. Виждали сме и прилагането на хеширане в C ++.
В заключение можем да кажем, че хеширането е най-ефективната структура на данни в света на програмирането.
=> Потърсете тук цялата серия за обучение на C ++.
Препоръчително четене
- Как да напиша сложни тестове за бизнес логика, използвайки техниката на таблицата за вземане на решения
- Таблица за проверка на полето (FVT): Техника за проектиране на тестове за проверка на полето
- Урок за QTP # 15 - Използване на текстови точки, таблици и странични контролни точки в QTP
- КАРТИ В STL
- Всичко за рутерите: Видове рутери, маршрутизираща таблица и IP маршрутизация
- Топ 40 най-добри въпроса и отговори за интервю за MySQL (2021 въпроса)
- Топ 90 въпроси и отговори за интервю за SQL (ПОСЛЕДНИ)
- Команди на програми за помощни програми на Unix: Кой, Човек, Намери Су, Судо (Част Г)