Въведение в функцията на хеширане в С
Тази статия има кратка бележка за хеширането (хеш таблица и хеш функция). Най-важното понятие е „търсене“, което определя сложността на времето. За да се намали сложността на времето от всяка друга концепция за хеширане на структурата на данните, се въвежда O (1) време в средния случай и в най-лошия случай ще отнеме O (n) време.
Хеширането е техника с по-бърз достъп до елементи, която картографира дадените данни с по-малък ключ за сравнения. По принцип в тази техника ключовете се проследяват с помощта на хеш функция в таблица, известна като хеш таблица.
Какво е Hash функция?
Хеш функцията е функция, която използва операцията с постоянно време, за да съхранява и извлича стойността от хеш таблицата, която се прилага върху ключовете като цели числа и това се използва като адрес за стойности в хеш таблицата.
Видове функция на хеш
Видовете хеш-функции са обяснени по-долу:
1. Метод на разделяне
При този метод хеш функцията зависи от остатъка от разделение.
Пример: елементите, които трябва да бъдат поставени в хеш таблицата, са 42, 78, 89, 64 и нека вземем размера на таблицата като 10.
Хеш (ключ) = Елементи% размер на таблицата;
2 = 42% 10;
8 = 78% 10;
9 = 89% 10;
4 = 64% 10;
Представянето на таблицата може да се види по-долу:
2. Метод на средния квадрат
При този метод средната част на елемента в квадрат е взета като индекс.
Елементът, който трябва да бъде поставен в хеш таблицата, е 210, 350, 99, 890, а размерът на таблицата е 100.
210 * 210 = 44100, индекс = 1, тъй като средната част на резултата (44100) е 1.
350 * 350 = 122500, индекс = 25, тъй като средната част на резултата (122500) е 25.
99 * 99 = 9801, индекс = 80, тъй като средната част на резултата (9801) е 80.
890 * 890 = 792100, индекс = 21, тъй като средната част на резултата (792100) е 21.
3. Метод на сгъване на цифри
При този метод елементът, който трябва да бъде поставен в таблицата uh, е пеещ хеш ключ, който се получава чрез разделяне на елементите на различни части и след това комбиниране на частите, като се извършват някои прости математически операции.
Елементът за поставяне е 23576623, 34687734.
- хеш (ключ) = 235 + 766 + 23 = 1024
- ключ за хеш) = 34 + 68 + 77 + 34 = 213
Да предположим, че в тези видове хеширане имаме числа от 1- 100 и размер на хеш таблицата = 10. Елементи = 23, 12, 32
Хеш (ключ) = 23% 10 = 3;
Хеш (ключ) = 12% 10 = 2;
Хеш (ключ) = 32% 10 = 2;
От горния пример забележете, че и двата елемента 12 и 32 сочат към 2-ро място в таблицата, където не е възможно да се напишат и двете на едно и също място, такъв проблем е известен като сблъсък. За да се избегнат този вид проблеми, има някои техники на хеш-функции, които могат да се използват.
Видове техники за разрешаване на сблъсък
Нека обсъдим видовете техники за разрешаване на сблъсъка:
1. Оковаване на вериги
В този метод, както подсказва името, той осигурява верига от полета за записа в таблицата, съдържащ два записа на елементи. Така че винаги, когато възникнат подобни сблъсъци, кутиите действат като свързан списък.
Пример: 23, 12, 32 с размер на таблицата 10.
Хеш (ключ) = 23% 10 = 3;
Хеш (ключ) = 12% 10 = 2;
Хеш (ключ) = 32% 10 = 2;
2. Отворете адресиране
- Линейно сондиране
Това е друг метод за решаване на проблеми при сблъсък. Както се казва в името, когато се случи сблъсък, два елемента трябва да бъдат поставени върху един и същ запис в таблицата, но по този метод можем да търсим следващо празно място или запис в таблицата и да поставим втория елемент. Това отново може да доведе до друг проблем; ако не намерим празен запис в таблицата, това води до групиране. По този начин това е известно като проблем с клъстеринг, който може да бъде решен по следния метод.
Пример: 23, 12, 32 с размер на таблицата 10
Хеш (ключ) = 23% 10 = 3;
Хеш (ключ) = 12% 10 = 2;
Хеш (ключ) = 32% 10 = 2;
На тази диаграма 12 и 32 могат да бъдат поставени в един и същи запис с индекс 2, но по този метод те се поставят линейно.
- Квадратно сондиране
Този метод е решение на проблема с клъстерирането по време на линейно сондиране. В този метод хеш функцията с хеш ключ се изчислява като хеш (ключ) = (хеш (ключ) + х * х)% размер на таблицата (където х = 0, 1, 2…).
Пример: 23, 12, 32 с размер на таблицата 10
Хеш (ключ) = 23% 10 = 3;
Хеш (ключ) = 12% 10 = 2;
Хеш (ключ) = 32% 10 = 2;
В това можем да видим, че 23 и 12 могат да бъдат поставени лесно, но 32 не могат, тъй като отново 12 и 32 споделят същия запис със същия индекс в таблицата, както при този метод hash (ключ) = (32 + 1 * 1) % 10 = 3. Но в този случай записът в таблица с индекс 3 се поставя с 23, така че трябва да увеличим x стойност с 1. Hash (ключ) = (32 + 2 * 2)% 10 = 6. Така че сега можем да поставим 32 във вписването с индекс 6 в таблицата.
- Двойно хеширане
Този метод трябва да изчислим 2 хеш функции, за да разрешим проблема на сблъсъка. Първият се изчислява с помощта на прост метод на разделяне. Второто трябва да отговаря на две правила; тя не трябва да е равна на 0 и записите трябва да бъдат сондирани.
- 1 (ключ) = ключ% размер на таблицата.
- 2 (ключ) = p - (клавиш mod p), където p е прости числа <размер на таблицата.
Пример: 23, 12, 32 с размер на таблицата 10
Хеш (ключ) = 23% 10 = 3;
Хеш (ключ) = 12% 10 = 2;
Хеш (ключ) = 32% 10 = 2;
В това отново елемент 32 може да бъде поставен с помощта на hash2 (ключ) = 5 - (32% 5) = 3. Така 32 може да бъде поставен в индекс 5 в таблицата, който е празен, тъй като трябва да прескочим 3 записа, за да го поставим.
Заключение-Хеширане функция в С
Хеширането е една от важните техники по отношение на търсенето на данни, осигурени с много ефективни и бързи методи, използващи хеш-функция и хеш-таблици. Всеки елемент може да бъде търсен и поставен с помощта на различни методи на хеширане. Тази техника е много по-бърза от всяка друга структура на данните по отношение на коефициента на времето.
Препоръчителни статии
Това е ръководство за функцията на хеширане в C. Тук обсъждаме въвеждането на функцията на хеширане в C, какво е Hash функция, типове хеш функция и др. Можете също да разгледате и другите ни предложени статии, за да научите повече -
- Хеширане в СУБД
- Процес на шифроване
- Как да инсталирате CakePHP?
- Как работи Blockchain
- Функция хеширане в Java
- Функция на хеширане в PHP | Как да работи?