Opowiedz o tablicach haszujących i ich głównym zasadzie działania.

Tablica haszowa (mapa haszowa) to struktura danych, która implementuje tablicę asocjacyjną, mapując klucze na wartości.

Zasada działania:

1. Hashowanie: Dla każdego klucza oblicza się kod hash — wartość numeryczną o stałym rozmiarze za pomocą funkcji hash. Dobra funkcja hash równomiernie rozkłada kody hash w całym zakresie wyjść.
2. Indeksowanie: Obliczony kod hash jest używany do określenia indeksu (pozycji) w tablicy, gdzie będzie przechowywana odpowiednia wartość. Często hash(key) % rozmiar_tablicy daje końcowy indeks.
3. Przechowywanie: W tablicy, pod obliczonym indeksem, przechowuje się parę (klucz, wartość).
4. Wyszukiwanie: Aby znaleźć wartość po kluczu, ponownie oblicza się kod hash klucza, określa indeks i z tego indeksu wyciąga się wartość.
5. Kolizje: Powstają, gdy różne klucze mają ten sam kod hash. Istnieją różne metody rozwiązywania kolizji:
   • Metoda łańcuchowa (Separate Chaining): Pod każdym indeksem tablicy przechowuje się listę (lub inną strukturę danych), zawierającą wszystkie pary (klucz, wartość), których kody hash doprowadziły do tego indeksu.
   • Metoda otwartego adresowania (Open Addressing): Gdy występuje kolizja, szuka się innego wolnego miejsca w tablicy według określonej reguły (sondowanie liniowe, kwadratowe, podwójne haszowanie).

Zalety:

• Średnio operacje wstawiania, usuwania i wyszukiwania mają złożoność O(1), jeśli funkcja hash jest dobra i kolizje są rzadkie.

Wady:

• Najgorszy przypadek wydajności może wynosić O(n), jeśli wszystkie klucze są haszowane do tego samego indeksu (np. przy złej funkcji hash lub dużej liczbie kolizji).
• Wymaga dodatkowej pamięci na tablicę i, być może, na rozwiązywanie kolizji.

W Swift, tablice haszujące są zaimplementowane za pomocą typu Dictionary.

// Przykład użycia Dictionary w Swift
var myDictionary: [String: Int] = ["apple": 1, "banana": 2, "orange": 3]

// Dostęp po kluczu
let value = myDictionary["banana"] // Zwraca Optional(2)

// Dodanie/aktualizacja
myDictionary["grape"] = 4 // Dodaje nową parę
myDictionary["apple"] = 10 // Aktualizuje wartość dla klucza "apple"

// Usunięcie
myDictionary["orange"] = nil // Usuwa parę z kluczem "orange"