Հեշ ֆունկցիա

Հեշ ֆունկցիան դա գերազանց որոշված ընթացակարգ կամ մաթեմատիկական ֆունկցիա է, որը հիշողությունը՝ ենթադրելի փոփոխականի չափով տվյալը փոխակերպում է փոքր թվի, սովորաբար մի ամբողջ թվի, որը կարող է ծառայել որպես զանգվածի ինդեքս, հեշտացնել և արագացնել մեծ տրամաբանական աղյուսակներում փնտրման աշխատանքը։ Այն արժեքները, որոնք վերադարձնում է հեշ ֆունկցիան կոչվում են հեշ արժեքներ, հեշ կոդեր կամ պարզապես հեշեր։ Հեշ ֆունկցիաները լայնորեն կիրառվում են աղյուսակների որոնումը կամ համեմատության գործողությունները արագեցնելու նպատակով, օրինակ "տվյալների բազա"-ից մասեր գտնելը, ԴՆԹ կառուցվածքների մեջ նույնատիպ հետքերի փնտրման, ուղղագրության ստուգման, բառարանների և այլ ծրագրերում հասցնելով բառարանային գործողությունների արագությունը Օ(1) կոնստանտ ժամանակի։

Հեշ ֆունկցիա
Դաս	ֆունկցիա, deterministic algorithm? և Համակարգչային ծրագիր

Հեշ ֆունկցիան կարող է քարտեզագրել երկու կամ ավելի բանալիներ մեկ հեշ արժեքի, ցանկալի է մինիմիզացնել այդպիսի բախումների առաջացումը, դա նշանակում է որ հեշ ֆունկցիան պետք է հնարավորինս պարզորեն քարտեզագրի հեշ արժեքները։ Ծրագրից կախված այլ պայմաններել կարող են նույնքան պահանջված լինել։ Չնայած այդ գաղափարը մտածել են 1950 թ., որակյալ հեշ ֆունկցիաների նախագծումը դեռևս հանդիսանում է ակտիվ հետազոտության թեմա։

Հեշ ֆունկցիաները առնչվում են (և հաճախ շփոթում են) մատնահետքերի, պատահական թվերի գեներացման, սխալների ուղղման կոդերի, թվանշանների ստուգման, և կրիպտոգռաֆիկ հեշ ֆունկցիաների հետ։ Չնայած նրան, որ այս հասկացությունները ինչ-որ իմաստով համընկնում են, յուրաքանչյուրը ունի իր կիրառությունը ու պահանջները, և նախագծված ու օպտիմիզացված են տարբեր եղանակներով։

Հեշ աղյուսակներ

Հեշ ֆունկցիաները պարզորեն օգտագործվում են հեշ աղյուսակներում, տվյալի գրառման հասցեն արագ որոշելու համար (օրինակ բառարանի սահմանումը) տրված է գտնել բանալի հանդիսացող բառը։ Սովորաբար հեշ ֆունկցիայով քարտեզագրում են որոնման բանալին հեշին՝ ստեղծելով ինդեքսը, որը ցույց կտա թե որտեղ է տվյալ գրառումը պահված։ Իսկ հեշ աղյուսակները իրենց հերթին օգտագործվում են դինամիկ բազմությունների և ասոցիացված զանգվածներ իրականացնելու համարի։ Ընդհանուր առմամբ հեշ ֆունկցիան կարող է քարտեզագրել մի քանի տարբեր բանալիներ նույն ինդեքսին, հետևաբար յուրաքանչյուր հեշ աղյուսակի դիրք ասոցացվում է (ուղղակիորեն կամ անուղղակիորեն) գրառումների ինչ-որ բազմության հետ, այլ ոչ թե մի գրառման հետ։ Սա է պատճառը, որ յուրաքանչյուր դիրքի հաճախ անվանում են փունջ և հեշ արժեքները նաև անվանում են փնջի ցուցանիշներ։ Այսպիսով հեշ ֆունկցիան միայն հուշում է ռեկորդի հասցեն՝ թե որտեղ պետք է փնտրել այն։

Գաղտնագրական հեշ ֆունկցիա դա ձևափոխություն է, որը վերցնում է հաղորդագրություն և վերադարձնում ֆիքսած երկարության տող, որը անվանում են հեշ արժեք, կամ հաղորդագրությունների հավաքածու կամ թվային մատնահետք։ Իդեալ հեշ ֆունկցիան ունի 3 հատկություն

• Շատ հեշտ է ստանալ ցանկացած տեքստի հեշ արժեքը
• Սարսափելի բարդ, կամ ընդհանրապես անհնար է հեշ արժեքից վերականգնել սկզբնական տեքստը
• Շատ անհավանական է, որ 2 տարբեր սկզբնական տեքստեր կտան նույն հեշը

Հեշ ֆունկցիաները օգտագործվում են բազմազան նպատակներով գաղտնագրման ասպարեզում և նրա սահմաններից դուրս։ Վերջիններս լայն կիրառում են գտել հաղորդագրությունների ամբողջականության ստուգման, թվային ստորագրությունների, անձորոշման և ինֆորմացիայի ապահովագրման գործում։ Հեշ ֆունկցիաների հատկություններից ելնելով կարելի է նրանց օգտագործել միանման կամ տարբերվող ֆայլերի հայտնաբերման և ինդեքսավորման գործում։ Ամենատարածված հեշ ֆունկցիաներն են MD5-ը և SHA-1-ը։ 2005-ին 2-ում էլ հանտնաբերվել են խոցելիություններ, որոնք կապված են օգտագործվող մաթեմատիկական համակարգի հետ, սա նշանակում է որ այժմ կա հզոր հեշ ֆունկցիայի պահանջ։ 2007-ին Ամերիկայի Ստանդարտների և Տեխնոլեգիայի ինստիտուտը հայտարարել է նոր ալգորիթմի մշակման մրցույթ, որը կկոչվի SHA-3 և կհանդիսանա FIPS ստանդարտի հիմքը։

Հեշ ֆունկցիան ընդունում է ցանկացած երկարության տող և վեր է ածում այն ֆիքսած երկարության տողի, որը կարելի է ընդունել որպես նախնական տողի ստորագրություն։ Այսպիսով, մեկը, ով գիտի հեշ կոդը՝ ի վիճակի չէ ստանալ նախնական տեքստը, սակայն, մեկը, ով գիտի սկզբնական տեքստը՝ կարող է ապացուցել որ հեշը ստացվել է այդ և միայն այդ տողից։ Այսպիսով հեշ ֆունկցիան պետք է վարի իրեն ինչպես պատահական ֆունկցիա, մինչդեռ պահպանելով իր միանշանակությունը և հեշտ հաշելիությունը։ Հեշ ֆունկցիան համարվում է անապահով, եթե հնարավոր է հետևյալ պայմաններից հաշվարկով ստացումը։

1. Գտնել անհայտ հաղորդագրությունը, որը համապատասխանում է հեշ կոդին
2. Գտնել ընդհարումներ, երբ 2 տարբեր սկզբնական տողեր տալիս են նույն հեշը

Հարձակվողը, որը կարող է անել թվարկվածներից որևէ մեկը, կարող է ներկայացնել չգրանցված տողը ինչպես գրանցված։ Իդեալական դեպքում պետք է ընդհանրապես հնարավոր չլինի գտնել 2 տողեր որ ունենան նույն հեշը, ինչը չի թույլ տա հարձակվողին որևէ ինֆորմացիա քաղել կոդի մասին։ Սակայն ցանկացած դեպքում հարձակվողը ստանում է մինիմալ ինֆորմացիա տեքստի մասին՝ հեշ կոդը, ինչը թույլ կտա հետագայում ճանաչել նույն կոդը հանդիպելու դեպքում։