Mis on hash-tabel?

Hash-tabel on andmestruktuur, mis rakendab assotsiatiivset massiivi (sõnastikku). See salvestab "võti-väärtus" paare, kus võtmed on unikaalsed.

Põhiprintsiibid:

• Hash funktsioon: Muudab võtme arvuks (hash-kood või indeks). See indeks näitab salvestuskohta massiivis (kott).
• Massiiv (kotid): Tegelik "võti-väärtus" paaride salvestus.
• Kollisioonid: Situatsioon, kus erinevad võtmed genereerivad sama hash-koodi.

Kollisioonide lahendamine:

• Lõngastamise meetod (Separate chaining): Igas kotis on nimekiri (või muu andmestruktuur) elementidest, millel on sama hash-kood.
• Ava aadressimine (Open addressing): Kollisiooni korral otsitakse vaba kott, kasutades erinevaid strateegiaid (jooneline sondimine, kvadraatne sondimine, topelt-hashimine).

Omadused:

• Kiire juurdepääs: Ideaalis O(1) sisestamise, otsimise ja kustutamise operatsioonidele.
• Sõltuvus hash-funktsioonist: Hash-funktsiooni kvaliteet ja kollisioonide lahendamise strateegia mõjutavad jõudlust oluliselt.
• Mälu kasutus: Vajab täiendavat mälu kottide massiivi jaoks.

Kasutamine QA-s:

• Testandmete salvestamine (võti - parameetri nimi, väärtus - oodatud või tegelik väärtus).
• Elementide unikaalsuse kontroll (näiteks kasutaja ID-d).
• Vahemälu (cache) rakendamine.