Rääkige hajutabelitest ja nende põhitegevuspõhimõttest.

Hash-tabel (hash-map) on andmestruktuur, mis rakendab assotsiatiivset massiivi ja kaardistab võtmed väärtustele.

Põhiprintsiip:

1. Hashimine: Iga võtme jaoks arvutatakse hash-kood — arvväärtus fikseeritud suurusega hash-funktsiooni abil. Hea hash-funktsioon jaotab hash-koode ühtlaselt kogu väljundvahemikus.
2. Indekseerimine: Arvutatud hash-kood kasutatakse indeksi (asendi) määramiseks massiivis, kus hoitakse vastavat väärtust. Sageli võetakse hash-kood modula massiivi suurusest (hash(key) % array_size), mis annab lõpliku indeksi.
3. Salvestamine: Massiivis vastaval indeksil hoitakse (võti, väärtus) paari.
4. Otsing: Väärtuse leidmiseks võtme järgi arvutatakse uuesti võtme hash-kood, määratakse indeks ja sellest indeksist saadakse väärtus.
5. Kollisioonid: Tekivad, kui erinevatel võtmetel on sama hash-kood. On erinevaid meetodeid kollisioonide lahendamiseks:
   • Eraldusketid (Separate Chaining): Iga massiivi indeksis hoitakse nimekiri (või muud andmestruktuuri), mis sisaldab kõiki (võti, väärtus) paare, mille hash-koodid viisid selle indeksini.
   • Ava aadress (Open Addressing): Kollisiooni korral otsitakse teist vaba kohta massiivis kindla reegli järgi (jooneline sondimine, kvadratuurne sondimine, topelt-hashimine).

Eelised:

• Keskmiselt operatsioonid sisestamine, kustutamine ja otsing on keerukusega O(1), kui hash-funktsioon on hea ja kollisioonid on harvad.

Miinused:

• Halvimal juhul võib jõudlus olla O(n), kui kõik võtmed on hash-itud samasse indeksisse (näiteks halb hash-funktsioon või suur kollisioonide arv).
• Vajalik täiendav mälu massiivi ja võimalike kollisioonide lahendamiseks.

Swiftis on hash-tabelid realiseeritud tüübi Dictionary abil:

// Näide, kuidas kasutada Dictionary Swiftis
var myDictionary: [String: Int] = ["apple": 1, "banana": 2, "orange": 3]

// Juurdepääs võtmega
let value = myDictionary["banana"] // Saab Optional(2)

// Lisamine/uudelleenustamine
myDictionary["grape"] = 4 // Lisab uue paari
myDictionary["apple"] = 10 // Uuendab väärtust "apple" võtmele

// Kustutamine
myDictionary["orange"] = nil // Kustutab "orange" paari