Maišos funkcija

Maišos funkcija (angl. hash function) – tai 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 yra, palyginti su , 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 kuriuo 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 (pavyzdžiui, equals ir hashCode Java kalboje).

Šaltiniai

1. Maišos funkcija. V. Dagienė, G. Grigas, T. Jevsikova. Enciklopedinis kompiuterijos žodynas. 4-as leidimas. Vilnius: VU MII, 2014 // EKŽ, 2021, nuolat atnaujinamas. ISBN 978-9986-680-52-9.

Nuorodos

• MD5
• Gegutės maiša