Kas saaksite selgitada hash-tabeli sisemist struktuuri ja tööd?

Hash-tabel on andmestruktuur, mis salvestab paare võti-väärtus ja tagab kiire juurdepääsu andmetele võti kaudu.

Sisemine struktuur koosneb tavaliselt massiivist (ämbrid). Iga võti jaoks arvutatakse hash-funktsioon, mis muudab võtme massiivi indeksiks. See indeks näitab ämbrisse, kus väärtus on salvestatud.

Kui mitu võtit annavad sama indeksi (kollisioon), võib ämber sisaldada nimekirja või teist struktuuri kollisioonide lahendamiseks (näiteks seotud nimekiri või puu).

Peamised toimingud:

• Lisamine: arvutame hash, leiame ämber, lisame võti-väärtus paari.
• Otsing: arvutame hash, otsime võtit ämbris.
• Kustutamine: leiame võti ja eemaldame selle ämbrist.