"kollisiooniohtu" - 1 õppematerjal

Algoritmid ja andmestruktuurid eksamiks kordamine

Kui mingi võtmega kirjet on vaja otsida, siis tehakse võtmega arvutus, saadakse indeks ja vaadatakse tabelisse. Võib tekkida olukord, kus kaks erinevat võtmeväärtust arvutatakse samaks indeksiks. Näiteks on võtmed 500 ja 588. Kui mõlemale võtmele rakendada täisarvulist jagamist 100ga, on tulemuseks 5, st mõlemad kirjed tuleks paigutada lahtrisse indeksiga 5, mis pole võimalik. Sellist olukorda kutsutakse vastuoluks ehk kollisiooniks ehk põrkeks. Esiteks tuleb vähendada kollisiooniohtu: 1. Suurendada tabel 2…3 korda, kui tegelikult on vaja 2. Leida selline paiskfunktsioon, mis indeksid/paiskväärtused võimalikult ühtlaselt üle kogu tabeli jaotab Ükskõik kui kavalalt paiskfunktsiooni ka ei valiks, ei maksa loota, et vastuolusid ei teki. Seega on põhimõtteliselt kaks lahendust, mida nendega peale hakata: 1. Kollisiooniahel Algoritmid ja andmestruktuurid 2015 37