Paisktabel

Allikas: Vikipeedia

Paisktabel ehk räsitabel (inglise k. hash table) on andmestruktuur, milles viiakse räsifunktsiooni abil vastavusse võtmete ja väärtuste paarid (näiteks inimeste nimed ja nende telefoninumbrid).

Räsifunktsioon arvutab võtmest räsi, mis määrab elemendi asukoha (indeksi) paisktabeli massiivisis. Ideaalis on igal elemendil oma koht massiivis, kuid praktikas juhtub, et kahele võtmele arvutatakse sama asukoht ning tekib kokkupõrge (kollisioon). Sellisel juhul saab kas elemendi salvestada järgmisele vabale kohale või teha iga massiivi indeksi kohta eraldi massiiv, kuhu saab salvestada mitu ühele indeksile vastavat elementi.

Paisktabelist võtme järgi elemendi otsimine on tavaliselt kiirem kui muudest andmestruktuuridest, näiteks otsingupuust. Paisktabeli efektiivseks tööks on vajalik minimeerida kokkupõrgete võimalust. Selleks tuleb valida selline räsifunktsioon, mille põhjal leitud indeksid kattuks võimalikult vähe. Samuti on oluline kasutada piisavalt suurt massiivi, et elementidele oleks piisavalt kohti.

Paisktabeleid kasutatakse näiteks andmebaasides, vahemäludes ja assotsiatiivsetes massiivides.