Реци о хеш табелама и њиховом основном принципу рада…

Таблица за хеш (хеш мапа) је структура података која имплементира асоцијативни низ, мапирајући кључеве на вредности.

Основни принцип рада:

Хеширање: За сваки кључ се израчунава хеш-код — бројчана вредност фиксне величине помоћу хеш функције. Добра хеш функција равномерно распоређује хеш-кодове по целом опсегу излаза.
Индексирање: Израчунарани хеш-код се користи за одређивање индекса (позиције) у низу где ће се чувати одговарајућа вредност. Често hash(key) % величина_низа даје коначни индекс.
Складиштење: У низу, на израчунатом индексу, се чува пар (кључ, вредност).
Проналажење: За проналажење вредности по кључу, поново се израчунава хеш-код кључа, одређује се индекс, и из тог индекса се извлачи вредност.
Колизије: Настају када различити кључеви имају исти хеш-код. Постоје различите методе за решавање колизија:
- Метод ланаца (Separate Chaining): На сваки индекс низа се одржава листа (или друга структура података) која садржи све парове (кључ, вредност) чији су хеш-кодови довели до тог индекса.
- Метод отвореног адресирања (Open Addressing): Када дође до колизије, тражи се друго слободно место у низу по одређеном правилу (линеарно сондирање, квадратично сондирање, дупло хеширање).

Предности:

У просеку, операције уметања, брисања и претраге имају сложеност O(1), ако је хеш-функција добра и колизије су ретке.

Недостаци:

Најгоре, перформансе могу бити O(n), ако су сви кључеви хеширани у исти индекс (нпр. при лошој хеш-функцији или великом броју колизија).
Потребна је додатна меморија за низ и, могуће, за решавање колизија.

У Swift-у, хеш табеле су реализоване типом Dictionary.

// Пример коришћења Dictionary у Swift-у
var myDictionary: [String: Int] = ["apple": 1, "banana": 2, "orange": 3]

// Приступ по кључу
let value = myDictionary["banana"] // Добија Optional(2)

// Додавање/ажурирање
myDictionary["grape"] = 4 // Додаје нов пар
myDictionary["apple"] = 10 // Ажурира вредност за кључ "apple"

// Брисање
myDictionary["orange"] = nil // Уклања пар са кључем "orange"

Реци о хеш табелама и њиховом основном принципу рада.