"paiskfunktsiooni" - 1 õppematerjal

Algoritmid ja andmestruktuurid eksamiks kordamine

tabeli lahtritesse 1..100. • Keerukus: parimal juhul lisamisel, otsimisel ja kustutamisel O(1). Halvim olukord tekib siis, kui kõigi võtmete jaoks arvutakse sama paiskväärtus. Sel juhul kiiruseks O(N), sõltumata kollisioonide lahendamise meetodist. 14.2 Paisktabel • Meetodit kutsutakse paisksalvestamiseks. • Igas kirjes eraldatakse üks väli, mis on võtmeks. • Sellele võtmele rakendatakse paiskfunktsiooni, mis vastavalt võtme väärtusele arvutab indeksi e tabeli lahtri aadressi. • Paiskfunktsioon tuleb valida selliselt, et arvutuse tulemus mahuks tabeli indeksite vahemikku. • Paisksalvestamiseks paigutatakse andmed paisktabelisse, mida saab realiseerida massiivina. 14.3 Paiskfunktsioon • On algoritm, mis arvutab suvalisele väärtusele vasteks täisarvu nii, et see mahub etteantud vahemikku.