Iš kokių komponentų sudaryta maišos lentelė?

Žodynėlis susideda iš:

1. Masyvas (arba sąrašas): Pagrindinė duomenų struktūra, kurioje saugomi elementai. Kartais vadinamas "kibirais" (buckets) arba "lizdais".
2. Hash funkcija: Funkcija, kuri priima raktą kaip įvestį ir grąžina indeksą (visas skaičius) masyve. Gera hash funkcija užtikrina vienodą raktų paskirstymą masyve, sumažindama kolizijas.
3. Kolizijų valdymo mechanizmas: Metodas, kaip spręsti situaciją, kai hash funkcija generuoja tą patį indeksą skirtingiems raktams. Du pagrindiniai metodai:
   • Atskirų grandinių (Separate Chaining): Kiekvienas masyvo elementas saugo nuorodą į sąrašą (sujungtą sąrašą, B-medį ir kt.) elementų, kurie buvo hashinti į tą indeksą.
   • Atvira adresacija (Open Addressing): Esant kolizijai, ieškoma kita laisva vieta pačiame masyve elementui įdėti. Paieškos strategijos:
     • Linijinis bandymas (Linear Probing)
     • Kvadratinis bandymas (Quadratic Probing)
     • Dvigubas hashavimas (Double Hashing)
4. Operacijos: Pagrindinių operacijų įgyvendinimas: įterpimas (insert), paieška (search), ištrynimas (delete). Šios operacijos naudoja hash funkciją, kad nustatytų elementų vietą masyve ir kolizijų valdymo mechanizmą, jei reikia.