Pastāsti par hash tabulām un to galveno darbības principu.

Hash-tabula (hash-map) ir struktūra datu, kas realizē asociatīvo masīvu, kas attēlo atslēgas uz vērtībām.

Galvenais darba princips:

1. Hashēšana: Katram atslēgai tiek aprēķināts hash kods — skaitliska vērtība, izmantojot hash funkciju. Labas hash funkcijas vienmērīgi sadala hash kodus pa visu izvades diapazonu.
2. Indeksēšana: Aprēķinātais hash kods tiek izmantots, lai noteiktu indeksu (pozīciju) masīvā, kur tiks glabāta atbilstošā vērtība. Bieži hash kods tiek ņemts modulo no masīva izmēra (hash(key) % array_size), iegūstot galīgo indeksu.
3. Glabāšana: Masīvā pēc aprēķinātā indeksa tiek glabāta (atslēga, vērtība) pāris.
4. Meklēšana: Lai atrastu vērtību pēc atslēgas, vēlreiz tiek aprēķināts atslēgas hash kods, noteikts indekss, un no šī indeksa tiek iegūta vērtība.
5. Kolīzijas: rodas, kad dažādiem atslēgām ir tas pats hash kods. Ir dažādas metodes kolīziju risināšanai:
   • Atsevišķu ķēžu metode (Separate Chaining): Katram masīva indeksam tiek glabāts saraksts (vai cita datu struktūra), kas satur visus (atslēga, vērtība) pārus, kuru hash kodi noveda pie šī indeksa.
   • Atvērtās adresēšanas metode (Open Addressing): Kolīzijas gadījumā meklē citu brīvu vietu masīvā pēc noteikta noteikuma (tiešais sēdēšana, kvadrātiskā sēdēšana, dubultā hashēšana).

Priekšrocības:

• Vidēji operācijas ievietošana, dzēšana un meklēšana ir ar sarežģītību O(1), ja hash funkcija ir laba un kolīzijas ir retas.

Trūkumi:

• Sliktākajā gadījumā veiktspēja var būt O(n), ja visi atslēgas tiek hashēti vienā un tajā pašā indeksā (piemēram, slikta hash funkcija vai liels kolīziju skaits).
• Nepieciešama papildu atmiņa masīvam un iespējams kolīziju risināšanai.

Swift hash-tabulas ir realizētas ar Dictionary tipu:

// Piemērs, kā izmantot Dictionary Swift
var myDictionary: [String: Int] = ["apple": 1, "banana": 2, "orange": 3]

// Pieejas pēc atslēgas
let value = myDictionary["banana"] // Saņem Optional(2)

// Pievienošana/atjaunināšana
myDictionary["grape"] = 4 // Pievieno jaunu pāri
myDictionary["apple"] = 10 // Atjaunina vērtību "apple" atslēgai

// Dzēšana
myDictionary["orange"] = nil // Dzēš "orange" pāri