Sandoris: O(1) už tvarką

Pirmoje pamokoje tiesinė paieška 100 000 įrašų bibliotekoje kainavo 100 000 palyginimų. Šeštoje dvejetainė sumažino iki 17 — bet pareikalavo surikiuotų duomenų, o rikiavimas kainavo 7–9 pamokas.

Šioje pamokoje paieška kainuos maždaug vieną palyginimą. Nesvarbu, ar įrašų tūkstantis, ar milijonas.

Kaip

Nustok ieškoti. Apskaičiuok, kur įrašas turi būti.

Maišos funkcija (hash function) paverčia pavadinimą skaičiumi, o skaičius nurodo vietą lentelėje. Vienas skaičiavimas, viena vieta — jokios paieškos.

Tai skamba per gerai, ir taip yra: du skirtingi pavadinimai gali gauti tą patį skaičių. Tai vadinama kolizija, ir jos tvarkymas yra visa šios pamokos inžinerija.

Ką už tai sumoki

Kiekviena ankstesnė struktūra kažko atsisakė, kad ką nors gautų. Ši atsisako daugiausiai:

Maišos lentelė nusiperka O(1) ir sumoka TVARKA.

Masyvas žino, kas eina pirma. Surikiuotas masyvas leidžia dvejetainę paiešką. Maišos lentelė nežino nieko apie tvarką — ji žino tik „ar šis raktas čia yra".

Jokio abėcėlinio sąrašo. Jokių rėžių („visi įrašai nuo B iki D"). Jokio „kitas po šito". Jokio mažiausio, jokio didžiausio.

Aštuntame šios pamokos žingsnyje paprašysi savo indekso pateikti biblioteką abėcėlės tvarka, ir jis neatsakys. Tas neatsakytas klausimas yra 11 pamokos pradžia.

Spėk prieš skaitydamas toliau

Pastatysi lentelę su kibirais (buckets) ir grandinėlėmis. Kai kibirų per mažai, grandinėlės ilgėja.

Kiek vidutiniškai palyginimų atliksi vienam paieškos veiksmui, jei lentelėje yra 10 000 įrašų ir tik 128 kibirai?

Užsirašyk skaičių. Penktame žingsnyje pamatysi lentelę, kurioje jis yra.