Pode explicar o princípio de funcionamento de uma tabela hash e como os dados são armazenados nela?

Uma tabela de hash é uma estrutura de dados que fornece acesso muito rápido aos dados por chave. O seu funcionamento baseia-se na utilização de uma função de hash, que transforma a chave num índice de um array onde o valor correspondente é armazenado.

Quando é necessário guardar um par chave-valor, a função de hash calcula o índice, e os dados são colocados na célula do array nesse índice. Ao procurar pela chave, a função de hash calcula novamente o índice, e o valor necessário é encontrado rapidamente.

Se duas chaves diferentes geram o mesmo índice (colisão), normalmente é utilizado o método de cadeias: na célula é armazenada uma lista de todos os elementos com esse índice, e a pesquisa é feita nessa lista.

Exemplo em Dart (Flutter):

void main() {
  Map<String, int> hashTable = {};
  hashTable['apple'] = 5;
  hashTable['banana'] = 3;

  print(hashTable['apple']); // 5
}

Aqui, Map é uma implementação de uma tabela de hash, onde a chave é uma string e o valor é um número.