Хеш функция
В този раздел ще обсъдим хеш функцията, която помага да се изпълни хеш кодът на свързания ключ на елемента с данни в структурата на данните, както е споменато по-долу:
Int hashItem ( вътр ключ ){
връщане ключ % размер на масата ;
}
Процесът на изпълнение на индекса на масив се нарича хеширане. Понякога се изпълнява един и същи тип код, за да се генерира същия индекс, като се използват едни и същи ключове, наречени сблъсъци, които се обработват чрез различни вериги (създаване на свързан списък) и внедряване на отворени стратегии за адресиране.
Работа с хеш таблица в C++
Указателите към реалните стойности се съхраняват в хеш-таблицата. Той използва ключ за търсене на индекса на масив, в който стойностите срещу ключовете трябва да бъдат съхранени на желаното място в масив. Взехме хеш таблицата с размер 10, както е споменато по-долу:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
Нека да вземем на случаен принцип всякакви данни срещу различни ключове и да съхраним тези ключове в хеш таблица, като просто изчислим индекса. И така, данните се съхраняват спрямо ключовете в изчисления индекс с помощта на хеш функция. Да предположим, че вземем данни = {14,25,42,55,63,84} и ключове = [ 15,9,5,25,66,75 ].
Изчислете индекса на тези данни с помощта на хеш функцията. Стойността на индекса е посочена в следното:
| Ключ | петнадесет | 9 | 29 | 43 | 66 | 71 |
|---|---|---|---|---|---|---|
| Изчислете индекса | 15%10 = 5 | 9%10=0 | 29%10=9 | 43%10=3 | 66%10=6 | 71%10=1 |
| Данни | 14 | 25 | 42 | 55 | 63 | 84 |
След като създадете индекса на масив, поставете данните срещу ключа върху точния индекс на даден масив, както е описано по-горе.
| 25 | 84 | 55 | 14 | 63 | 42 | ||||
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
След това можем да видим, че възниква сблъсък, ако два или повече ключа имат един и същ хеш код, което води до същия индекс на елементите в масива. Имаме едно решение за избягване на шансовете за сблъсък: избор на добър хеш метод и прилагане на точните стратегии.
Сега нека обсъдим различните техники за внедряване с помощта на подходящи примери.
Пример: Добавете данни в хеш-таблица с помощта на отворена хешираща техника
В този пример използваме техника за внедряване като Open Hashing, за да избегнем сблъсък в хеш-таблицата. При отворено хеширане или верижно свързване създаваме свързан списък, за да веригираме стойностите на хеш-таблицата. Кодовият фрагмент на този пример е приложен в следното, което описва отворената хешираща техника:
#include#include <списък>
клас Хеш-таблица {
частен :
статичен конст вътр tableSize = 10 ;
std :: списък < вътр > tableHas [ tableSize ] ;
вътр hashFunc ( вътр ключ ) {
връщане ключ % tableSize ;
}
публичен :
невалиден вмъкнете ( вътр ключ ) {
вътр индекс = hashFunc ( ключ ) ;
tableHas [ индекс ] . избутвам ( ключ ) ;
}
невалиден viewTable ( ) {
за ( вътр аз = 0 ; аз < tableSize ; ++ аз ) {
std :: cout << '[' << аз << ']' ;
за ( Автоматичен то = tableHas [ аз ] . започвам ( ) ; то ! = tableHas [ аз ] . край ( ) ; ++ то ) {
std :: cout << ' -> ' << * то ;
}
std :: cout << std :: endl ;
}
}
} ;
вътр основен ( ) {
HashTable hasTable ;
hasTable. вмъкнете ( петнадесет ) ;
hasTable. вмъкнете ( 33 ) ;
hasTable. вмъкнете ( 23 ) ;
hasTable. вмъкнете ( 65 ) ;
hasTable. вмъкнете ( 3 ) ;
hasTable. viewTable ( ) ;
връщане 0 ;
}
Това е много интересен пример: създаваме свързан списък и вмъкваме данните в хеш-таблицата. Първо, ние дефинираме библиотеките в началото на програмата. The < списък > библиотека се използва за внедряване на свързан списък. След това изграждаме клас с име „HashTable“ и създаваме атрибутите на класа, които са частни като размер на таблица и масив от таблици, използвайки ключовата дума „private:“. Не забравяйте, че частните атрибути не могат да се използват извън класа. Тук приемаме размера на таблицата като „10“. Инициализираме хеш метода с помощта на това и изчисляваме индекса на хеш таблицата. В хеш функцията предаваме ключа и размера на хеш таблицата.
Създаваме няколко необходими функции и ги правим публични в класа. Не забравяйте, че публичните функции могат да се използват извън класа навсякъде. Използваме ключовата дума „public:“, за да стартираме публичната част на класа . Тъй като искаме да добавим нови елементи към хеш-таблицата, създаваме функция с име „InsertHash“ с ключ като аргумент на функцията. Във функцията „вмъкване“ инициализираме индексната променлива. Предаваме хеш функцията на индексната променлива. След това прехвърлете индексната променлива към свързания списък tableHas[], като използвате метода „push“, за да вмъкнете елемент в таблицата.
След това изграждаме функция „viewHashTab“, за да покажем хеш-таблицата, за да видим нововмъкнатите данни. В тази функция вземаме цикъл „for“, който търси стойностите до края на хеш-таблицата. Уверете се, че стойностите се съхраняват при същия индекс, който е разработен с помощта на хеш функция. В цикъла предаваме стойностите на съответния им индекс и завършваме класа тук. Във функцията „main“ вземаме обекта от клас с име „hasTable“. С помощта на този клас обект можем да получим достъп до метода на вмъкване, като подадем ключа в метода. Ключът, който предадохме във функцията „main“, се изчислява във функцията „insert“, която връща позицията на индекса в хеш-таблицата. Показахме хеш-таблицата, като извикахме функцията „view“ с помощта на обект „Class“.
Резултатът от този код е приложен в следното:
Както виждаме, хеш-таблицата е създадена успешно с помощта на свързания списък в C++. Отвореното верижно свързване се използва, за да се избегне сблъсък на един и същи индекс.
Заключение
В крайна сметка заключихме, че хеш-таблицата е най-новата техника за съхраняване и получаване на ключовете с двойки стойности, за да се справят ефективно с огромни количества данни. Шансовете за сблъсък са много високи в хеш-таблицата, унищожавайки данните и тяхното съхранение. Можем да преодолеем този сблъсък, като използваме различни техники за управление на хеш таблицата. Чрез разработването на хеш-таблицата в C++, разработчиците могат да увеличат производителността, като използват най-подходящата техника за съхраняване на данните в хеш-таблицата. Надяваме се, че тази статия е полезна за вашето разбиране на хеш-таблицата.