Разкажете за хеш таблиците и техния основен принцип на работа.

Хеш таблицата (хеш-мап) е структура от данни, която реализира асоциативен масив, който картографира ключове към стойности.

Основен принцип на работа:

1. Хеширане: За всеки ключ се изчислява хеш-код — числова стойност с фиксиран размер чрез хеш функция. Добрата хеш функция разпределя хеш-кодовете равномерно по цялата изходна област.
2. Индексиране: Изчисленият хеш-код се използва за определяне на индекса (позицията) в масива, където ще се съхранява съответната стойност. Често hash(key) % размер_на_масива дава крайния индекс.
3. Съхранение: В масива, на изчисления индекс, се съхранява двойка (ключ, стойност).
4. Търсене: За намиране на стойност по ключ, отново се изчислява хеш-кодът на ключа, определя се индексът, и от този индекс се извлича стойността.
5. Колизии: Възникват, когато различни ключове имат един и същ хеш-код. Съществуват различни методи за разрешаване на колизии:
   • Метод на веригите (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"