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 massiivis oma koht, kuid praktikas juhtub, et kahele võtmele arvutatakse sama asukoht ja tekib kokkupõrge (kollisioon). Sel juhul saab elemendi salvestada järgmisele vabale kohale või teha iga massiivi indeksi kohta eraldi massiivi, 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 vaja minimeerida kokkupõrgete võimalust. Selleks tuleb valida selline räsifunktsioon, mille põhjal leitud indeksid kattuksid võimalikult harva. Samuti on oluline kasutada piisavalt suurt massiivi, et elementidele oleks piisavalt kohti.

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