Hashing հասկացությունները


ներածություն

Hash File ֆայլերի կազմակերպման մեթոդը այն մեթոդն է, որտեղ տվյալները պահվում են տվյալների բլոկներում, որոնց հասցեն առաջանում է օգտագործելով hash ֆունկցիա: Հիշողության տեղը, որտեղ պահվում են այս գրառումները, կոչվում է որպես տվյալների բլոկ կամ տվյալների դույլ: Տվյալների այս դույլը ունակ է պահելու մեկ կամ մի քանի գրառում:

Հեշ ֆունկցիան կարող է օգտագործել սյունակի ցանկացած արժեք ՝ հասցե ստեղծելու համար: Հաշ ֆունկցիան ժամանակի մեծ մասում օգտագործում է հիմնական բանալին ՝ հեշ ինդեքս առաջացնելու համար ՝ տվյալների բլոկի հասցեն: Հաշ ֆունկցիան կարող է լինել պարզ մաթեմատիկական ֆունկցիա ցանկացած բարդ մաթեմատիկական ֆունկցիայի համար: Մենք կարող ենք նույնիսկ առաջնային բանալին համարել որպես տվյալների բլոկի հասցե: Դա նշանակում է, որ յուրաքանչյուր տող կպահվի տվյալների բլոկում, որի հասցեն նույնը կլինի հիմնական բանալին: Սա ենթադրում է, թե որքան պարզ է հեշ ֆունկցիան տվյալների շտեմարանում:

Դիագրամի վերևում պատկերված է տվյալների բլոկի հասցեն նույնը, ինչ հիմնական բանալին: Այս հեշ ֆունկցիան կարող է նաև լինել պարզ մաթեմատիկական ֆունկցիա, ինչպիսին է mod, sin, cos, exponential և այլն: Պատկերացրեք, որ մենք ունենք hash ֆունկցիա որպես mod (5) ՝ տվյալների բլոկի հասցեն որոշելու համար: Այսպիսով, ի՞նչ է պատահում վերը նշված դեպքի հետ: Այն կիրառում է նախնական ստեղների վրա մոդ (5) և առաջացնում համապատասխանաբար 3,3,1,4 և 2, և գրառումները պահվում են այդ տվյալների բլոկի հասցեներում:

Երկու դիագրամների վերևից այժմ պարզ է դառնում, թե ինչպես է գործում հաշ ֆունկցիան:

Հեշ ֆայլերի կազմակերպությունները կան երկու տեսակի. Ստատիկ և Դինամիկ Կոտորելով

Ստատիկ հեշինգ

Հեշավորման այս եղանակով ստացված տվյալների դույլի հասցեն միշտ կլինի նույնը: Դա նշանակում է, որ եթե մենք ուզում ենք ստեղծել EMP_ID = 103 հասցե ՝ օգտագործելով mod (5) հեշ գործառույթը, դա միշտ հանգեցնում է նույն դույլի հասցեի 3-ին: Այստեղ դույլի հասցեում փոփոխություններ չեն լինի: Հետևաբար, այս ստատիկ հեշի համար հիշողության մեջ տվյալների դույլերի քանակը մնում է կայուն: Մեր օրինակում, տվյալների պահպանման համար օգտագործվող հիշողության մեջ, մենք կունենանք հինգ տվյալների դույլ:

Գրառման որոնում

Օգտագործելով hash գործառույթը, տվյալների շերեփի հասցեն ստեղծվում է hash ստեղնաշարի համար: Դրանից հետո գրառումը վերցվում է այդ վայրից: այսինքն; եթե ուզում ենք 104 գրառման համար վերցնել ամբողջ գրառումը, և եթե հեշ ֆունկցիան ID- ի վրա mod (5) է, ապա գեներացվող հասցեն կլինի 4-ը: Այնուհետև մենք ուղղակիորեն պետք է հասցեագրենք 4-ը և հետ վերցնենք ամբողջ գրառումը ID 104-ի համար: գործում է որպես հեշ բանալին:

Գրառում տեղադրելը

Երբ նոր գրառում պետք է տեղադրվի աղյուսակի մեջ, մենք կստեղծենք նոր գրառման հասցե ՝ հիմնվելով նրա հեշ բանալու վրա: Հասցեն առաջացնելուց հետո գրառումը պահվում է այդ վայրում:

Deleteնջել գրառումը

Օգտագործելով hash ֆունկցիան մենք առաջին հերթին բերելու ենք այն գրառումը, որը ենթադրաբար պետք է ջնջվի: Դրանից հետո մենք այդ հասցեի գրառումները կհեռացնենք հիշողության մեջ:

Թարմացրեք գրառումը

Թարմացման համար նշված տվյալների գրառումը կփնտրվի օգտագործելով ստատիկ հեշ ֆունկցիա, ապա այդ հասցեում գրառումը թարմացվում է:

 

Ենթադրենք, որ մենք պետք է որոշ գրառումներ տեղադրենք գործի մեջ: Բայց հաշ գործառույթի կողմից առաջացած տվյալների շերեփի հասցեն լրիվ է կամ տվյալներն արդեն առկա են այդ հասցեում: Ինչպե՞ս ենք տեղադրում տվյալները: Ստատիկ հեշինգում այս իրավիճակը կոչվում է դույլի վարարում, Սա այս մեթոդի կրիտիկական իրավիճակներից մեկն է: Այս դեպքում որտե՞ղ ենք պահելու տվյալները: Մենք չենք կարող կորցնել տվյալները: Այս իրավիճակը հաղթահարելու համար կան տարբեր մեթոդներ: Ստորև թվարկված են առավել հաճախ օգտագործվող մեթոդները.

Փակ հեշինգ

Այս մեթոդով մենք ներկայացնում ենք տվյալների նոր դույլ նույն հասցեով և այն կապում ենք տվյալների ամբողջական դույլից հետո: Շերեփի գերազանցումը հաղթահարելու այս մեթոդները կոչվում են փակ հեշինգ կամ վարարման շղթայակցում:

Հաշվի առեք, որ մենք պետք է աղյուսակների մեջ տեղադրենք նոր գրառում R2: Ստատիկ հեշ ֆունկցիան առաջացնում է տվյալների դույլի հասցեն որպես «AACDBF»: Բայց այս դույլը լի է ՝ նոր տվյալները պահելու համար: Այն, ինչ արվում է այս պարագայում, տվյալների նոր փաթեթ է, որը ավելացվում է «AACDBF» տվյալների շերտի վերջում և կապված է դրա հետ: Այնուհետև նոր ռեկորդ R2- ն տեղադրվում է նոր դույլի մեջ: Այսպիսով, այն պահպանում է ստատիկ հեշման հասցեն: Այն կարող է ավելացնել ցանկացած քանակի նոր տվյալների դույլ, երբ դրանք լի են:

Բաց հեշինգ

Այս մեթոդով հաջորդ մատչելի տվյալների բլոկն օգտագործվում է նոր գրառումը մուտքագրելու համար, փոխարենը հինը վերագրանցելու: Այս մեթոդը կոչվում է Open Hashing կամ գծային զոնդավորում.

Ստորև բերված օրինակում R2- ը նոր գրառում է, որը պետք է տեղադրվի: Բայց հեշ ֆունկցիան առաջացնում է հասցեն ՝ 237: Բայց դա արդեն լրիվ է: Այսպիսով, համակարգը որոնում է հաջորդ հասանելի տվյալների 238 դույլը և դրան վերագրում R2:

Գծային զոնդում հին դույլի և նոր դույլի տարբերությունը սովորաբար ամրագրված է, և դա կլինի դեպքերի մեծ մասը:

Քառակուսային զոնդավորում

Սա նման է գծային զոնդավորման: Բայց այստեղ հին և նոր դույլի տարբերությունը գծային է: Մենք օգտագործում ենք քառակուսային ֆունկցիա `դույլի նոր հասցեն որոշելու համար:

Կրկնակի կոտրում

Սա նաև գծային զննումի մեկ այլ մեթոդ է: Այստեղ տարբերությունը ամրագրված է ինչպես գծային զոնդավորման դեպքում, բայց այս ֆիքսված տարբերությունը հաշվարկվում է օգտագործելով մեկ այլ հաշ ֆունկցիա: Ուստի անունը կրկնակի հեշինգ է:

Դինամիկ կոտրում

Հեշացման այս մեթոդը օգտագործվում է ստատիկ հեշացման խնդիրները լուծելու համար `դույլի արտահոսք: Հեշացման այս մեթոդով տվյալների դույլերը աճում կամ նեղանում են, երբ գրառումները ավելանում կամ նվազում են: Հեշավորման այս մեթոդը հայտնի է նաև որպես երկարաձգվող խաշման մեթոդ: Եկեք տեսնենք մի օրինակ ՝ այս մեթոդը հասկանալու համար:

Հաշվի առեք, որ աղյուսակում կա երեք գրառում. R1, R2 և R4: Այս գրառումները առաջացնում են համապատասխանաբար 100100, 010110 և 110110 հասցեներ: Պահպանման այս մեթոդը հաշվի է առնում այս հասցեի միայն մի մասը, հատկապես միայն առաջին մեկ բիթը ՝ տվյալները պահելու համար: Այսպիսով, այն փորձում է բեռնել դրանցից երեքը 0 և 1 հասցեներում:

Ի՞նչ կլինի այստեղ R3- ի հետ: R3- ի համար դույլի տեղ չկա: R3- ը տեղավորելու համար դույլը պետք է դինամիկ աճի: Այսպիսով, այն փոխում է, որ հասցեները ունենան ավելի քան 2 բիթ, քան 1 բիթ, ապա այն թարմացնում են եղած տվյալները ՝ ունենալով 2 բիթ հասցե: Այնուհետև այն փորձում է տեղավորել R3- ը:

Այժմ մենք կարող ենք տեսնել, որ R1- ի և R2- ի հասցեն փոխվում են `արտացոլելով նոր հասցեն, և R3- ը նույնպես տեղադրվում է: Տվյալների չափը մեծանալուն պես դրանք փորձում են ներդնել առկա դույլերում: Եթե ​​դույլեր չկան, ապա բիտերի քանակը մեծանում է ՝ ավելի մեծ հասցե դիտարկելու համար, և հետևաբար դույլերն ավելանում են: Եթե ​​մենք ջնջում ենք որևէ գրառում, և եթե տվյալները կարող են պահվել ավելի քիչ դույլերով, դա փոքրացնում է դույլի չափը: Դա անում է հակառակն այն բանի, ինչ տեսանք վերևում: Այսպես է աշխատում դինամիկ հեշինգը: Սկզբում հաշի գործառույթի կողմից առաջացած միայն մասնակի ինդեքսը / հասցեն համարվում է տվյալները պահելու համար: Տվյալների քանակի ավելացման և ավելի շատ դույլի անհրաժեշտության առկայության դեպքում, տվյալների պահուստը դիտարկվում է ինդեքսի ավելի մեծ մասի համար:

Դինամիկ խաշման առավելությունները

  • Արդյունավետությունը չի իջնում, քանի որ համակարգում տվյալներն աճում են: Դա պարզապես մեծացնում է հիշողության չափը ՝ տվյալները տեղավորելու համար:
  • Քանի որ դրանք աճում և նեղանում են տվյալների հետ, հիշողությունը լավ է օգտագործվում: Չօգտագործված հիշողություն չի ստելու:
  • Հարմար է դինամիկ տվյալների շտեմարանների համար, որտեղ տվյալները հաճախ աճում և նեղանում են:

 

Դինամիկ խաշման թերությունները

  • Տվյալների չափի մեծացման հետ մեկտեղ դույլի չափը նույնպես մեծանում է: Այս հասցեները կպահպանվեն դույլ հասցեի աղյուսակներում: Դա այն պատճառով է, որ տվյալների հասցեն կշարունակվի փոխվել, քանի որ դույլերն աճում և նեղանում են: Երբ տվյալների հսկայական աճ կա, այս դույլ հասցեի աղյուսակի պահպանումը դառնում է հոգնեցուցիչ:
  • Դույլով լցվելու իրավիճակ կլինի նաև այս դեպքում: Բայց այս իրավիճակին հասնելու համար կարող է քիչ ժամանակ պահանջվել, քան ստատիկ հեշը:

Պատվերով ինդեքսավորման և հեշինգի համեմատություն

Պատվիրված ինդեքսավորում

Հեշինգ

Հիշողության հասցեները տեսակավորվում են ըստ հիմնական արժեքի: Այս առանցքային արժեքը կարող է լինել հիմնական բանալին կամ աղյուսակի ցանկացած այլ սյունակ:Հասցեները գեներացվում են օգտագործելով հիմնական գործառույթի արժեքի վրա հեշ գործառույթ: Այս առանցքային արժեքը կարող է լինել հիմնական բանալին կամ աղյուսակի ցանկացած այլ սյունակ:
Այս մեթոդի կատարումը իջնում ​​է, քանի որ ֆայլում տվյալներն ավելանում են: Քանի որ դրանք պահում են տվյալները տեսակավորված տեսքով, տեղադրման / ջնջման / թարմացման գործողություն լինելու դեպքում անհրաժեշտ է լրացուցիչ ջանք գործադրել ձայնագրությունը տեսակավորելու համար: Սա նվազեցնում է դրա կատարումը:Դինամիկ հեշինգների կատարումը լավ կլինի, երբ տվյալների հաճախակի ավելացում և ջնջում կա: Բայց եթե տվյալների բազան շատ հսկայական է, տեխնիկական սպասարկումն ավելի ծախսատար կլինի:

Ստատիկ հեշացումը լավ կլինի ավելի փոքր տվյալների շտեմարանների համար, որտեղ նախկինում հայտնի էր գրառման չափը: Եթե ​​տվյալների աճ կա, դա հանգեցնում է լուրջ խնդիրների, ինչպիսիք են դույլի արտահոսքը:

Deleteնջման / թարմացման գործողության պատճառով կլինեն չօգտագործված տվյալների բլոկներ: Տվյալների այս բլոկները չեն թողարկվի նորից օգտագործման համար: Ուստի անհրաժեշտ է հիշողության պարբերական սպասարկում: Այլապես, հիշողությունը վատնում է, և կատարումը նույնպես դեգրադացվում է: Նաև հիշողությունը պահպանելու համար գնի ընդհանուր ծախս:Ե՛վ ստատիկ, և՛ դինամիկ հեշինգում հիշողությունը լավ է կառավարվում: Շերեփի արտահոսքը նաև ավելի լավ է կարգավորվում ստատիկ կոտրման ժամանակ: Տվյալների բլոկները նախատեսված են նեղանալու և դինամիկ հեշինգում աճելու համար:

Բայց շերեփի հասցեի աղյուսակը դինամիկ հեշինգում պահելու գլխավերև կլինի, երբ տվյալների բազայի հսկայական աճ լինի:

Տվյալների տիրույթի վերականգնման համար նախընտրելի. Դա նշանակում է, երբ առկա են տվյալների տիրույթի որոշակի տիրույթի համար, այս մեթոդը լավագույնս համապատասխանում է:Այս մեթոդը հարմար է որոնման բանալիի հիման վրա որոշակի գրառում ստանալու համար: Բայց ավելի լավ չի ստացվի, եթե hash ֆունկցիան չկա որոնման բանալին: