hash table



räsitabel Otsingutabel, mis on mõeldud selliste võtmete (kontonumbrid, detailinumbrid, firma töötajate perekonnanimed jne) efektiivseks salvestamiseks, mille tähestikulises või numbrilises jadas võivad olla suured tühikud.

Otsingutabelites vastab igale võtmele teatud väärtus ning kui võtmeteks oleks näit. väärtuste unikaalsed järjekorranumbrid, siis oleks kõige mõistlikum kasutada lineaarset otsingut - võtmed vaadatakse üks kord läbi ja sobiva võtme järgi leitakse vajalikud andmed. Kui aga võtmeteks on näiteks firma töötajate perekonnanimed (stringid), siis tuleks lineaarse otsingu korral võrrelda neid stringe tähthaaval, mis on väga aeganõudev. Selle asemel arvutatakse räsifunktsiooni (räsialgoritmi) abil välja kõigi võtmete (antud näites perekonnanimede) räsiväärtused ning kui kahe või enama võtme räsiväärtused tulevad samad, siis vastavad võti-väärtus paarid paigutatakse ühte nn. räsipange. Räsialgoritm püütakse valida selliselt, et igasse räsipange satuks võimalikult vähe võti-väärtus paare. Kui nüüd on vaja leida tabelist töötaja Karupoeg andmed, siis kõigepealt arvutatakse sama räsifunktsiooni abil stringi "Karupoeg" räsiväärtus, leitakse vastav räsipang ja täht-tähelist võrdlust tuleb nüüd teostada ainult selles räsiämbris leiduvate nimede osas. Selline meetod võimaldab tunduvalt tõsta andmeotsingu efektiivsust, mis on eriti oluline suurte tabelite puhul