Шта је хеширање?
Хеш је вредност која има фиксну дужину и генерише се помоћу математичке формуле. Вредности хеша користе се у компресији података, криптологији итд. У индексирању података користе се хеш вредности јер имају фиксну величину дужине без обзира на вредности које су коришћене за њихово генерисање. То чини хеш вредности да заузимају минималан простор у поређењу са другим вредностима различите дужине.
Хеш функција користи математички алгоритам за претварање кључа у хеш. До судара долази када хеш функција даје исту вредност хеширања за више кључева.
У овом упутству из алгоритма научићете:
- Шта је хеширање?
- Шта је Хасх табела?
- Хасх функције
- Квалитете добре хеш функције
- Судар
- Операције хеш табела
- Пример хеш табеле Питхон
- Објашњење шифре табеле хеширања
- Пример Питхон-овог речника
- Анализа сложености
- Апликације из стварног света
- Предности хеш табела
- Мане хеш табела
Шта је Хасх табела?
Хасх табеле је структура података која чува вредности коришћењем два кључа и вредности. Свакој вредности се додељује јединствени кључ који се генерише помоћу хеш функције.
Име кључа користи се за приступ придруженој вредности. Ово чини претраживање вредности у хеш табели врло брзим, без обзира на број ставки у хеш табели.
Хасх функције
На пример, ако желимо да чувамо евиденцију запослених, а сваки запослени је јединствено идентификован помоћу броја запосленог.
Број запосленог можемо користити као кључ и доделити податке о запосленом као вредност.
Горе наведени приступ захтеваће додатни слободни простор реда (м * н 2 ) где је променљива м величина низа, а променљива н број цифара за број запосленог. Овај приступ уводи проблем са складишним простором.
Хасх функција решава горњи проблем добијањем броја запосленог и употребом њега за генерисање хеш целобројне вредности, фиксних цифара и оптимизацијом простора за складиштење. Сврха хеш функције је стварање кључа који ће се користити за референцирање вредности коју желимо да сачувамо. Функција прихвата вредност коју треба сачувати, а затим користи алгоритам за израчунавање вредности кључа.
Следи пример једноставне хеш функције
h(k) = k1 % m
ОВДЕ,
- х (к) је хеш функција која прихвата параметар к. Параметар к је вредност за коју желимо да израчунамо кључ.
- к 1 % м је алгоритам за нашу хеш функцију где је к1 вредност коју желимо да сачувамо, а м је величина листе. За израчунавање кључа користимо оператор модула.
Пример
Претпоставимо да имамо листу фиксне величине 3 и следеће вредности
[1,2,3]
Горњу формулу можемо користити за израчунавање позиција које треба да заузима свака вредност.
Следећа слика приказује доступне индексе у нашој хеш табели.
Корак 1)
Израчунајте положај који ће тако заузети прва вредност
х (1) = 1% 3
= 1
Вредност 1 заузимаће простор на индексу 1
Корак 2)
Израчунајте положај који ће заузимати друга вредност
х (2) = 2% 3
= 2
Вредност 2 заузимаће простор на индексу 2
Корак 3)
Израчунајте положај који ће заузимати трећа вредност.
х (3) = 3% 3
= 0
Вредност 3 заузимаће простор на индексу 0
Крајњи резултат
Наша попуњена хеш табела сада ће бити следећа.
Квалитете добре хеш функције
Добра хеш функција треба да има следеће особине.
- Формула за генерисање хеша треба да користи вредност података која се чува у алгоритму.
- Хасх функција треба да генерише јединствене хеш вредности чак и за улазне податке који имају исту количину.
- Функција треба да смањи број судара. До судара долази када се иста вредност генерише за више од једне вредности.
- Вредности морају бити доследно распоређене по свим могућим хешовима.
Судар
До судара долази када алгоритам генерише исто хеширање за више од једне вредности.
Погледајмо пример.
Претпоставимо да имамо следећу листу вредности
[3,2,9,11,7]
Претпоставимо да је величина хеш табеле 7 и користићемо формулу (к 1 % м) где је м величина хеш табеле.
Следећа табела приказује хеш вредности које ће се генерисати.
| Кључ | Алгоритам хеширања (к 1 % м) | Хасх Валуе |
| 3 | 3% 7 | 3 |
| 2 | 3% 7 | 2 |
| 9 | 3% 7 | 2 |
| 11 | 3% 7 | 4 |
| 7 | 3% 7 | 0 |
Као што видимо из горњих резултата, вредности 2 и 9 имају исту хеш вредност и не можемо сачувати више од једне вредности на свакој позицији.
Дати проблем се може решити или коришћењем ланца или сондирањем. Следећи одељци детаљно разматрају уланчавање и испитивање.
Цхаининг
Ланчано повезивање је техника која се користи за решавање проблема судара коришћењем повезаних листа које имају јединствене индексе.
Следећа слика приказује како изгледа ланчана листа
И 2 и 9 заузимају исти индекс, али се чувају као повезане листе. Свака листа има јединствени идентификатор.
Предности уланчаних листа
Следеће су предности ланчаних листа:
- Ланчане листе имају боље перформансе приликом уметања података, јер је редослед уметања О (1).
- Није потребно променити величину хеш табеле која користи уланчану листу.
- Лако може да прими велики број вредности све док је на располагању слободан простор.
Сондирање
Друга техника која се користи за решавање судара је сондирање. Када се користи метода сондирања, ако дође до судара, можемо једноставно ићи даље и пронаћи празно место за чување наше вредности.
Следе методе испитивања:
| Метод | Опис |
| Линеарно сондирање | Баш као што и само име говори, овај метод тражи празне прорезе линеарно, почев од положаја на којем је дошло до судара и кретања напред. Ако се дође до краја листе и празно место није пронађено. Сондирање започиње на почетку листе. |
| Квадратно сондирање | Ова метода користи квадратне полиномске изразе за проналажење следећег слободног слота. |
| Доубле Хасхинг | Ова техника користи алгоритам секундарне хеш функције за проналажење следећег слободног слота. |
Користећи наш горњи пример, хеш табела након употребе сондирања приказала би се на следећи начин:
Операције хеш табела
Ево операција које подржавају Хасх табеле:
- Уметање - ова операција се користи за додавање елемента у хеш табелу
- Претраживање - ова Операција се користи за тражење елемената у хеш табели помоћу кључа
- Брисање - ова операција се користи за брисање елемената из хеш табеле
Уметање операција података
Операција уметања користи се за чување вредности у хеш табели. Када се нова вредност ускладишти у хеш табели, додељује јој се индексни број. Број индекса израчунава се помоћу хеш функције. Функција хеширања решава сваки судар који се догоди приликом израчунавања индексног броја.
Потражите операцију података
Операција претраживања користи се за тражење вредности у хеш табели помоћу индексног броја. Операција претраживања враћа вредност која је повезана са бројем индекса претраживања. На пример, ако вредност 6 похранимо у индекс 2, операција претраживања са индексним бројем 2 вратиће вредност 6.
Операција брисања података
Операција брисања користи се за уклањање вредности из хеш табеле. За брисање Операција се врши помоћу индексног броја. Једном када је вредност избрисана, индексни број постаје бесплатан. Може се користити за чување других вредности помоћу операције уметања.
Примена хеш табеле на примеру Питхон-а
Погледајмо једноставан пример који израчунава хеш вредност кључа
def hash_key( key, m):return key % mm = 7print(f'The hash value for 3 is {hash_key(3,m)}')print(f'The hash value for 2 is {hash_key(2,m)}')print(f'The hash value for 9 is {hash_key(9,m)}')print(f'The hash value for 11 is {hash_key(11,m)}')print(f'The hash value for 7 is {hash_key(7,m)}')
Објашњење шифре табеле хеширања
ОВДЕ,
- Дефинише функцију хасх_кеи која прихвата кључ параметара и м.
- Користи једноставну операцију модула за одређивање хеш вредности
- Дефинише променљиву м која је иницијализована на вредност 7. Ово је величина наше хеш табеле
- Израчунава и исписује хеш вредност 3
- Израчунава и исписује хеш вредност 2
- Израчунава и исписује хеш вредност 9
- Израчунава и исписује хеш вредност 11
- Израчунава и исписује хеш вредност 7
Извршење горњег кода даје следеће резултате.
The hash value for 3 is 3The hash value for 2 is 2The hash value for 9 is 2The hash value for 11 is 4The hash value for 7 is 0
Пример Питхон-овог речника
Питхон долази са уграђеним типом података који се зове Дицтионари. Речник је пример хеш табеле. Похрањује вредности помоћу пара кључева и вредности. Вредности хеша се аутоматски генеришу за нас, а сви судари се решавају у позадини.
Следећи пример показује како можете да користите тип података речника у питхон 3
employee = {'name': 'John Doe','age': 36,'position': 'Business Manager.'}print (f"The name of the employee is {employee['name']}")employee['position'] = 'Software Engineer'print (f"The position of {employee['name']} is {employee['position']}")employee.clear()print (employee)
ОВДЕ,
- Дефинише променљиву речника запослени. Име кључа користи се за чување вредности Јохн Дое, старосне доби 36 година, и позиција чува вредност Бусинесс Манагер.
- Дохваћа вредност имена кључа и исписује је у терминалу
- Ажурира вредност позиције кључа на вредност Софтверски инжењер
- Штампа вредности имена и положаја кључева
- Брише све вредности које су сачуване у нашој променљивој речника запосленик
- Штампа вредност запосленог
Покретање горњег кода даје следеће резултате.
The name of the employee is John Doe.The position of John Doe is a Software Engineer.{}
Анализа сложености
Табеле хеша имају просечну временску сложеност О (1) у најбољем случају. Најгора временска сложеност је О (н). Најгори сценарио се јавља када многе вредности генеришу исти хасх кључ, а судар морамо решити испитивањем.
Апликације из стварног света
У стварном свету, хеш табеле се користе за чување података за
- Базе података
- Асоцијативни низови
- Сетови
- Кеш меморија
Предности хеш табела
Ево предности / предности употребе хеш табела:
- Хасх табеле имају високе перформансе приликом тражења података, уметања и брисања постојећих вредности.
- Сложеност времена за хеш табеле је константна без обзира на број ставки у табели.
- Имају врло добре резултате чак и када раде са великим скуповима података.
Мане хеш табела
Ево слабости употребе хеш табела:
- Не можете користити нулл вредност као кључ.
- Колизије се не могу избећи приликом генерисања кључева помоћу. хеш функције. До судара долази када се генерише кључ који се већ користи.
- Ако функција хеширања има много судара, то може довести до смањења перформанси.
Резиме:
- Табеле хеша се користе за чување података помоћу пара кључева и вредности.
- Хеш функција користи математички алгоритам за израчунавање хеш вредности.
- До судара долази када се иста хеш вредност генерише за више од једне вредности.
- Цхаининг решава колизију стварањем повезаних листа.
- Сондирање решава колизију проналажењем празних места у хеш табели.
- Линеарно сондирање тражи следећи слободни слот ради чувања вредности почев од места у коме је дошло до судара.
- Квадратно сондирање користи полиномске изразе за проналажење следећег слободног слота када дође до судара.
- Двоструко хеширање користи алгоритам секундарне хеш функције за проналажење следећег слободног слота када дође до судара.
- Табеле хеша имају боље перформансе у поређењу са другим структурама података.
- Просечна временска сложеност хеш табела је О (1)
- Тип података речника у питхону је пример хеш табеле.
- Табеле хеша подржавају операције уметања, претраживања и брисања.
- Нулл вредност се не може користити као вредност индекса.
- Колизије се не могу избећи у хеш функцијама. Добра хеш функција смањује број судара који се јављају ради побољшања перформанси.