Fale sobre as tabelas hash e o seu princípio de funcionamento principal.

A tabela de hash (mapa de hash) é uma estrutura de dados que implementa um array associativo, mapeando chaves para valores.

Princípio de funcionamento:

1. Hashing: Para cada chave, calcula-se um código hash, um valor numérico de tamanho fixo usando uma função de hash. Uma boa função de hash distribui os códigos hash de forma uniforme por todo o intervalo de saídas.
2. Indexação: O código hash calculado é usado para determinar o índice (posição) no array onde o valor correspondente será armazenado. Frequentemente, o código hash módulo o tamanho do array (hash(chave) % tamanho_array) fornece o índice final.
3. Armazenamento: No array, no índice calculado, armazena-se um par (chave, valor).
4. Busca: Para encontrar um valor por chave, calcula-se novamente o código hash da chave, determina-se o índice, e nesse índice extrai-se o valor.
5. Colisões: Ocorrem quando diferentes chaves têm o mesmo código hash. Existem vários métodos para resolver colisões:
   • Método de encadeamento (Separate Chaining): Em cada índice do array, mantém-se uma lista (ou outra estrutura de dados) contendo todos os pares (chave, valor) cujos códigos hash levam a esse índice.
   • Método de endereçamento aberto (Open Addressing): Quando ocorre uma colisão, busca-se outro lugar livre no array de acordo com uma regra determinada (sondagem linear, sondagem quadrática, duplo hashing).

Vantagens:

• Em média, as operações de inserção, remoção e busca têm complexidade O(1), se a função de hash for boa e colisões forem raras.

Desvantagens:

• O pior caso de desempenho pode ser O(n), se todas as chaves forem hashadas no mesmo índice (por exemplo, com uma má função de hash ou muitas colisões).
• Requer memória adicional para o array e, possivelmente, para resolver colisões.

Em Swift, as tabelas de hash são implementadas com o tipo Dictionary.

// Exemplo de uso de Dictionary em Swift
var myDictionary: [String: Int] = ["apple": 1, "banana": 2, "orange": 3]

// Acesso por chave
let value = myDictionary["banana"] // Obtém Optional(2)

// Adição/atualização
myDictionary["grape"] = 4 // Adiciona um novo par
myDictionary["apple"] = 10 // Atualiza o valor para a chave "apple"

// Remoção
myDictionary["orange"] = nil // Remove o par com a chave "orange"