|
'''Räsifunktsioon''' (inglise ''hash function'') on [[krüptograafia]]s kasutatav ühesuunaline [[Funktsioon (matemaatika)|funktsioon]] [[tekstistring]]ide [[kodeerimine|kodeerimiseks]]<ref name="e-Teatmik"/>.
Räsifunktsiooni kasutatakse assotsiatiivsete massiivide ülesehituseks, andmekogumite seeriates dublikaatideduplikaatide otsimiseks, unikaalsete identifikaatorite (andmekogumite jaoks) ülesehituseks, kontroll-liitmiseks kogemata või meelega pandud (säilimisel või ülekandmisel) vigade leidmise eesmärgil, ka kaitsesüsteemide paroolide säilitamiseks (sel juhul ligipääs sellele mälukohale, kus asuvad paroolid, ei lase taastada parooli ennast).
Üldjuhul ühemõttelist vastavust lähteandmete ning räsikoodi vahel pole seetõttu, et räsifunktsiooni tähenduste arv on vähemväiksem, kui sisendmassiivi variantide arv; on olemas palju massiive erineva sisuga, mis annavad samu räsikoode - siis on tegemist nn. kollisioonidega. Kollisioonide tekkimise tõenäosus mängib suurt rolli räsifunktsioonide kvaliteedi hindamisel.
On olemas palju räsimisalgoritme erinevate omadustega (arvutuse raskus, krüpteerimiskindlus jne.) räsimisalgoritme. Ühe või teise räsifunktsiooni valiku tehaksevalik kindlaksoleneb lahendavalahendatava ülesanneülesande eripäragaeripärast.
== Ajalugu ==
[[Donald Knuth]] arvabpeab esimese räsimise süsteemiräsimissüsteemi idee autoriks [[IBM]]i kaastöötajat, kelleks on Hans Peter Lun, kes pakkus välja kodeerimist räsimise abil jaanuaris 1953. [[Arnold Dumey]] esitas oma 1956. aasta töös "Computers and automation" esimesena räsimise kontseptsiooni sellisena, millena seda teabnagu enamik programmeerijatest seda tänapäeval tunneb. Dumey vaatasnägi räsimist naguräsimises "Sõnaraamatusõnaraamatu probleemi" lahendust ning pakkus välja idee kasutada räsiaadressiks algarvuga jagamise jääki.
Esimeseks tõsiseks tööks, mis oli seotudtegeles otsimisega suurtest failidest, oli [[W. Wesley Peterson]]i artikkel 1957. aastalaasta artikkel, milles ta avaskäsitles avalikuavalikku adresseerimist ning osutas tootlikkuse halvenemisele kustutamisel. Kuus aastat hiljem avalikustatiavaldati [[Werner Buchholz]] töö, milles on tehtudläbi viidud räsifunktsioonide laipõhjalik uurimine. MitmeteMitme järgmistejärgmise aastateaasta jooksul olikasutati räsimineräsimist küll laialt kasutatudlaialdaselt, agakuid ei avalikustatud mitteavaldatud ainsatkiühtegi tähtsatolulist tööduurimust.
1967. aastal mainis räsimist kaasaegses tähenduses Herbert Hellerman oma raamatus "Numbriliste arvutisüsteemide põhimõtted". 1968. aastal avalikustasavaldas [[Robert Morris]] suureräsimisest räsimisepõhjaliku ülevaate ning seda tööd arvataksepeetakse võtmepublikatsiooniks, mis viis räsimise mõiste teaduslikku keelendi sisseteaduskeelde ning kinnistas seni vaid spetsialistide argoos kasutatud terminit "räsi".
1990-te. aastate alguseni kasutati venekeelses kirjanduses oli tänu Andrei Jeršovi töödele kasutatud termini "räsimine" ekvivalendina sõna "järjestus", ning kollisioonide jaoks kasutati terminit "konflikt". Tänapäeval on jäänud vaid sõna "räsimine".
== Räsifunktsioonide liigid ==
Hea räsifunktsioon peab vastama kahele tingimusele:
* Olemaolema kiiresti arvutatav;
* Minimiseerimaminimeerima kollisioonide arvu.
Määratletuseks oletame, et võtidevõtmete arv on <math>K</math>, ja räsifunktsioonil <math>h(K)</math> on mitte rohkem, kui <math>M</math> erinevaid tähendusi:
<math>0<h(k)<M</math>
"Halva" räsifunktsiooni näitena võib tuua funktsiooni <math>M=1000</math>, mis kümnekohalisele [[Naturaalarv|naturaalarvule]] <math>K</math> vastastab kolm numbri <math>K</math> kahekümnenda ruudu keskest valitud arvu. Tundub, et räsikoodide tähendused peaksid ühtlaselt jaotuma «000» ja «999» vahel, kuid reaalsete andmete jaoks sobib selline meetod sobib vaid juhul, kui võtmetel pole suurt nullide arvu vasakul ja paremal.{{sfn|Дональд Кнут. Искусство программирования}}
KuidOn on olemaska mitu lihtsamaidlihtsamat ja kindlamaidkindlamat meetodeidmeetodit, millelemida tuginevadkasutavad paljud räsifunktsioonid.
=== Jagamisele rajatud räsifunktsioonid ===
| 