Концепти на хаширање


Вовед

Методот на организација на Hash File е оној каде податоците се зачувуваат во блоковите на податоци чија адреса се генерира со употреба на хаш функција. Мемориската локација каде што се зачувани овие записи се нарекува блок на податоци или кофа со податоци. Оваа кофа со податоци е способна да зачувува една или повеќе записи.

Функцијата хаш може да користи која било од вредноста на колоната за да ја генерира адресата. Поголемиот дел од времето, функцијата хаш користи примарен клуч за генерирање на индексот на хаш - адреса на блокот на податоци. Хаш функцијата може да биде едноставна математичка функција за која било комплексна математичка функција. Можеме да го сметаме и самиот примарен клуч како адреса на блокот со податоци. Тоа значи дека секој ред ќе биде зачуван во блокот со податоци чија адреса ќе биде иста како примарен клуч. Ова подразбира колку е едноставна хаш-функцијата во базата на податоци.

Над дијаграмот е прикажана адреса на блок на податоци исто како и примарната клучна вредност. Оваа хаш функција може да биде и едноставна математичка функција како mod, sin, cos, експоненцијална итн. Замислете дека имаме хаш функција како mod (5) за да ја одредиме адресата на блокот со податоци Па, што се случува со горенаведениот случај? Применува мод (5) на примарните клучеви и генерира 3,3,1,4 и 2 соодветно и записите се зачувуваат во тие адреси на блокови со податоци.

Од над два дијаграма сега е јасно како функционира хаш функцијата.

Постојат два вида на организации со хаш-датотеки - Статични Динамична Хаширање.

Статичко хаширање

Во овој метод на хаширање, добиената адреса на корпата за податоци ќе биде секогаш иста. Тоа значи, ако сакаме да генерираме адреса за EMP_ID = 103 користејќи хаш функција mod (5), таа секогаш резултира со иста адреса на корпата 3. Нема да има промени во адресата на корпата тука. Оттука, бројот на кофи со податоци во меморијата за ова статичко хаширање останува постојан во текот на целиот тек. Во нашиот пример, ќе имаме пет кофи со податоци во меморијата што се користи за складирање на податоците.

Пребарување запис

Користејќи ја функцијата хаш, генерирана е адреса на кофа со податоци за копчето за хаш. Записот потоа се зема од таа локација. т.е. ако сакаме да го повратиме целиот запис за ID 104, и ако хаш функцијата е mod (5) на ID, генерираната адреса ќе биде 4. Тогаш ние директно ќе треба да ја адресираме 4 и да го вратиме целиот запис за ID 104. Еве делува како хаш-клуч.

Вметнување запис

Кога треба да се вметне нов запис во табелата, ќе генерираме адреса за новиот запис заснован на неговиот хаш-клуч. Откако ќе се генерира адресата, записот е зачуван на таа локација.

Избришете запис

Користејќи ја функцијата хаш, прво ќе го преземеме записот за кој се претпоставува дека е избришан. Потоа, ќе ги отстраниме записите за таа адреса во меморијата.

Ажурирајте запис

Записот за податоци означен за ажурирање ќе се пребарува со употреба на статичка хаш функција и потоа снимањето на таа адреса се ажурира.

 

Да претпоставиме дека треба да внесеме некои записи во датотеката. Но, адресата на корпата за податоци генерирана од функцијата хаш е полна или податоците веќе постојат на таа адреса. Како ги вметнуваме податоците? Оваа ситуација во статичкото хаширање се нарекува прелевање на кофата. Ова е една од критичните ситуации / недостаток во овој метод. Каде ќе ги зачуваме податоците во овој случај? Не можеме да ги изгубиме податоците. Постојат различни методи за надминување на оваа состојба. Најчесто користените методи се наведени подолу:

Затворено хаширање

Во овој метод воведуваме нова кофа со податоци со иста адреса и ја поврзуваме по целосната кофа со податоци. Овие методи за надминување на прелевањето на корпата се нарекуваат затворено хаширање или ланење со прелевање.

Размислете дека треба да внесеме нов запис R2 во табелите. Статичката хаш функција ја генерира адресата на корпата за податоци како 'AACDBF'. Но, оваа кофа е полна за складирање на новите податоци. Она што е направено во овој случај е нова кофа за податоци што се додава на крајот од корпата за податоци „AACDBF“ и е поврзана со неа. Потоа, новиот рекорд R2 е вметнат во новата кофа. Така ја одржува статичката адреса за хаширање. Може да додаде било кој број нови кофи за податоци, кога е полна.

Отворено хаширање

Во овој метод, се користи следниот достапен блок со податоци за внесување на новиот запис, наместо за пребришување на постариот. Овој метод се нарекува Отворено хаширање или линеарно сондирање.

Во подолу примерот, R2 е нов запис што треба да се вметне. Но, функцијата хаш генерира адреса како 237. Но, таа е веќе полна. Значи, системот ја пребарува следната достапна кофа со податоци, 238 и му доделува R2 на него.

Во линеарната сонда, разликата помеѓу постарата корпа и новата кофа обично е фиксирана и таа ќе биде 1 во повеќето случаи.

Квадратно сондирање

Ова е слично на линеарно сондирање. Но, тука, разликата помеѓу старата и новата кофа е линеарна. Ние користиме квадратна функција за да ја одредиме новата адреса на корпата.

Двојно хаширање

Ова е исто така уште еден метод на линеарно сондирање. Тука разликата е фиксирана како во линеарно сондирање, но оваа фиксна разлика се пресметува со употреба на друга хаш функција. Оттука, името е двојно хаширање.

Динамичко хаширање

Овој метод на хаширање се користи за надминување на проблемите со статичко хаширање - прелевање на корпи. Во овој метод на хаширање, корпите за податоци растат или се намалуваат со зголемувањето или намалувањето на записите. Овој метод на хаширање е познат и како метод на продолжување на хаширање. Ајде да видиме пример за да го разбереме овој метод.

Размислете дека има три записи R1, R2 и R4 во табелата. Овие записи генерираат адреси 100100, 010110 и 110110, соодветно. Овој метод на зачувување разгледува само дел од оваа адреса - особено само првиот бит за зачувување на податоците. Така, се обидува да вчита три од нив на адреса 0 и 1.

Што ќе се случи со R3 тука? Нема простор за кофа за R3. Кофата треба да расте динамично за да се смести R3. Значи, таа ја менува адресата има 2 бита отколку 1 бит, а потоа ги ажурира постојните податоци за да има 2-битна адреса. Потоа се обидува да го прими R3.

Сега можеме да видиме дека адресата на R1 и R2 се менува за да ја одразува новата адреса и исто така е вметната R3. Како што се зголемува големината на податоците, тие се обидуваат да ги вметнат во постојните кофи. Доколку не се достапни кофи, бројот на битови се зголемува за да се разгледа поголема адреса, а со тоа се зголемуваат и корпите. Ако избришеме кој било запис и ако податоците може да се зачуваат со помалку кофи, тоа ја намалува големината на корпата. Тоа го прави спротивното од она што го видовме погоре. Вака работи динамично хаширање. Првично, само делумниот индекс / адреса генерирана од функцијата хаш се смета за зачувување на податоците. Како што се зголемува бројот на податоци и има потреба од повеќе кофа, се разгледува поголем дел од индексот за складирање на податоците.

Предности на динамичко хаширање

  • Перформансите не се намалуваат бидејќи податоците растат во системот. Тоа едноставно ја зголемува големината на меморијата за да се прилагодат на податоците.
  • Бидејќи расте и се намалува со податоците, меморијата е добро искористена. Нема да лаже неискористена меморија.
  • Добро за динамични бази на податоци каде што податоците растат и се намалуваат често.

 

Недостатоци на динамичко хаширање

  • Како што се зголемува големината на податоците, така се зголемува и големината на корпата. Овие адреси ќе се одржуваат во табелите за адреси на кофата. Ова е затоа што, адресата на податоците продолжува да се менува додека корпите растат и се намалуваат. Кога има огромно зголемување на податоците, одржувањето на оваа табела за адреси на кофа станува досадно.
  • Ситуацијата за прелевање на корпите ќе се појави и во овој случај. Но, можеби е потребно малку време за да се постигне оваа ситуација отколку статичното хаширање.

Споредба на нарачаното индексирање и хаширање

Нарачано индексирање

Хашинг

Адресите во меморијата се подредени според клучната вредност. Оваа вредност на клучот може да биде примарен клуч или која било друга колона во табелата.Адресите се генерираат со употреба на хаш функција на клучната вредност. Оваа вредност на клучот може да биде примарен клуч или која било друга колона во табелата.
Перформансите на овој метод се намалуваат со зголемувањето на податоците во датотеката. Бидејќи ги зачувува податоците во сортирана форма, кога има операција за вметнување / бришење / ажурирање, потребни се дополнителни напори за сортирање на записот. Ова ги намалува неговите перформанси.Перформансите на динамичко хаширање ќе бидат добри кога има чести додатоци и бришење на податоците. Но, ако базата на податоци е многу огромна, одржувањето ќе чини поскапо.

Статичкото хаширање ќе биде добро за помалите бази на податоци каде што претходно беше познат ID на големината на записот. Ако има раст на податоците, тоа резултира со сериозни проблеми како прелевање на корпите.

.Е има неискористени блокови на податоци поради операција за бришење / ажурирање. Овие блокови на податоци нема да бидат објавени за повторна употреба. Оттука, потребно е периодично одржување на меморијата. Друго, меморијата се троши и перформансите исто така ќе се влошат. Исто така, трошоците ќе бидат трошоци за одржување на меморијата.И во статичко и во динамично хаширање, меморијата е добро управувана. Исто така, со преливот на кофата се постапува во подобра мера при статичко хаширање. Податоците блокови се дизајнирани да се намалуваат и растат во динамично хаширање.

Но, ќе има надминување на одржувањето на табелата за корпи за адреси во динамично хаширање кога има огромен раст на базата на податоци.

Преферирано е за пребарување опсег на податоци - тоа значи кога има податоци за пребарување за одреден опсег, овој метод е најсоодветен.Овој метод е погоден за враќање на одреден запис заснован на клучот за пребарување. Но, нема да се претстави подобро ако функцијата хаш не е на копчето за пребарување.