Maišos funkcija

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.

Maišos funkcija (angl. hash function) - tai funkcija h = h(m), priskirianti argumentui m pseudoatsitiktinį skaičių, vadinamą maišos kodu. Tam pačiam argumentui funkcija visada turi duoti tokį patį rezultatą, taigi ji nėra atsitiktinė. Dažniausiai funkcijos reikšmių sritis yra, palyginti su apibrėžimo sritimi, nedidelė.

Pagrindinės maišos funkcijos savybės:

• apibrėžimo sritis didelė palyginti su fiksuoto dydžio reikšmių sritimi;
• funkciją nesunku apskaičiuoti bet kokiam argumentui;
• daug kartų kviečiant funkciją su įvairiais argumentais, jos rezultatai pasiskirsto tolygiai;
• pagal rezultatą negalima vienareikšmiškai nustatyti argumento;
• labai sunku surasti du argumentus m₁ ir m₂ tokius, kad h(m₁) = h(m₂) (svarbu kriptografijoje).

Maišos funkcijos naudojamos:

• kai kuriose duomenų struktūrose rikiuojant duomenis.
• duomenų bazėse (maišos jungtyse).
• įvairioje programinėje įrangoje - patikrinimui, ar tam tikri duomenys (pavyzdžiui, failas) nepakeisti sistemos išorėje.
• kriptografijoje
• rikiavimo algoritmuose (pavyzdžiui, sujungiant skaitmeninį rikiavimą su kurio nors kitu)

Jei funkcijos apibrėžimo sritis yra objektas, kaip maišos funkcija neretai vartojamas fizinis to objekto adresas kompiuterio atmintyje. Tuomet tariama, jog kiekvienas objektas gali būti lygus tik sau pačiam. Jei pagal programos algoritmą du skirtingą padėtį atmintyje užimantys objektai gali būti lygūs tarpusavyje, būtina iš naujo apibrėžti ne tik palyginimo operaciją, bet tos klasės objektams taikomą maišos funkciją, pakeičiant du sutartus, kiekvieno objekto turimus virtualius metodus (pavyzdžiui, equals ir hashCode Java kalboje).

[taisyti] Nuorodos

• Maiša
• MD5