Maišos funkcija

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigaciją, paiešką
 NoFonti.svg  Šiam straipsniui ar jo daliai trūksta šaltinių ar nuorodų į juos.
Jūs galite padėti Vikipedijai įrašydami tinkamas išnašas ar nuorodas į šaltinius.

Maišos funkcija[reikalingas šaltinis] (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 m1 ir m2 tokius, kad h(m1) = h(m2) (svarbu kriptografijoje).

Maišos funkcijos naudojamos:

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).

Nuorodos[taisyti | redaguoti kodą]