Maišos funkcijos yra pagrindinė kompiuterių mokslo koncepcija ir atlieka lemiamą vaidmenį įvairiose programose, tokiose kaip duomenų saugojimas, paieška ir kriptografija. Duomenų struktūrose ir algoritmuose (DSA) maišos funkcijos pirmiausia naudojamos maišos lentelėse, kurios yra būtinos efektyviam duomenų valdymui. Šiame straipsnyje gilinamasi į maišos funkcijų sudėtingumą, jų savybes ir skirtingus DSA naudojamų maišos funkcijų tipus.

Kas yra maišos funkcija?

A maišos funkcija yra funkcija, kuri paima įvestį (arba „pranešimą“) ir grąžina fiksuoto dydžio baitų eilutę. Išvestis, paprastai skaičius, vadinama maišos kodas arba maišos vertė . Pagrindinis maišos funkcijos tikslas yra efektyviai susieti savavališko dydžio duomenis su fiksuoto dydžio reikšmėmis, kurios dažnai naudojamos kaip indeksai maišos lentelėse.

Pagrindinės maišos funkcijų savybės

• Deterministinis : maišos funkcija turi nuolat generuoti tą pačią išvestį tai pačiai įvestiei.
• Fiksuotas išvesties dydis : maišos funkcijos išvestis turi būti fiksuoto dydžio, neatsižvelgiant į įvesties dydį.
• Efektyvumas : maišos funkcija turėtų greitai apdoroti įvestį.
• Vienodumas : maišos funkcija turėtų tolygiai paskirstyti maišos reikšmes visoje išvesties erdvėje, kad būtų išvengta grupavimo.
• Atsparumas išankstiniam vaizdui : Turėtų būti neįmanoma skaičiavimo būdu pakeisti maišos funkcijos, t. y. rasti pradinę įvestį, kuriai suteikta maišos reikšmė.
• Atsparumas susidūrimui : Turėtų būti sunku rasti dvi skirtingas įvestis, kurios sukuria tą pačią maišos vertę.
• Lavinos efektas : nedidelis įvesties pakeitimas turėtų žymiai skirtis maišos reikšmė.

Maišos funkcijų taikymas

• Maišos lentelės : dažniausiai DSA maišos funkcijos naudojamos maišos lentelėse, kurios yra efektyvus duomenų saugojimo ir gavimo būdas.
• Duomenų vientisumas : maišos funkcijos naudojamos duomenų vientisumui užtikrinti generuojant kontrolines sumas.
• Kriptografija : kriptografinėse programose maišos funkcijos naudojamos saugiems maišos algoritmams, pvz., SHA-256, sukurti.
• Duomenų struktūros : maišos funkcijos naudojamos įvairiose duomenų struktūrose, tokiose kaip Bloom filtrai ir maišos rinkiniai.

Maišos funkcijų tipai

Yra daug maišos funkcijų, kuriose naudojami skaitiniai arba raidiniai ir skaitiniai klavišai. Šiame straipsnyje aptariamos įvairios maišos funkcijos:

1. Padalijimo metodas.
2. Daugybos metodas
3. Vidutinio kvadrato metodas
4. Sulankstymo būdas
5. Kriptografinės maišos funkcijos
6. Universalus maišymas
7. Tobulas maišymas

Pradėkime išsamiai aptarti šiuos metodus.

1. Padalijimo metodas

Padalijimo metodas apima rakto padalijimą iš pirminio skaičiaus ir likusios dalies naudojimą kaip maišos reikšmę.

h ( k )= k prieš m

kruskal algoritmas

Kur k yra raktas ir 𝑚 m yra pirminis skaičius.

Privalumai :

• Paprasta įgyvendinti.
• Puikiai veikia, kai 𝑚 m yra pirminis skaičius.

Trūkumai :

python sąrašo inicijavimas

• Prastas paskirstymas, jei 𝑚 m nėra pasirinktas protingai.

2. Daugybos metodas

Taikant daugybos metodą, konstanta 𝐴 A (0 m gauti maišos vertę.

žiniasklaidos perdavimas

1. Padalinkite raktą į dalis.
2. Sumuokite dalis.
3. Pasiimk modulį 𝑚 m sumos.

Privalumai :

• Paprasta ir lengva įgyvendinti.

Trūkumai :

• Priklauso nuo skirstymo schemos pasirinkimo.

5. Kriptografinės maišos funkcijos

Kriptografinės maišos funkcijos sukurtos taip, kad būtų saugios ir naudojamos kriptografijoje. Pavyzdžiui, MD5, SHA-1 ir SHA-256.

Charakteristikos :

• Atsparumas išankstiniam vaizdui.
• Antrasis išankstinio vaizdo pasipriešinimas.
• Atsparumas susidūrimui.

Privalumai :

• Aukštas saugumas.

Trūkumai :

formato eilutė java

• Intensyvus skaičiavimas.

6. Universali maiša

Universali maiša naudoja maišos funkcijų šeimą, kad sumažintų susidūrimo tikimybę bet kuriame įvesties rinkinyje.

h ( k )=(( a ⋅ k + b ) prieš p ) prieš m

Kur a ir b yra atsitiktinai parinktos konstantos, p yra pirminis skaičius, didesnis už m , ir k yra raktas.

Privalumai :

10 iš 50

• Sumažina susidūrimų tikimybę.

Trūkumai :

• Reikia daugiau skaičiavimo ir saugojimo.

7. Puikus maišymas

Tobulos maišos tikslas – sukurti statinio raktų rinkinio maišos funkciją be susidūrimų. Tai garantuoja, kad dviejų raktų maišos vertė nebus tokia pati.

Tipai :

• Minimal Perfect Hashing: užtikrina, kad maišos funkcijos diapazonas būtų lygus raktų skaičiui.
• Ne minimalus tobulas maišymas: diapazonas gali būti didesnis nei raktų skaičius.

Privalumai :

• Jokių susidūrimų.

Trūkumai :

• Sudėtinga statyti.

Išvada

Apibendrinant galima pasakyti, kad maišos funkcijos yra labai svarbūs įrankiai, padedantys greitai saugoti ir rasti duomenis. Norint, kad programinė įranga veiktų geriau ir saugiau, labai svarbu žinoti apie skirtingus maišos funkcijų tipus ir teisingai jomis naudotis. Pasirinkę darbui tinkamą maišos funkciją, kūrėjai gali labai pagerinti savo sistemų efektyvumą ir patikimumą.